阅读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 的工作原理:
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)
就是这样。