首页 文章

为什么foldr在Haskell中的无限列表上工作但是foldl不工作？

提问于
浏览 次
3

我一直在努力理解Haskell中的 foldl vs foldr vs foldl' . 我理解，当 f 在其第二个参数中是懒惰时，共识是使用 foldr ，因为它反映了列表的结构 . 当我们知道整个列表需要处理并且 f 在其参数中是严格的时候， foldl' 会更好 .

我特别感兴趣的是这样的情况：

foldr (&&) False (repeat False)

返回 False .

但：

foldl (&&) False (repeat False)

永远不会完成

foldr 扩展为：

False && (False && (False && .... (False && *False*)) ... )

foldl ：

&& (... (&& (&& *False* False) False) ...) False

星星是 False 传入 fold 的基本案例 .

foldr 是否能够立即终止，因为LHS只是单个 False ，而 foldl 单个 False 一直在右边，并且它没有't '检查' that until it'已完成处理左侧？

haskell lazy-evaluation fold

1 回答

  • 7

    让我们看一下相关的定义（与Prelude中的定义不完全相同，但与此分析相同） .

    (&&) :: Bool -> Bool -> Bool
True && x = x
False && _ = False

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs

    看看每个 foldr 和 foldl 产生结果的机会 . 当给出 [] 时，它们都会立即产生结果 . 在 (x:xs) 情况下，如果 f 立即返回而没有评估其右参数（这是递归调用）， foldr 也有机会产生结果 . foldl 没有这个，因为它的最外面的调用是它自己的，所以 foldl 唯一可以提供任何信息的时间是在 [] 情况下，从来没有达到无限列表 .

    在这样的例子中，我发现做一些手动评估很有帮助 . 回想一下，Haskell的评估顺序是在外面进行的：我们尽可能少地评估最外层函数应用程序的适用模式匹配 . 我将在每个步骤中使用下一个要评估的函数 . foldr 很简单：

    foldr (&&) False (repeat False)
= foldr (&&) False (False : repeat False)
= False && foldr (&&) False (repeat False)
= False

    foldl 揭示了这个问题：

    foldl (&&) False (repeat False)
= foldl (&&) False (False : repeat False)
= foldl (&&) (False && False) (repeat False)
= foldl (&&) (False && False) (False : repeat False)
= foldl (&&) ((False && False) && False) (repeat False)
= foldl (&&) ((False && False) && False) (False : repeat False)
= foldl (&&) (((False && False) && False) && False) (repeat False)

    等等 . 请注意，即使 (&&) 能够通过检查任何一方来简化，我们仍然永远不会有机会返回它，因为我们从未达到 [] 情况 .

    但是， (&&) 评估其参数的顺序仍然很重要（它首先评估左边的一个，由模式匹配语义决定） . 我们可以 flip 参数的顺序，看看 foldr 的作用：

    ghci> foldr (flip (&&)) False (repeat False)
^CInterrupted

    （运动）这是为什么？

    回复于

相关问题