无法定义无限流

Question

我正在研究UPENN Haskell Homework 6练习5,试图定义一个ruler function

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

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

我想出了一个没有任何可分性测试的构建它的想法:

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也可以逐步构建结果.