0

据我了解，由于 Haskell 使用惰性求值，它允许在有限的时间内对无限列表等操作进行求值。

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

X Boolean
Y Int

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

因此，左折叠应用于[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 没有从这里的惰性评估中受益？

4

1 回答 1

6

因为在开始将其归约为最终结果之前，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
于 2020-01-13T15:29:00.113 回答