haskell - Haskell 中的自引用函数 (interleaveStreams)

Question

我的代码导致了某种无限递归，因此我决定仔细阅读这篇文章(OP 正在做与我相同的问题:在无限流上实现标尺函数):

Implementing the ruler function using `streamInterleave`

我的代码如下所示:

data Stream a = Cons a (Stream a)

streamRepeat :: a -> Stream a
streamRepeat x = Cons x (streamRepeat x)

interleaveStreams :: Stream a -> Stream a -> Stream a
interleaveStreams (Cons x xs) (Cons y ys) = Cons x (Cons y (streamInterleave xs ys))

ruler :: Stream Integer
ruler = interleaveStreams (streamRepeat 0) (streamMap (+1) $ ruler)

现在，事实证明，如果我将 interleaveStreams 的定义更改为

interleaveStreams :: Stream a -> Stream a -> Stream a
interleaveStreams (Cons x xs) ys = Cons x (interleaveStreams ys xs)

并保持其他一切不变，没有无限递归并且它可以正常工作。据我所知，interleaveStreams 的两个版本是等效的。为什么其中一个挂起，而另一个正常工作？

Answer 1

假设您只需要Cons x (Cons y (streamInterleave xs ys)) 的头部。 interleaveStreams 的挂起实现仍然表示它需要匹配 Cons x xs 和 Cons y ys 才能做到这一点。当与 Cons y ys 匹配的值是 x 的函数时，这足以破坏您可能希望有效的某些操作。

这就是ruler = interleaveStreams (streamRepeat 0) (streamMap (+1) $ruler)的情况!为了简单起见，streamMap 不会对此进行任何更改:

ruler = interleaveStreams (streamRepeat 0) ruler

并忽略streamRepeat:

interleaveStreams (Cons y ys) = Cons 0 (Cons y (streamInterleave xs ys))
ruler = interleaveStreams ruler

你可以明白为什么 Haskell 无法弄清楚 y 是什么了。

另一种选择是使用惰性模式:

interleaveStreams (Cons x xs) ~(Cons y ys) = Cons x (Cons y (streamInterleave xs ys))

或者你可以给ruler一个先机:

ruler = Cons 0 (interleaveStreams (streamMap (+1) ruler) (streamRepeat 0))