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

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

关于您的问题：如果您使用 interleaveStreams，它也会在第二个 Cons 上进行模式匹配 - 但是如果您查看您的代码，您会发现第二部分是由以下内容生成的：

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

所以如果 interleaveStreams 现在要求它为这部分生成一个 Cons 你最终会陷入无限循环

另一个函数通过仅强制第一个构造函数解决了这个问题，你可以立即从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 永远无法产生列表缺点，然后你就会遇到问题

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)
= ...

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

中懒惰的快乐之路

短一点

顺便说一句：您可以使用 streamMap:

在没有 s 内部函数的情况下编写此代码

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

Haskell CIS194 Spring 13 家庭作业 6 练习 5

Haskell CIS194 Spring 13 Homework 6 Exercise 5

haskell

lazy-evaluation

交错流：

interleaveStreams':

短一点