P05 - 反转列表
Reverse a list
官方模块:
Problems.P05核心函数:myReverse
题目描述
反转列表，将列表中的元素顺序颠倒。
函数签名
1myReverse :: [a] -> [a]
思路
- 空列表反转后还是空列表
- 非空列表
x:xs反转 =reverse xs ++ [x]
这个递归定义很直观，但用 ++ 拼接的效率不高（O(n²)）。更好的方法是尾递归 + 累加器，逐个把元素往前插。
实现
方法一：递归 + ++
1myReverse :: [a] -> [a]
2myReverse [] = []
3myReverse (x:xs) = myReverse xs ++ [x]
最直接的递归，但效率很差——总复杂度 O(n²)。小列表没问题，大列表不推荐。
为什么是 O(n²)？
++ 运算符的代价是 O(左列表长度)，因为它要遍历整个左列表，把每个 cons 单元 (:) 重新指向右列表的头部：
1-- (++) 的定义
2[] ++ ys = ys
3(x:xs) ++ ys = x : (xs ++ ys)
所以 myReverse [1,2,3] 的求值过程是：
1myReverse [1,2,3]
2→ myReverse [2,3] ++ [1] -- ++ 遍历左侧 0 次，递归准备
3→ (myReverse [3] ++ [2]) ++ [1] -- ++ 遍历左侧 0 次，递归准备
4→ ((myReverse [] ++ [3]) ++ [2]) ++ [1] -- ++ 遍历左侧 0 次
5→ (([3]) ++ [2]) ++ [1] -- [3] ++ [2] 遍历 1 个元素
6→ (3 : ([] ++ [2])) ++ [1] -- 继续遍历...
7→ [3,2] ++ [1] -- [3,2] ++ [1] 遍历 2 个元素
8→ 3 : ([2] ++ [1]) -- 继续遍历...
9→ 3 : 2 : ([] ++ [1])
10→ [3,2,1]
在递归的每一层，当前的左列表长度都在增长：
| 层级 | ++ 左列表长度 | 遍历次数 |
|---|---|---|
| 第 1 层 | 0 ([]) | 0 |
| 第 2 层 | 1 ([3]) | 1 |
| 第 3 层 | 2 ([3,2]) | 2 |
| … | … | … |
| 第 n 层 | n-1 | n-1 |
总遍历次数 = 0 + 1 + 2 + … + (n-1) = n(n-1)/2 = O(n²)
相比之下，尾递归版本（方法二）每步只做一次 : 操作（O(1)），总复杂度 O(n)。
方法二：尾递归（推荐）
1myReverse :: [a] -> [a]
2myReverse xs = go [] xs
3 where
4 go acc [] = acc
5 go acc (x:xs) = go (x:acc) xs
核心思路：遍历原列表，每遇到一个元素就把它放到累加器的最前面（x:acc），当原列表遍历完时，累加器正好是反转结果。
这个实现复杂度 O(n)，是生产环境的标准做法。
方法三：使用 foldl
1myReverse :: [a] -> [a]
2myReverse = foldl (\acc x -> x : acc) []
foldl 从左到右遍历列表，每次把当前元素 x 插到累计结果 acc 的前面。和方法二的本质完全一样，只是更简洁。
方法四：使用 reverse 标准库
1import Prelude hiding (reverse)
2
3myReverse :: [a] -> [a]
4myReverse = reverse
如果只是想完成任务而不是练习，标准库 reverse（在 GHC.List 中）就是尾递归实现的。
如何理解尾递归反转
假设输入 [1,2,3]：
1go [] [1,2,3]
2→ go (1:[]) [2,3] -- acc = [1]
3→ go (2:1:[]) [3] -- acc = [2,1]
4→ go (3:2:1:[]) [] -- acc = [3,2,1]
5→ [3,2,1] -- 返回 acc
每步都把当前元素前插到累加器，相当于用 : 构造了逆序列表。
测试
1>>> myReverse "A man, a plan, a canal, panama!"
2"!amanap ,lanac a ,nalp a ,nam A"
3
4>>> myReverse [1,2,3,4]
5[4,3,2,1]
6
7>>> myReverse []
8[]
9
10>>> myReverse [1]
11[1]