无法定义无限流

Question

我正在研究UPENN Haskell家庭作业6练习5，试图定义一个ruler function

0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,...

其中，流中的第n个元素(假设第一个元素对应于n = 1)是均分n的最大power of 2。

我只是想出了一个不需要任何可分性测试就构建它的想法：

data Stream x = Cons x (Stream x) deriving (Eq)

streamRepeat x = Cons x (streamRepeat x)

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

ruler =
    interleaveStreams (streamRepeat 0)
        (interleaveStreams (streamRepeat 1)
            (interleaveStreams (streamRepeat 2)
                (interleaveStreams (streamRepeat 3) (...))

中的前20元素

ruler =
    interleaveStreams (streamRepeat 0)
        (interleaveStreams (streamRepeat 1)
            (interleaveStreams (streamRepeat 2)
                (interleaveStreams (streamRepeat 3) (streamRepeat 4))))

是

[0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2]

显然，我不能手动将它定义为无穷大，所以我定义了一个infInterStream来帮助这样的无限递归定义：

infInterStream n = interleaveStreams (streamRepeat n) (infInterStream (n+1))

ruler = infInterStream 0

但是现在我在ruler中输入ghci时被卡住了，它可能会陷入无限循环。

如果懒惰的评估有效的话，那就不应该了。我想知道为什么懒惰的评估在这里失败了。

观察Stream的辅助函数

streamToList (Cons x xs) = x : streamToList xs

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

Answer 1

你的交错功能太严格了。以下工作：

interleaveStreams (Cons x xs) ys = Cons x (interleaveStreams ys xs)

这也适用于：

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

最初的定义进入无限循环，因为interleaveStreams要求这两个参数都必须是Cons表单。infInterStream n计算为两个流的交织，第一个流可以立即计算为Cons，但第二个流也必须先还原为Cons，因此我们递归地调用infInterStream (n + 1)，它始终无限地调用自己。

如果interleaveStreams可以在不强制第二个参数的情况下返回一个Cons a _，那么infInterStream也可以递增地构建结果。

Answer 2

不需要流的新类型，我们只需使用Haskell的惰性列表即可。正如其他人所指出的，交错的定义必须足够懒惰，在测试第二个参数是否为非空之前，它可以生成输出的第一个元素。这一定义将用于：

interleave (x:xs) ys = x : interleave ys xs

如果希望interleave也适用于有限列表，则可以添加该方程。

interleave [] ys = ys

还请注意，使用标准序曲中的函数，

ruler = interleave (repeat 0) (map (+1) ruler)

这里，repeat 0是列表[0, 0, 0, ...]。