Haskell折叠剩余的无限列表不应用懒惰评估

Question

根据我的理解，Haskell 使用惰性求值，它允许在有限的时间内对例如无限列表的操作进行求值。

作为测试，我定义了以下函数

X Boolean
Y Int

f(X,Y) = (Y == 3) OR X

因此， fold left 应用于[1..]具有False初始值的无限整数列表和上面定义的函数，应该返回True，因为当它达到n=3评估时f(n==3,False)将返回True，因此这True将通过函数传播。

我在 Haskell 代码中实现了这个功能

myfunc :: Bool -> Int -> Bool
myfunc True _ = True
myfunc _ n
  | (n == 3)  = True
  | otherwise = False

并在 cli 中试用

foldl myfunc False [1..]

该命令变得无响应，表明它正在执行无限计算。为什么 Haskell 没有从这里的惰性求值中受益？

Answer 1

因为在开始将其归约为最终结果之前，foldl必须始终遍历其整个参数列表；并foldl'遍历整个参数列表，同时将其简化为最终结果：

foldl f z [x1, x2, ..., xn]  ==           foldl f (f z x1) [x2, ..., xn]

foldl' f z [x1, x2, ..., xn]  ==  z `seq` foldl' f (f z x1) [x2, ..., xn]

-- thus,

foldl f z1 [x1, x2, ..., xn]  ==  f (...(f (f z1 x1) x2)...) xn

foldl' f z1 [x1, x2, ..., xn]  ==  z1 `seq` (let z2 = f z1 x1  in
                                    z2 `seq` (let z3 = f z2 x2  in
                                     z3 `seq` (... `seq` (f zn xn)...))) 

您虽然希望能够停止遍历，这是通过带有非严格减少功能的右折叠完成的：

present y xs  =  foldr myfunc False xs 
  where
  myfunc x r  =  y == x || r 

由于myfunc是不严格的在第二个参数，foldr myfunc探讨名单xs中左到右的顺序，

foldr myfunc False (x:xs)  =  myfunc x (foldr myfunc False xs)
                           =  y == x || foldr myfunc False xs