P04 - 求列表长度
Length of a list
官方模块:
Problems.P04核心函数:myLength
题目描述
求列表的长度，即列表中元素的个数。
函数签名
1myLength :: [a] -> Int
注意这里返回 Int 而不是 Maybe Int——空列表的长度是 0，没有 “失败” 的情况。
思路
- 空列表
[]的长度是 0 - 非空列表
x:xs的长度是 1 +myLength xs
这是列表递归的经典入门模式。
实现
方法一：标准递归
1myLength :: [a] -> Int
2myLength [] = 0
3myLength (_:xs) = 1 + myLength xs
最直接的递归定义，可读性最好，但不是尾递归（需要压栈），对大列表可能栈溢出。
方法二：尾递归（累加器）
1myLength :: [a] -> Int
2myLength xs = go 0 xs
3 where
4 go acc [] = acc
5 go acc (_:xs) = go (acc + 1) xs
用累加器 acc 保存已计数的元素，每一步加 1，最后返回累加器。这是尾递归，GHC 会优化为循环，无栈溢出风险。
方法三：使用 foldl'
1import Data.List (foldl')
2
3myLength :: [a] -> Int
4myLength = foldl' (\acc _ -> acc + 1) 0
foldl' 是 Haskell 中实现尾递归折叠的标准工具，严格求值避免 thunk 堆积。
方法四：使用 sum + map
1myLength :: [a] -> Int
2myLength = sum . map (const 1)
把每个元素映射为 1，然后求和。思路巧妙但不是最高效的写法。
初学者常对 sum . map (const 1) 的解析感到困惑。我们像算术表达式一样逐步拆解。
第 1 步：列出所有运算符的优先级
| 符号 | 名称 | 优先级 | 结合性 |
|---|---|---|---|
| 空格 (函数应用) | application | 10 | 左结合 |
. | 函数组合 | 9 | 右结合 |
数字越大，绑定越紧。这就像算术中 × 优先级 3 > + 优先级 2。
第 2 步：按优先级逐层解析
1sum . map (const 1)
先找优先级最高的——函数应用（空格），优先级 10：
1sum . map (const 1)
2 ├──┬──┘ ← 函数应用: map 应用到 (const 1)
3 └── result ──── ← 得到一个函数: [a] -> [a]
map (const 1) 是一个完整的函数应用（就像 2 × 3），得到一个"把每个元素变成 1"的函数。
再找次高的——.，优先级 9：
1sum . (map (const 1))
2├──┘ ├──────┬──────┘ ← 函数组合: sum 和 map(const 1) 组合
3└────────── result ── ← 等价于 \xs -> sum (map (const 1) xs)
这就像算术 1 + 2 × 3 → × 优先级更高，所以解析为 1 + (2 × 3)。
同理，sum . map (const 1) → 函数应用优先级更高，所以解析为 sum . (map (const 1))。
第 3 步：如果去掉括号会怎样
1sum . map const 1
函数应用左结合，所以等价于：
1sum . ((map const) 1) ← 先把 map const 组合，再应用到 1
map const 的类型是 [b] -> [a -> a]，再应用到 1（不是列表）→ 类型错误。
记住关键原则：. 右侧如果要传参给函数，必须用括号把整个函数应用包起来。因为函数应用（空格）优先级 10 > . 优先级 9。
测试
1>>> myLength [123, 456, 789]
23
3
4>>> myLength "Hello, world!"
513
6
7>>> myLength []
80
9
10>>> myLength [1..1000]
111000
要点总结
- 三种风格：普通递归（直观）、尾递归 + 累加器（高效）、fold（Haskell 惯用）
- 对于
Int类型，超过maxBound :: Int的长度会溢出，但实际场景几乎不会遇到 foldl'的严格求值比foldl更适合累加场景