无限列表上的foldl行为

Question

关于在列表上使用foldl和foldr，我的理解如下：

如果我们使用函数s和一个起始累加器a从右侧对[0,1,2,3] 进行折叠，那么我们正在执行以下操作：

f 0 (f 1 (f 2 (f 3 a)))

如果我们使用函数s和一个起始累加器a从左侧对[0,1,2,3] 进行折叠，那么我们正在执行以下操作：

f (f (f (f 0 a) 1) 2) 3)

---

给定:

elem_r :: (Eq a) => a -> [a] -> Bool
elem_r y ys = foldr (\x acc -> if x == y then True else acc) False ys

并且

elem_l :: (Eq a) => a -> [a] -> Bool
elem_l y ys = foldl (\acc x -> if x == y then True else acc) False ys

我认为elem_r 3 [0..]会计算出它必须的内容，一旦值3被找到就会立即返回True。

f 0 (f 1 (f 2 (f 3 (...)))

而elem_l 3 [0..]需要在返回结果之前评估完整个嵌套函数应用。

f (f (f (f (f 0 3) 1) 2) 3) ...)

---

现在我的问题是：

在特定情况下的elem_l 0 [0..] 所寻找的元素是列表的第一个项目。

在这个表达式中: f (f (f (f (f 0 0) 1) 2) 3) ...) 最内部的函数(f 0 0)可以立即评估为“真”。 Haskell为什么还要继续评估其余嵌套函数？

- espern

---

如果 x == y，则 True，否则 acc 的代码可以更简洁一些，我的看法是 acc || x == y。 - Bartek Banachewicz

推荐阅读：https://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl' - jub0bs

@BartekBanachewicz 你肯定是想说 x == y || acc。 - Will Ness

Answer 1

即使你立即将f 0 0减少为True，也没有帮助。你仍然有所有周围的f出现要减少...

- kosmikus

Answer 2

因为f(f(f(f(f 0 0)1)2)3)...)是不正确的。最后一个括号和第一个f不匹配，而且初始参数也都是错误的。它确实是这样。

(f ... (f (f (f (f False 0) 1) 2) 3) ...)

所以在foldl完成构建这个表达式后（也就是永远不会完成），我们必须先评估这无限嵌套的表达式中的它们，然后才能到达最里面的表达式，最后评估它（因为f在0处停止）。或者在这种情况下，从未评估。

而另一个测试，在搜索3时，会更早地停止在(f (f (f (f False 0) 1) 2) 3)上，因为现在f在3处停止；但仍然需要在构建无限嵌套表达式之后，先通过无限嵌套的表达式。

- Will Ness