Haskell CIS194 Spring 13 作业 6 练习 5

Question

http://www.seas.upenn.edu/~cis194/spring13/hw/06-laziness.pdf

问题是关于表示标尺函数

0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, . . . where the nth element in the stream (assuming the first element corresponds to n = 1) is the largest power of 2 which evenly divides n

我有一个可行的解决方案，使用 show 通过 interleaveStreams 函数显示前 20 个元素:

data Stream a = Cons a (Stream a)

streamToList :: Stream a -> [a]
streamToList (Cons a b) = a : streamToList b 

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

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

ruler :: Stream Integer
ruler = 
  let s n = interleaveStreams' (streamRepeat n) (s (n+1)) 
  in s 0

interleaveStreams :: Stream a -> Stream a -> Stream a
interleaveStreams (Cons x xs) (Cons y ys) = Cons x (Cons y (interleaveStreams xs ys))

interleaveStreams' :: Stream a -> Stream a -> Stream a
interleaveStreams' (Cons x xs) y = Cons x $ interleaveStreams' y xs

但是我不明白为什么使用交错函数的标尺不以 Show 终止。

Answer 1

首先恭喜 - 您解决了困难部分;)

对于你的问题:如果你使用interleaveStreams，那么它也会在第二个Cons上进行模式匹配 - 但如果你查看你的代码，你会发现第二部分生成者:

let s n = interleaveStreams ... (s (n+1)) 

因此，如果 interleaveStreams 现在要求它为这部分产生一个缺点，那么您最终会陷入无限循环

另一个函数通过仅强制执行第一个构造函数来解决此问题，您可以从streamRepeat立即获得该构造函数

交错流:

s 0
= interleaveStreams (streamRepeat 0) (s 1))
{ need both cons }
= interleaveStreams (Cons 0 (streamRepeat 0)) (s 1)
= interleaveStreams (Cons ...) (interleaveStreams (streamRepeat 1) (s 2))
{ the inner interleaveStream needs both Cons again for it's pattern }
= ...

你永远不会遇到Cons，并且streamToList将永远无法生成列表cons，然后你就会遇到问题

interleaveStreams':

s 0
= interleaveStreams' (streamRepeat 0) (s 1))
{ need only first Cons for the pattern-match }
= interleaveStreams' (Cons 0 (streamRepeat 0)) (s 1)
= Cons 0 $ interleaveStreams' (s 1) (streamRepeat 0)
= ...

如您所见，您得到了缺点，这是 show/streamToList

中懒惰的最佳途径

---

短一点

顺便说一句:您可以使用 streamMap 在没有 s 内部函数的情况下编写此代码:

ruler :: Stream Integer
ruler = interleaveStreams (streamRepeat 0) (streamMap (+1) ruler)