P07 - 展平嵌套列表
Flatten a nested list structure
官方模块:
Problems.P07核心函数:flatten
题目描述
展平一个嵌套列表结构。需要自定义 NestedList 数据类型，可以是单个元素 Elem a 或子列表 List [NestedList a]。
函数签名
1flatten :: NestedList a -> [a]
NestedList 数据类型
要表示 “嵌套列表”，普通列表不够用——[a] 只能存储同一类型的元素，而嵌套列表在任意深度都可能是一个元素或一个子列表。
Haskell 的代数数据类型（ADT）正是解决这类问题的利器：
1data NestedList a
2 = Elem a
3 | List [NestedList a]
4 deriving (Show, Eq)
这定义了一个递归类型：
Elem a——一个普通元素（叶子节点）List [NestedList a]——一个子列表（内部节点），其元素可以是Elem或List
例如 List [Elem 1, List [Elem 2, List [Elem 3, Elem 4], Elem 5]] 表示 [1,[2,[3,4],5]]。
思路
递归遍历 NestedList：
Elem x→[x]（单个元素转成单元素列表）List xs→concatMap flatten xs（对每个子元素递归展平，然后拼接）
这正是 flatten 的语义：遇到叶子就包裹成列表，遇到内部节点就展平后合并。
实现
方法一：递归模式匹配
1flatten :: NestedList a -> [a]
2flatten (Elem x) = [x]
3flatten (List []) = []
4flatten (List (x:xs)) = flatten x ++ flatten (List xs)
这版写法最显式地展示了递归结构：
Elem x直接返回单元素列表List []空子列表返回空List (x:xs)展平第一个子元素，再拼上展平剩余部分
方法二：concatMap（更简洁）
1flatten :: NestedList a -> [a]
2flatten (Elem x) = [x]
3flatten (List xs) = concatMap flatten xs
concatMap flatten xs = concat (map flatten xs)，先对每个子元素 flatten，再把所有结果拼成一个列表。
方法三：纯 fold 风格
1flatten :: NestedList a -> [a]
2flatten (Elem x) = [x]
3flatten (List xs) = foldMap flatten xs
foldMap 来自 Data.Foldable，它用 Monoid 的 mappend（对列表就是 ++）来组合结果。这里 foldMap flatten xs 等价于 concatMap flatten xs。
理解 NestedList 的内存结构
1List [
2 Elem 1,
3 List [
4 Elem 2,
5 List [Elem 3, Elem 4],
6 Elem 5
7 ]
8]
可以看作树形结构：
1 List
2 / | \
3 1 List ...
4 / | \
5 2 List 5
6 / \
7 3 4
flatten 就是做了一次前序遍历，把所有叶子节点的值收集到列表中。
测试
1>>> flatten (Elem 5)
2[5]
3
4>>> flatten (List [Elem 1, List [Elem 2, List [Elem 3, Elem 4], Elem 5]])
5[1,2,3,4,5]
6
7>>> flatten (List [])
8[]
9
10>>> flatten (List [Elem 1, Elem 2, Elem 3])
11[1,2,3]
要点总结
- 递归 ADT 用递归函数处理：
NestedList是递归类型，flatten自然地也是递归函数 concatMap flatten xs是核心模式：遍历每个子元素，递归展平，合并结果——这种模式在后面树的问题中会反复出现- 这道题是理解 Haskell 自定义数据类型的绝佳起点，为后面二叉树、多路树打好基础