这个 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 returns 一个 ([a] -> [a]) -> [a] 类型的函数，考虑到之后应用 id 有点有意义。但后来我意识到我仍然不知道这个 h 在这里做什么。看起来 h 将上次的 g (x:) 传送到下一个应用程序中。

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

如果有人能帮助我，我将不胜感激。

Answer 1

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

init' [1,2,3]
  = foldr f (const []) [1,2,3] id
  = <b>f</b> 1 (foldr f (const []) [2,3]) id

这里f因此被称为1为x，foldr f (const []) [2,3]为g和id h，这意味着这被解析为：

id <b>(foldr f (const []) [2,3] (1:))</b>

这意味着我们现在将 1: 添加到结果中，而不是在递归中使用 id 。接下来我们可以将内部的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:)
 = <b>f</b> 3 (foldr f (const []) []) (2:)
 = (2:) (foldr f (const []) [] (3:))
 = (2:) (const [] (3:))

const 将因此忽略参数 (3:) 和 return 一个空列表。所以 foldr f (const []) [3] (2:) 的结果是 [2]:

foldr f (const []) [3] (2:)
 = <b>f</b> 3 (foldr f (const []) []) (2:)
 = (2:) (foldr f (const []) [] (3:))
 = (2:) (const [] (3:))
 = <b>(2:)</b> []
 = [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:))
 = <b>(1:)</b> [2]
 = [1,2]

所以这意味着 init' [1,2,3] 将 return [1,2].

这意味着

foldr f (const []) [x<sub>1</sub>, x<sub>2</sub>, …, x<sub>n</sub>] (x<sub>0</sub>:)

将被替换为：

(x<sub>0</sub>:) (foldr f (const []) [x<sub>2</sub>, x<sub>3</sub>, …, x<sub>n</sub>] (x<sub>1</sub>:))

如果列表用完，它将替换：

foldr f (const []) [] (x<sub>n</sub>:)

与：

<b>const</b> [] (x<sub>n</sub>:)

因此最后一个元素将被 const 函数忽略。

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

How does this implementation of `init` work?

function

haskell

functional-programming

fold

accumulate