P11 - 改进的游程编码
Modified run-length encoding
官方模块:
Problems.P11核心函数:encodeModified
题目描述
修改 P10 的 encode 函数——如果元素没有重复，直接以 Single 形式放入结果列表；只有重复的元素才编码为 Multiple n x。
输出类型不再是 [(Int, a)]，而是自定义的 Encoding a 类型。
Encoding 数据类型
1data Encoding a
2 = Single a -- 只出现一次的元素
3 | Multiple Int a -- 出现 n 次的元素
4 deriving (Show, Eq)
函数签名
1encodeModified :: Eq a => [a] -> [Encoding a]
思路
基于 P09 的 pack（或 P10 的 encode），对每一组连续重复元素：
- 如果长度为 1 →
Single x - 如果长度 > 1 →
Multiple n x
实现
方法一：基于 pack
1import Data.List (group)
2
3encodeModified :: Eq a => [a] -> [Encoding a]
4encodeModified = map encodeGroup . group
5 where
6 encodeGroup [x] = Single x
7 encodeGroup xs = Multiple (length xs) (head xs)
group 把连续重复元素打包成子列表，然后根据子列表长度选择 Single 或 Multiple。
方法二：基于 P10 的 encode
1encodeModified :: Eq a => [a] -> [Encoding a]
2encodeModified = map convert . encode
3 where
4 convert (1, x) = Single x
5 convert (n, x) = Multiple n x
先做 P10 的标准编码，再把 (1, x) 转为 Single x。
方法三：手动递归
1encodeModified :: Eq a => [a] -> [Encoding a]
2encodeModified [] = []
3encodeModified (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) : encodeModified rest
span (== x) xs 切分出与 x 相等的连续段，根据长度直接构造 Encoding。
测试
1>>> encodeModified "aaaabccaadeeee"
2[Multiple 4 'a', Single 'b', Multiple 2 'c', Multiple 2 'a', Single 'd', Multiple 4 'e']
3
4>>> encodeModified []
5[]
6
7>>> encodeModified "a"
8[Single 'a']