如何用递归实现Data.List模块中inits函数的正确顺序？

嘿，这个问题很典型，递归完全可以实现正确顺序的inits函数，咱们先看看你现有代码的问题，再给出正确的写法～

你的代码为什么得到逆序结果？ #

你当前的代码：

inits' :: [Int] -> [[Int]]
inits' [] = [[]]
inits' (x:xs) = inits' xs ++ [(x:xs)]

问题出在递归的构建方向上：你先递归处理了xs（也就是列表的尾部），得到的是尾部的所有后缀式前缀（比如处理[1,2,3,4]时，先得到[2,3,4]的结果[[],[4],[3,4],[2,3,4]]），然后把整个x:xs加在后面，相当于从后往前拼接前缀，自然得到逆序的结果。

正确的递归实现方案 #

方案1：直接构建正序前缀 #

我们换个思路：当处理x:xs时，xs的所有前缀已经是[[], [x2], [x2,x3], ...]，那么给每个前缀前面加上x，就能得到以x开头的所有前缀[[x], [x,x2], [x,x2,x3], ...]，再把空列表放在最前面，就凑齐了所有前缀：

inits' :: [Int] -> [[Int]]
inits' [] = [[]]
inits' (x:xs) = [] : map (x:) (inits' xs)

测试inits' [1,2,3,4]，结果就是[[],[1],[1,2],[1,2,3],[1,2,3,4]]，完全符合预期。

方案2：用累加器逐步构建 #

如果你更倾向于“逐个添加元素”的直观过程，可以用累加器来跟踪当前已构建的前缀，最后反转得到正序结果：

inits' :: [Int] -> [[Int]]
inits' = reverse . go [[]]
  where
    go acc [] = acc
    go acc (x:xs) = go ( (x : head acc) : acc ) xs

这个思路的步骤是：

• 初始累加器acc是[[]]（只有空前缀）
• 每处理一个元素x，就把x加到当前累加器的第一个元素（最近构建的前缀）前面，形成新前缀，再把这个新前缀加到累加器头部
• 处理完所有元素后，累加器里的前缀是逆序的，反转一下就得到正序结果

比如处理[1,2,3]：

1. 初始acc = [[]]
2. 处理1：新前缀是1:[] = [1]，acc变为[[1], []]
3. 处理2：新前缀是2:[1] = [2,1]，acc变为[[2,1], [1], []]
4. 处理3：新前缀是3:[2,1] = [3,2,1]，acc变为[[3,2,1], [2,1], [1], []]
5. 反转后得到[[], [1], [1,2], [1,2,3]]

总结 #

递归完全可以实现符合要求的inits函数，关键是调整递归的构建方向——要么从前往后生成前缀，要么用累加器跟踪后反转。

内容的提问来源于stack exchange，提问作者A.A