为什么有时可以从右边折叠无限列表？

Question

我一直在经历优秀的CIS 194 course when I got stuck on Part 5 of Homework 6. It revolves around implementing the ruler function，没有任何可分性测试。

我发现可以通过用无限列表中的值连续散布累加器来构建标尺函数。

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

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

import Data.List

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

我错过了什么？为什么一个实施有效而另一个实施无效？

Answer 1

我们可以查看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，因为不是这种情况，它将 return (x:xs)，所以：

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

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

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

现在我们计算 2 == 2，因为这是 True，函数 returns 是空列表，ingores 是累加器, 所以它永远不会看 foldr f [5]:

-> 1 : (4 : [])

对于无限列表，它也会因此产生一个空列表并忽略折叠列表的其余部分。

Answer 2

你的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 上开始模式匹配之前已知。

为什么有时可以从右边折叠无限列表？

Why is it sometimes possible to fold an infinite list from the right?

haskell

lazy-evaluation