为什么有时可以从右侧对无限列表进行折叠？

Question

我一直在学习优秀的CIS 194课程，但在第六次作业的第五部分遇到了困难。它涉及实现标尺函数而不进行任何除法测试。

我发现可以通过不断地将累加器与无限列表中的值交错来构建标尺函数。

nats = [0,1,2,3,..]
[3]
[2,3,2]
[1,2,1,3,1,2,1]
[0,1,0,2,0,1,0,3,0,1,0,2,0]

然后我尝试将该算法实现到Stream数据类型上，它是一个没有nil的列表。

data Stream a = Cons a (Stream a)

streamToList :: Stream a -> [a]
streamToList (Cons x xs) = x : streamToList xs

instance Show a => Show (Stream a) where
  show = show . take 20 . streamToList

streamFromSeed :: (a -> a) -> a -> Stream a
streamFromSeed f x = Cons x (streamFromSeed f (f x))

nats :: Stream Integer
nats = streamFromSeed succ 0

interleave x (Cons y ys) = Cons x (Cons y (interleave x ys))
foldStream f (Cons x xs) = f x (foldStream f xs)
ruler = foldStream interleave nats

正如预期的那样，我因为尝试从右侧折叠而遇到了stackoverflow错误。然而，我惊讶地发现同样的算法适用于普通的无限列表。

import Data.List

interleave x list = [x] ++ (intersperse x list) ++ [x]
ruler = take 20 (foldr interleave [] [0..])

我错过了什么？为什么一个实现可行而另一个不行？

- ducaale

---

这个回答解决了你的问题吗？为什么在Haskell中foldr可以处理无限列表，但foldl不能？ - user14215102

foldr 并不是从右边折叠，而是从右边关联，即 foldr f z [1 .. 3] = 1 `f` (2 `f` (3 `f` z)) = f 1 $ f 2 $ f 3 $ z。如果 f 在第二个参数上是惰性的，它可以处理无限流并逐步产生结果。同样，懒惰的 foldl（而不是严格的 foldl'）对于在其第一个参数上懒惰的函数也是可以的。问题在于使用了错误的严格性——将在参数1中严格的函数给予 foldl 或在参数2中严格的函数给予 foldr——因此需要一直强制到流的末尾才能开始产生结果。对于无限流，没有这样的结尾。 - Jon Purdy

Answer 1

你的interleave不够懒惰。正确折叠无限结构的魔法是在执行第一段计算之前不要过于仔细地检查折叠值的结果。因此：

interleave x stream = Cons x $ case stream of
    Cons y ys -> Cons y (interleave x ys)

在检查stream之前，它会生成Cons x _; 相比之下，你的版本需要稍微评估一下stream，然后才能传递到等式的右侧，这实际上迫使整个折叠操作发生在任何构造函数被生成之前。

您可以在interleave的列表版本中看到这一点：

interleave x list = [x] ++ intersperse x list ++ [x]

返回结果： 返回的列表中的第一个元素（x）在 intersperse 开始对 list 进行匹配前就已知。

- Daniel Wagner

Answer 2

我们可以检查foldr [src]的源代码。一个更简洁的版本如下：

foldr f z [] = z
foldr f z (x:xs) = <b>f</b> x (foldr f z xs)

Haskell 不会急切地进行求值。这意味着，除非你需要 (foldr f z xs)，否则它不会对累加器进行求值。这也就意味着 f 不需要第二个参数。例如，如果第一个项目 x 有一个特定的值，它将不会对累加器进行求值。

例如，如果我们实现 takeWhileNeq：

takeWhileNeq a = foldr f []
    where f x xs -> if x == a then [] else (x:xs)

如果我们对列表takeWhileNeq 2 [1,4,2,5]运行此操作，那么它不会评估任何内容。但是，如果我们想要打印结果，它将评估为：

   f 1 (foldr f [4,2,5])

并且f会检查1 == 2，由于这不是真实情况，它将返回(x:xs)，所以：

-> 1 : foldr f [4,2,5]

现在它将评估4 == 2，因为这是假的，所以它将评估为：

-> 1 : (4 : foldr f [2,5])

现在我们评估 2 == 2，由于这是 True，这个函数返回空列表，并忽略累加器，因此它永远不会查看 foldr f [5]:

-> 1 : (4 : [])

对于一个无限列表，fold操作将导致结果为空列表，并忽略对列表的剩余部分进行折叠。

- Willem Van Onsem