这个 `init` 的实现是如何工作的？

Question

我正在学习 Haskell，我发现了一个有趣的init使用foldr. 但是，我很难理解它是如何工作的。

init' xs = foldr f (const []) xs id
    where f x g h = h $ g (x:)

考虑到我有一个输入[1,2,3]，那么就会变成

f 1 (f 2 ( f 3 (const []))) id

我将这些参数代入f其中h $ (const []) (1:)，最里面的一个就变成了，这很简单h []。但是，当我想进一步减少表达时，我发现很难掌握。下一个变成f 2 (h [])，即

h $ (h []) (2:)

如果它像那样工作。这对我来说看起来很混乱。要匹配 的类型foldr，h应该是 类型[a] -> [a]并且h []只是类型[a]，这不适用于(2:)。

我还以另一种方式考虑了它，即f x g返回一个 type 的函数([a] -> [a]) -> [a]，这在考虑id之后应用是有意义的。但后来我意识到我仍然不知道这h在这里做什么。看起来像是从上次h传送g (x:)到下一次应用程序。

当我考虑fold将函数用作累加器时，我是否错过了什么？

如果有人能帮我解决这个问题，我将不胜感激。

Answer 1

对于 list [1,2,3]，init'被替换为：

init' [1,2,3]
  = foldr f (const []) [1,2,3] id
  = f 1 (foldr f (const []) [2,3]) id

f因此这里用1as x、foldr f (const []) [2,3]asg和 来调用id h，这意味着 this 被解析为：

id (foldr f (const []) [2,3] (1:))

因此，这意味着id我们现在将1:在结果前面加上，而不是在递归中使用。接下来我们可以将内部解析foldr为：

foldr f (const []) [2,3] (1:)
 = f 2 (foldr f (const []) [3]) (1:)
 = (1:) (foldr f (const []) [3] (2:))

然后内部foldr结果为：

foldr f (const []) [3] (2:)
 = f 3 (foldr f (const []) []) (2:)
 = (2:) (foldr f (const []) [] (3:))

最终foldr f (const []) []将导致const [].

因此，这意味着：

foldr f (const []) [3] (2:)
 = f 3 (foldr f (const []) []) (2:)
 = (2:) (foldr f (const []) [] (3:))
 = (2:) (const [] (3:))

因此const将忽略参数(3:)，并返回一个空列表。所以结果foldr f (const []) [3] (2:)是[2]：

foldr f (const []) [3] (2:)
 = f 3 (foldr f (const []) []) (2:)
 = (2:) (foldr f (const []) [] (3:))
 = (2:) (const [] (3:))
 = (2:) []
 = [2]

如果我们在 中替换它foldr f (const []) [2,3] (1:)，我们得到：

foldr f (const []) [2,3] (1:)
 = f 2 (foldr f (const []) [3]) (1:)
 = (1:) (foldr f (const []) [3] (2:))
 = (1:) [2]
 = [1,2]

所以这意味着init' [1,2,3]将返回[1,2]。

这因此意味着一个

foldr f (const []) [x1, x2, …, xn] (x0:)

将被替换为：

(x0:) (foldr f (const []) [x2, x3, …, xn] (x1:))

如果列表耗尽，那么它将替换：

foldr f (const []) [] (xn:)

和：

const [] (xn:)

所以最后一个元素将被const函数忽略。