haskell - 为什么foldright适用于无限列表？

Question

我的印象是 foldright 从列表末尾开始向后工作(这就是我想象的右关联的含义)。所以我很困惑以下内容适用于无限列表。

我有一个函数find:

find :: (a -> Bool) -> List a -> Optional a
find p = foldRight (\c a -> if p c then Full c else a) Empty

注意以下工作:

>> find (const True) infinity
Full 0

我做了一些搜索并发现了这篇文章:How do you know when to use fold-left and when to use fold-right?

不幸的是，接受的答案并不是特别有用，因为右关联运算的示例是:

A x (B x (C x D))

这仍然意味着它需要首先执行最右边的事情。

我想知道是否有人可以帮我解决这个问题，谢谢。

Answer 1

让我们从一个函数开始:

>>> let check x y = if x > 10 then x else y
>>> check 100 5
100
>>> check 0 5
5

check 接受两个参数，但可能不使用第二个参数。由于 haskell 是惰性的，这意味着第二个参数可能永远不会被计算:

>>> check 20 (error "fire the missles!")
20

这种懒惰让我们跳过了可能无限的工作量:

>>> check 30 (sum [1..])
30

现在让我们使用等式推理逐步完成 foldr check 0 [0..]:

foldr check 0 [0..]
= check 0 (foldr check 0 [1..]) -- by def'n of foldr
= foldr check 0 [1..] -- by def'n of check
= check 1 (foldr check 0 [2..]) -- by def'n of foldr
= foldr check 0 [2..] -- by def'n of check
-- ...
= foldr check 0 [10..]
= check 10 (foldr check 0 [11..]) -- by def'n of foldr
= foldr check 0 [11..] -- by def'n of check
= check 11 (foldr check 0 [12..]) -- by def'n of foldr
= 11 -- by def'n of check

请注意，惰性如何迫使我们从上到下进行评估，看看最外层函数调用如何(以及是否)使用其参数，而不是从下到上(在将所有参数传递给函数之前评估所有参数) ，就像严格的语言一样。