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

Question

当我被困在家庭作业 6 的第 5 部分时，我一直在学习优秀的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

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]

正如预期的那样，由于我试图从右侧折叠，因此出现了 stackoverflow 错误。然而，我很惊讶地看到相同的算法适用于普通的无限列表。

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

我错过了什么？为什么一种实现有效而另一种则无效？

Answer 1

你interleave不够懒。右折叠必须在无限结构上做的神奇事情是在进行第一次计算之前不要太仔细地检查折叠值的结果。所以：

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

这Cons x _在检查前产生stream；相比之下，您的版本需要stream在它传递到等式的右侧之前进行一些评估，这实际上强制整个折叠在生成任何构造函数之前发生。

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

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

返回的列表 ( x)的第一个元素在intersperse开始模式匹配之前是已知的list。

Answer 2

我们可以检查foldr[src]的源代码。噪声较小的版本如下所示：

foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)

哈斯克尔并没有急切地评估。因此，这意味着，除非您需要 ，否则(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 : [])

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