Haskell 并不懒惰地评估交错

Question

我正在解决一个问题(它来自 UPenn 类(class)，但我没有接受它(只是通过它来学习 Haskell))，重点是构造一个 Stream(如下定义)，它被定义为通过“标尺”(标尺!! n = 2 的最高幂的指数来除以 n)。问题是，我认为下面标尺的定义应该延迟评估，但它似乎严格评估并无限运行。如果我通过添加像“nthStream 10 = streamRepeat 10”这样的终端案例来限制它，它就会运行并生成输出，直到我想要正确的点。

data Stream a = Stream a (Stream a)

streamToList :: Stream a -> [a]
streamToList (Stream a rest) = [a] ++ streamToList rest

instance Show a => Show (Stream a) where
    show s = show $ take 100 $ streamToList s

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

interleaveStreams :: Stream a -> Stream a -> Stream a
interleaveStreams (Stream a arest) (Stream b brest) = (Stream a (Stream b (interleaveStreams arest brest)))

nthStream :: Integer -> Stream Integer

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

ruler :: Stream Integer
ruler = nthStream 0 

任何人都可以解释为什么统治者(和nthStream)不延迟评估吗？

Answer 1

我会尽力将您推向正确的方向，或者至少指出出了什么问题。函数 nthStream 永远不会计算，甚至不会计算它的第一个元素，因为它是用 interleaveStreams 定义的。举个例子，让我们计算一下 nthStream 0 的计算结果(为了简洁和可读性，我将 nthStream 重命名为 nth， interleaveStream 到 interleave、streamRepeat 到 repeat 以及 Stream 到 Strm ):

nth 0 = interleave (repeat 0) (nth 1)
      = interleave (Strm 0 _0) (interleave (repeat 1) (nth 2))
      = interleave (Strm 0 _0) (interleave (Strm 1 _1) (nth 2))
      = interleave (Strm 0 _0) (interleave (Strm 1 _1) (interleave (repeat 2) (nth 3)))
      = interleave (Strm 0 _0) (interleave (Strm 1 _1) (interleave (Strm 2 _2) (nth 3)))

我选择将从 repeat 返回的每个流的尾部表示为 _N，其中 N 是重复的数字。这些目前是 thunk，因为我们还不需要请求它们的值。请注意，正在构建的是一个 interleave 链，而不是一个 Strm 构造函数链。我们得到了我们感兴趣的每个参数，但在计算第二个参数之前，它们永远无法从 interleave 返回。由于第二个参数始终会减少为对 interleave 的新调用，因此它永远不会减少。

这里有一个提示:如何递归地定义 interleaveStreams 以便它仅依赖于已经构造的第一个参数？即

interleaveStreams (Stream a arest) streamB = Stream a (???)