为何在某些情况下能从右侧折叠无限列表？

在我完成CIS 194课程的家庭作业6的第5部分时，遇到了一个有趣的问题。该课程要求我们在不使用可分性测试的情况下实现一个标尺函数。我发现在构建这个函数时，可以通过连续将无限列表中的值插入累加器来实现这一目标。

例如，通过以下步骤构建标尺函数：

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

这让我感到困惑，为什么一种实现有效而另一种则导致错误？

解答一

问题在于你的interleave函数不够懒惰。在无限结构上进行右折叠的关键是，在执行首次计算之前不应过度检查折叠值的结果。因此，可以修改interleave函数如下：

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

这样可以在检查stream之前就产生Cons x _；而你原来的版本在传递给等式右侧之前需要对stream进行一些评估，实际上迫使整个折叠在生成任何构造器之前完成。

解答二

我们可以查看foldr的源码来理解这个问题。简化后的版本如下：

foldr f z [] = z
foldr f z (x:xs) = f 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])
- (1 == 2) -> False -> 1 : foldr f [4,2,5]
- (4 == 2) -> False -> 1 : (4 : foldr f [2,5])
- (2 == 2) -> True -> 1 : (4 : [])

对于无限列表，一旦遇到终止条件，它就会立即停止评估，从而避免了无限循环或栈溢出的问题。