P13 - 直接实现游程编码
Direct run-length encoding of a list
官方模块:
Problems.P13核心函数:encodeDirect
题目描述
实现游程编码，但不借助 pack 或 group 等中间打包步骤——直接边遍历边计数，生成 [Encoding a]。
结果格式与 P11 相同：单个元素用 Single，重复元素用 Multiple n。
函数签名
1encodeDirect :: Eq a => [a] -> [Encoding a]
思路
遍历列表，用一个计数器记录当前连续重复元素的个数：
- 当前元素和下一个不同 → 结束当前组，输出
Single或Multiple，重置计数器 - 当前元素和下一个相同 → 计数器加 1，继续
实现
方法一：递归 + 累加器
1encodeDirect :: Eq a => [a] -> [Encoding a]
2encodeDirect [] = []
3encodeDirect (x:xs) = go x 1 xs
4 where
5 go a n [] = [toEncoding a n]
6 go a n (b:bs)
7 | a == b = go a (n + 1) bs
8 | otherwise = toEncoding a n : go b 1 bs
9
10 toEncoding x 1 = Single x
11 toEncoding x n = Multiple n x
go a n 维护当前元素 a 和出现次数 n。遇到不同元素时，把当前组输出为 Encoding，重置计数器处理新元素。
方法二：使用 span 简化
1encodeDirect :: Eq a => [a] -> [Encoding a]
2encodeDirect [] = []
3encodeDirect (x:xs) = case span (== x) xs of
4 (same, rest) -> let n = 1 + length same
5 in (if n == 1 then Single x else Multiple n x) : encodeDirect rest
span 自动切分出与 x 相等的连续段，比手动维护计数器更简洁。
方法三：使用 foldr
1encodeDirect :: Eq a => [a] -> [Encoding a]
2encodeDirect = foldr go []
3 where
4 go x [] = [Single x]
5 go x (Single y : rest)
6 | x == y = Multiple 2 x : rest
7 | otherwise = Single x : Single y : rest
8 go x (Multiple n y : rest)
9 | x == y = Multiple (n + 1) y : rest
10 | otherwise = Single x : Multiple n y : rest
从右向左扫描，遇到相同元素就递增计数器，不同就插入新的 Single。
三种方法对比
| 方法 | 思路 | 特点 |
|---|---|---|
| 递归 + go | 手动维护计数器 | 逻辑显式，适合理解 |
span 版 | 自动切分连续段 | 最简洁 |
foldr 版 | 从右向左构建 | 巧妙但难读 |
测试
1>>> encodeDirect "aaaabccaadeeee"
2[Multiple 4 'a', Single 'b', Multiple 2 'c', Multiple 2 'a', Single 'd', Multiple 4 'e']
3
4>>> encodeDirect []
5[]
6
7>>> encodeDirect "a"
8[Single 'a']