1

我不明白为什么以下函数会导致无限循环：

import Data.List

isTrue = foldl' (&&) False (repeat False)
4

2 回答 2

13

两者foldl和foldl'都以这样一种方式定义，即它们必须遍历整个列表才能产生甚至是部分结果（事实上，没有办法定义它们，以免出现这种情况）。所以两者都不适用于无限列表。

于 2013-03-10T19:56:28.567 回答
5

这些是 plainfoldl和的定义repeat：

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

repeat :: a -> [a]
repeat a = a : repeat a

现在，当我们尝试您的定义时会发生什么isTrue？（当然，适应了 lazy foldl，但这与您的问题相同。）

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

现在是关键时刻。评估如何从这里继续？嗯，这是一个foldlthunk，所以我们必须弄清楚要使用两个 foldl 方程中的哪一个——一个有[]模式的，或者一个有x:xs. 这意味着我们必须强制repeat False查看它是一个空列表还是一对：

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

...它会继续这样做。基本上，foldl只能在遇到 a 时终止[]，并且repeat永远不会产生 a []。

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

使用 strictfoldl'意味着这些False && False术语被简化为 just False，因此代码将在恒定空间中运行。但它仍然会继续，直到它看到 a []，它永远不会出现：

foldl' f z [] = z
foldl' f z (x:xs) = 
    let z' = f z x 
    in z' `seq` foldl' f z' xs

foldl' (&&) False (repeat False)
    == foldl' (&&) False (False : repeat False)
    == let z' = False && False in z' `seq` foldl' (&&) z' (repeat False)

       -- We reduce the seq by forcing z' and substituting its result into the 
       -- its second argument.  Which takes us right back to where we started...
    == foldl' (&&) False (repeat False)
    ...

这些函数没有任何智能让他们看到累加器永远不会是False. 对两者的工作foldl'方式一无所知。它所知道的只是列表，它只会在一个空列表上结束。(&&)repeat False

对于来自严格语言的人来说，关于 Haskell 的一个棘手的事情是，他们已经了解到，在这种语言中，左折叠比右折叠“更好”，因为左折叠是尾递归的，因此在恒定空间中运行，而右折叠folds 是真正的递归，并且会在长列表中破坏堆栈。

在 Haskell 中，由于懒惰，它通常是相反的，所以foldl和foldl'是糟糕的，而foldr' 是“好”的。例如，以下将终止：

foldr (&&) False (repeat False)

为什么？这是 的定义foldr：

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

比较这里的第二个等式和foldl; foldl'是尾递归的，而foldr尾调用f并将递归foldr调用作为参数传递。这意味着f可以选择是否以及何时向下递归foldr; 如果f在其第二个参数上是惰性的，则递归将延迟到需要其结果为止。如果f丢弃它的第二个参数，那么我们永远不会递归。

因此，应用于我的示例：

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

我们完成了！但请注意，这只有效，因为(&&)它的第一个参数是严格的，如果第一个参数是 ，则丢弃它的第二个参数False。以下变体进入无限循环：

foldr (flip (&&)) False (repeat False)
于 2013-03-10T22:54:39.703 回答