递归定义inits函数

Question

在 Data.List 模块中，有一个名为 inits 的函数，它可以将 [1,2,3,4] 转换为 [[],[1],[1,2],[1,2,3],[1,2,3,4]]。

我正在尝试使用递归定义类似的函数，但是我无法想出正确顺序的方法。我最接近的结果是列表倒序，即 result = [[],[4],[3,4],[2,3,4],[1,2,3,4]]:

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

我不确定如何通过逐个添加元素来按正确顺序创建列表？是否有人可以指点一下，或者这不可能通过递归完成？

- A.A

---

这个问题似乎涉及到一个高效的 inits 版本。 - RoadRunner

@WillNess，你成功地让我有点困惑，但是我相信你可能漏掉了一些东西。你最终会得到一个类似于(((a:) . (b:)) . (c:)) . (d:) $ []的元素。在揭示它的头之前，这需要重新关联。因此，如果你做类似于map headMay (inits xs)的事情，我预计你会遇到麻烦。 - dfeuer

另一方面，我忘记了最优解的简单方法（大O表示法，但常数因子中等）：使用“take”。但这可能对于这个问题来说不够“递归”。 - dfeuer

@dfeuer 根据您的要求，重新关联的复杂度也是*O(i)*（其中i是原始列表中的索引）。实际上，运行 head $ (map ($[]) . scanl (\a x-> a . (x:)) id) [1..] !! 300000，然后再运行 3000000，运行时间比为10.0。（参见此处） - Will Ness

@dfeuer 当然会是二次的，没错。map headMay $ zipWith (\_ i -> take i xs) xs [0..] 不会，确实不错。很好。 - Will Ness

Answer 1

对于这样一个函数，最简单的尝试就是只看所期望的结果，并在函数方程的右手边进行“逆模式匹配”。

你已经具备了这个能力。

inits' [] = [[]]

现在有 inits (x:xs)，例如 inits (1:[2,3,4])，你应该知道结果应该是 [[],[1],[1,2],[1,2,3],[1,2,3,4]]，它匹配了模式 []:_。因此

inits' (x:xs) = [] : _

现在，最简单的递归方式就是直接在xs上再次调用inits'，如下所示：

inits' (x:xs) = [] : inits' xs

然而，这并不能得出正确的结果：假设递归调用已经正确执行，你会得到

inits' (1:[2,3,4]) = [] : [[],[2],[2,3],[2,3,4]]
                   = [[],[],[2],[2,3],[2,3,4]]

很明显，1完全缺失，因为我们在定义中实际上没有使用它。我们需要使用它，实际上应该在递归结果中的所有列表块之前添加它。您可以使用 map 实现这一点。

- leftaroundabout

Answer 2

我们可以将所有剩余的inits数据都添加到前面，例如：

inits' :: [a] -> [[a]]
inits' [] = [[]]
inits' (x:xs) = [] : <b>map (x:) (</b>inits' xs<b>)</b>

作为基本情况，当输入为空列表时，我们返回一个包含空列表的单例列表。

在递归情况下，我们首先生成空列表，然后是列表尾部的inits'，但所有这些元素都被x前置（使用map (x:)）。

然后我们有：

Prelude> inits' [1,4,2,5]
[[],[1],[1,4],[1,4,2],[1,4,2,5]]

鉴于以下原因(非按照评估顺序排列):

   inits' [1,4,2,5]
-> [] : map (1:) (inits' [4,2,5])
-> [] : map (1:) ([] : map (4:) (inits' [2,5]))
-> [] : map (1:) ([] : map (4:) ([] : map (2:) (inits' [5])))
-> [] : map (1:) ([] : map (4:) ([] : map (2:) ([] : map (5:) (inits' []))))
-> [] : map (1:) ([] : map (4:) ([] : map (2:) ([] : map (5:) [[]])))
-> [] : map (1:) ([] : map (4:) ([] : map (2:) ([] : [[5]])))
-> [] : map (1:) ([] : map (4:) ([] : map (2:) [[],[5]]))
-> [] : map (1:) ([] : map (4:) ([] : [[2],[2,5]]))
-> [] : map (1:) ([] : map (4:) [[],[2],[2,5]])
-> [] : map (1:) ([] : [[4],[4,2],[4,2,5]])
-> [] : map (1:) [[],[4],[4,2],[4,2,5]]
-> [] : [[1],[1,4],[1,4,2],[1,4,2,5]]
-> [[],[1],[1,4],[1,4,2],[1,4,2,5]]

- Willem Van Onsem

---

这个定义看起来与 ghc 7.8.3 中的那个 "令人恐惧的低效" 完全相同（http://hackage.haskell.org/package/base-4.7.0.1/docs/src/Data-List.html#inits）。在 ghci 提示符下进行快速测试 head $ inits' [1..] !! n，解释后，实际上显示了 ~n^2 的经验增长率。 - Will Ness

Answer 3

我认为你应该将函数定义更改为：

inits' :: [Int] -> [[Int]]

to:

inits' :: [a] -> [[a]]

由于来自Data.List的inits的类型是[a] -> [[a]]，它并不关心列表中实际包含的内容。它需要是多态的，并接受任何类型的列表。

此外，既然其他人已经展示了最简单的递归方法，你也可以在这里使用foldr。

以下是基本代码：

inits' :: [a] -> [[a]]
inits' = foldr (\x acc -> [] : (map (x:) acc)) [[]]

当[[]]是基本情况时，与您的函数类似。对于实际的递归部分，以下是使用调用inits' [1, 2, 3, 4]的工作方式：

• 从右侧开始折叠值4，并创建[[], [4]]
• 现在在值3上，并创建[[], [3], [3, 4]
• 现在在值2上，并创建[[], [2], [2, 3], [2, 3, 4]]
• 现在在值1上，并创建[[], [1], [1, 2], [1, 2, 3], [1, 2, 3, 4]]

这将给出所需的最终嵌套列表，类似于函数调用：

*Main> inits' [1,2,3,4]
[[],[1],[1,2],[1,2,3],[1,2,3,4]]

从上述描述的行为中，你只需要关注[] : (map (x:) acc)，在这里你将当前值x映射到累加列表acc中，同时在每次折叠时在其前面添加一个空列表。

如果你仍然难以理解foldr，你可以看一下这个最简化的例子，展示了从右侧进行折叠的过程:

foldr f x [a, b, c] = a `f` (b `f` (c `f` x))

以及foldr如何工作？

（关于IT技术）

- RoadRunner