function - `init`的这种实现方式如何工作？

我正在学习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返回了([a] -> [a]) -> [a]类型的函数，考虑到之后再应用id，这有点有意义。但是后来我意识到我仍然不知道这个h在这里做什么。看来h将上次的g (x:)传达给了下一个应用程序。
当我考虑将fold与函数用作累加器时，是否错过了某些东西？
如果有人可以帮助我，我将非常感激。

最佳答案

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

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

因此，在这里f被称为1为x，foldr f (const []) [2,3]为g和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 []) [x, x, …, x] (x:)

将被替换为:

(x:) (foldr f (const []) [x, x, …, x] (x:))

如果列表用尽，它将替换:

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

和:

const [] (x:)

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

关于function - `init`的这种实现方式如何工作？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/63310382/