严格版本的foldl无限运行

Question

我无法理解为什么以下函数会导致无限循环:

import Data.List

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

Answer 1

双方foldl并foldl'在他们要经过整个列表,他们可以生产甚至部分结果之前,这样的方式定义(其实是没有办法去界定,使得不会是这种情况).所以既不适用于无限列表.

Answer 2

这些是普通的定义foldl和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？(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永远不会产生[].

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

使用严格foldl'意味着False && False术语会减少到恰好False,因此代码将在恒定的空间中运行.但它仍会继续,直到它看到一个[]永远不会到来的东西:

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是真正的递归,并且会在长列表中炸掉堆栈.

在哈斯克尔,由于懒惰,它通常是相反的方式,所以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)