无法定义无限流

Question

我正在研究 UPENN Haskell Homework 6 Exercise 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

但是现在在ghci中输入ruler就卡住了，估计是死循环了

如果惰性求值有效，则不应该。我想知道为什么懒惰评估在这里失败。

观察辅助函数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 可以 return 一个 Cons a _ 而无需首先强制第二个参数，infInterStream 也可以逐步构建结果。

Answer 2

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

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

如果您希望interleave也适用于有限列表，您可以添加等式

interleave [] ys = ys

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

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

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

无法定义无限流

Fail to define an infinite stream

haskell

stream

lazy-evaluation