P08 - 去除连续重复元素
Eliminate consecutive duplicates of list elements
官方模块:
Problems.P08核心函数:compress
← P07 展平嵌套列表 | P09 将连续重复元素打包成子列表 →
← P07 展平嵌套列表 | P09 将连续重复元素打包成子列表 →
题目描述
去除列表中连续重复的元素，每组连续相同元素只保留一个。元素的相对顺序不变。
函数签名
1compress :: Eq a => [a] -> [a]
需要 Eq a 约束来比较元素是否相等。
思路
遍历列表，只保留与前一个元素不同的那些元素。即：
- 空列表 →
[] - 单元素 → 原样保留
x : y : xs：- 如果
x == y，跳过y，继续检查x和xs的头部 - 如果
x /= y，保留x，递归处理y : xs
- 如果
实现
方法一：模式匹配 + 递归
1compress :: Eq a => [a] -> [a]
2compress [] = []
3compress [x] = [x]
4compress (x:y:xs)
5 | x == y = compress (x:xs)
6 | otherwise = x : compress (y:xs)
最直接的递归版本。[x] 模式处理单元素列表（避免不必要的对比），双元素 (x:y:xs) 模式决定去重还是保留。
方法二：使用 map + group
1import Data.List (group)
2
3compress :: Eq a => [a] -> [a]
4compress = map head . group
group 把连续重复元素打包成子列表（"aaaabccaadeeee" → ["aaaa","b","cc","aa","d","eeee"]），map head 取每个子列表的第一个元素。
这是一个经典的 Haskell 单行惯用法。
方法三：使用 foldr
1compress :: Eq a => [a] -> [a]
2compress = foldr go []
3 where
4 go x [] = [x]
5 go x acc
6 | x == head acc = acc
7 | otherwise = x : acc
从右向左 fold，如果当前元素等于已积累结果的头部，就跳过它。
理解 group 的工作方式
Data.List.group 是 P09 要解决的问题。但在 P08 中我们可以用它来简化实现：
1输入: "aaaabccaadeeee"
2group: ["aaaa","b","cc","aa","d","eeee"]
3map head: "abcade"
每一组连续重复元素被压成一个单元素，恰好完成去重。
测试
1>>> compress "aaaabccaadeeee"
2"abcade"
3
4>>> compress [1,1,2,2,3,3,3,1,1]
5[1,2,3,1]
6
7>>> compress []
8[]
9
10>>> compress "a"
11"a"
注意最后的
1不会被去掉，因为compress只去连续重复，而这两个1被2,3隔开了。