P09 - 将连续重复元素打包成子列表
Pack consecutive duplicates of list elements into sublists
官方模块:
Problems.P09核心函数:pack
题目描述
将列表中连续重复的元素打包成子列表。每个子列表包含一组连续相同的元素。
函数签名
1pack :: Eq a => [a] -> [[a]]
思路
维护一个当前正在构建的子列表（current group）。遍历输入列表：
- 如果当前元素和当前组的元素相同，加入当前组
- 如果不同，结束当前组，开始一个新组
在 Haskell 中可以用两种思路实现：
- 显式递归：手动维护当前组和已完成的组列表
- 高阶函数：用
span或groupBy抽象分组逻辑
实现
方法一：递归 + 累加器
1pack :: Eq a => [a] -> [[a]]
2pack [] = []
3pack (x:xs) = let (group, rest) = span (== x) xs
4 in (x : group) : pack rest
span (== x) xs 从 xs 头部开始，提取所有等于 x 的连续元素（返回两个部分：匹配的列表和剩余部分）。然后把 x 放在匹配列表前面，构成一组，再递归处理剩余部分。
方法二：使用 group（标准库）
1import Data.List (group)
2
3pack :: Eq a => [a] -> [[a]]
4pack = group
标准库 Data.List.group 做的就是这个事。但如果自己实现，用方法一或方法三。
方法三：显式递归（逐元素推进）
1pack :: Eq a => [a] -> [[a]]
2pack [] = []
3pack (x:xs) = go [x] xs
4 where
5 go current [] = [current]
6 go current@(c:_) (y:ys)
7 | c == y = go (y:current) ys
8 | otherwise = current : go [y] ys
用累加器 current 手动构建当前组。如果下一元素和当前组元素相同，加入组；否则结束当前组，开始新组。
注意：因为用
:前插，组内元素是逆序的，但group不要求组内元素有序，所以不影响。
如果需要保持组内顺序，可以用 go (current ++ [y]) ys 但效率低。更好的做法是最后 reverse 每个组。
理解 span
span :: (a -> Bool) -> [a] -> ([a], [a]) 在谓词首次不满足时切分列表：
1span (== 'a') "aaaabccaadeeee" → ("aaaa", "bccaadeeee")
这正是分组需要的操作：从当前元素开始，把所有连续相等的元素切出来。
示例过程
输入 "aaaabccaadeeee"：
1pack "aaaabccaadeeee"
2→ span (== 'a') "aaaabccaadeeee" = ("aaaa","bccaadeeee")
3→ "a" : "aaaa" = "aaaa" → ["aaaa"] ++ pack "bccaadeeee"
4
5pack "bccaadeeee"
6→ span (== 'b') "bccaadeeee" = ("b","ccaadeeee")
7→ ["b"] ++ pack "ccaadeeee"
8
9... 最终 → ["aaaa","b","cc","aa","d","eeee"]
测试
1>>> pack "aaaabccaadeeee"
2["aaaa","b","cc","aa","d","eeee"]
3
4>>> pack [1,1,2,2,2,3]
5[[1,1],[2,2,2],[3]]
6
7>>> pack []
8[]
9
10>>> pack "a"
11["a"]