Haskell 上的 foldr1 和无限列表

ElB*_*ulP 6 haskell fold

阅读folds这本精彩的书时,我有一个问题foldr1以及head'那里提出的实现,有问题的代码是:

head' = foldr1 (\x _ -> x)
Run Code Online (Sandbox Code Playgroud)

此代码适用于无限列表,而不适用于foldl1。关于为什么是这个答案的一个很好的视觉解释。

我不太明白为什么它起作用,考虑到foldr1使用最后一个元素作为累加器。例如:

foldr1 (\x _ -> x) [1..]
Run Code Online (Sandbox Code Playgroud)

这是有效的,因为(我认为)懒惰评估,即使foldr是从列表的最后一个元素(无限)开始,我假设因为该函数没有使用任何中间结果,只返回第一个元素。

那么,编译器是否足够聪明知道,因为仅在 lambda 函数内部x被使用,只返回列表的第一个元素?即使它应该从最后开始?

相反,做

scanr1 (\x _ -> x) [1..]
Run Code Online (Sandbox Code Playgroud)

将打印无限列表的所有元素而不会结束,我想这就是它foldr正在做的事情,只是编译器足够聪明,不会评估它并返回头部。

提前致谢。

更新

我找到了一个非常好的答案,可以帮助我更深入地了解 foldr 的工作原理:

/sf/answers/4422437421/

Wil*_*ess 6

foldr1 使用的最后一个元素作为初始累加器值,但组合功能(\x _ -> x)是在其第二个参数懒惰。

因此,如果列表非空(更不用说无限),则永远不需要“累加器”值,因此永远不需要。

foldr并不意味着它应该从右侧开始,只是操作在右侧分组/关联/括号。如果组合函数在其第二个参数中是严格的,这将确实需要从右侧开始计算,但如果不是 - 则不是。

所以不,这不是关于编译器是否聪明,而是关于 Haskell 的惰性语义要求这样做。foldr被定义为

foldr g z [x1,x2,...,xn]  =  g x1 (foldr g z [x2,...,xn])
Run Code Online (Sandbox Code Playgroud)

foldr1 g xs  =  foldr g (last xs) (init xs)
Run Code Online (Sandbox Code Playgroud)

就是这样。

  • _`foldr` 并不意味着它应该从右侧“开始”,只是操作在右侧进行分组/关联/括号化。我喜欢这种明确性。 (3认同)