P12 - 解码游程编码
Decode a run-length encoded list
官方模块:
Problems.P12核心函数:decodeModified
← P11 改进的游程编码 | P13 直接实现游程编码 →
题目描述
将 P11 生成的 Encoding 编码列表解码，还原为原始列表。Single x 展开为单个 x，Multiple n x 展开为 n 个 x。
函数签名
1decodeModified :: [Encoding a] -> [a]
思路
遍历编码列表，对每个编码：
Single x→[x]Multiple n x→replicate n x
然后用 concat 把所有结果拼接起来。
实现
方法一：concatMap
1decodeModified :: [Encoding a] -> [a]
2decodeModified = concatMap expand
3 where
4 expand (Single x) = [x]
5 expand (Multiple n x) = replicate n x
最直接的实现，concatMap 遍历并展平。
方法二：列表推导
1decodeModified :: [Encoding a] -> [a]
2decodeModified [] = []
3decodeModified (Single x : rest) = x : decodeModified rest
4decodeModified (Multiple n x : rest) = replicate n x ++ decodeModified rest
显式递归，逐个处理编码。
方法三：使用 foldr
1decodeModified :: [Encoding a] -> [a]
2decodeModified = foldr expand []
3 where
4 expand (Single x) acc = x : acc
5 expand (Multiple n x) acc = replicate n x ++ acc
为什么叫"改进的"编码？
对比 P10 的标准编码 [(Int, a)] 和 P11 的改进编码 [Encoding a]：
1P10: [(4,'a'), (1,'b'), (2,'c'), (2,'a'), (1,'d'), (4,'e')]
2P11: [Multiple 4 'a', Single 'b', Multiple 2 'c', Multiple 2 'a', Single 'd', Multiple 4 'e']
改进之处在于用类型系统表达语义——Single 明确表示"只有一个"，比 (1, 'a') 更自解释。
测试
1>>> decodeModified [Multiple 4 'a', Single 'b', Multiple 2 'c', Multiple 2 'a', Single 'd', Multiple 4 'e']
2"aaaabccaadeeee"
3
4>>> decodeModified []
5[]
6
7>>> decodeModified [Single 'x']
8"x"