Haskell不懒惰地评估交织 [英] Haskell not lazy evaluating interleaving

问题描述

我正在解决一个问题(来自UPenn类，但是我没有接受(只是通过它来学习Haskell))，重点是构造一个Stream(定义如下)由"ruler"(统治者!! n = 2的最高次幂的指数除以n)得出.问题是我认为下面的标尺定义应该懒惰地求值，但是它似乎在严格地评估并且无限地运行.如果我通过添加诸如"nthStream 10 = streamRepeat 10"之类的终端案例来设置其上限，它将运行并生成直到我想要的正确点的输出.

I am working through a problem (its from a UPenn class, but I am not taking it (just working through it to learn Haskell)), and the point is to construct a Stream (as defined below), that is defined by "ruler" (ruler !! n = the exponent of the highest power of 2 which will divide n). The issue is that I think that the definition for ruler below should lazily evaluate, but it seems to be evaluating strictly and running infinitely. If I cap it by adding a terminal case like "nthStream 10 = streamRepeat 10" it runs and generates output up to the point I want correctly.

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)没有懒惰地求值吗?

Can anyone explain why ruler (and nthStream) is not lazily evaluating?

推荐答案

我将尝试向正确的方向轻推，或者至少指出出了什么问题.函数 nthStream 永远不会求值，即使它的第一个元素也不会求值，因为它是通过 interleaveStreams 定义的.举一个例子，让我们计算一下它对 nthStream 0 的评估结果(为了简洁起见，我将 nthStream 重命名为 nth ， interleaveStream 到 interleave ， streamRepeat 到 repeat ，以及 Stream 到 Strm):

I'll try to nudge you in the right direction, or at least point out what's going wrong. The function nthStream will never evaluate, not even its first element, because of how it's defined with interleaveStreams. To give you an example, let's work out what it evaluates to for nthStream 0 (for brevity and readability I've renamed nthStream to nth, interleaveStream to interleave, streamRepeat to repeat, and Stream to 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 是要重复的数字.这些目前是重击，因为我们还没有要求它们的值.请注意，是如何建立一个 interleave 链，而不是一个 Strm 构造函数链.我们得到了我们感兴趣的每个参数，但是在评估第二个参数之前，它们永远无法从 interleave 返回.由于第二个参数总是减少为对 interleave 的新调用，因此永远不会减少.

I've chosen to represent the tails of each stream returned from repeat as _N where N is the number being repeated. These are currently thunks, since we haven't had to request their values yet. Notice how what is building up is a chain of interleaves, rather than a chain of Strm constructors. We get each one we're interested in, but they can never return from interleave until the second argument is evaluated. Since the second argument is always getting reduced to a new call to interleave, it'll never reduce.

这里有个提示:如何递归定义 interleaveStreams ，使其仅取决于已构造的第一个参数?即

Here's a hint: how can you define interleaveStreams recursively so that it only depends on its first argument being constructed already? i.e.

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

这篇关于Haskell不懒惰地评估交织的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！