我正在做CIS 194的作业。问题是通过使用streamInterleave
来实现标尺功能。代码看起来像
data Stream a = Cons a (Stream a)
streamRepeat :: a -> Stream a
streamRepeat x = Cons x (streamRepeat x)
streamMap :: (a -> b) -> Stream a -> Stream b
streamMap f (Cons x xs) = Cons (f x) (streamMap f xs)
streamInterleave :: Stream a -> Stream a -> Stream a
streamInterleave (Cons x xs) ys = Cons x (streamInterleave ys xs)
ruler :: Stream Integer
ruler = streamInterleave (streamRepeat 0) (streamMap (+1) ruler)
我真的很困惑为什么统治者可以像这样实施。这会给我[0,1,0,1....]
吗?
任何帮助将不胜感激。谢谢!!
首先,我们将代表像这样的Stream
:
a1 a2 a3 a4 a5 ...
现在,我们将ruler
的定义分开:
ruler :: Stream Integer
ruler = streamInterleave (streamRepeat 0) (streamMap (+1) ruler)
在哈斯克尔,重要的一点是懒惰;也就是说,在需要之前不需要对东西进行评估。这在这里很重要:它是使这个无限递归定义起作用的原因。那我们怎么理解这个呢?我们将从streamRepeat 0
位开始:
0 0 0 0 0 0 0 0 0 ...
然后将其输入streamInterleave
,将streamMap (+1) ruler
(用x
s表示)与(尚未知)流交错:
0 x 0 x 0 x 0 x 0 x 0 x ...
现在我们将开始填写那些x
s。我们已经知道ruler
的每一个元素都是0
,所以streamMap (+1) ruler
的每一个元素都必须是1
:
1 x 1 x 1 x 1 x 1 x ... <--- the elements of (streamMap (+1) ruler)
0 1 0 x 0 1 0 x 0 1 0 x 0 1 0 x 0 1 0 x ... <--- the elements of ruler
现在我们知道每组四个中的每一个元素(所以数字2,6,10,14,18,...)是1
,所以streamMap (+1) ruler
的相应元素必须是2
:
1 2 1 x 1 2 1 x 1 2 ... <--- the elements of (streamMap (+1) ruler)
0 1 0 2 0 1 0 x 0 1 0 2 0 1 0 x 0 1 0 2 ... <--- the elements of ruler
现在我们知道每组八个中的每四个元素(所以数字4,12,20,...)是2
所以streamMap (+1) ruler
的相应元素必须是3
:
1 2 1 3 1 2 1 x 1 2 ... <--- the elements of (streamMap (+1) ruler)
0 1 0 2 0 1 0 3 0 1 0 2 0 1 0 x 0 1 0 2 ... <--- the elements of ruler
我们可以通过替换每个ruler
编号的n/2, 3n/2, 5n/2, ...
值继续像这样无限制地建立ruler
。
在Haskell表示法中,用[]
代替Stream
(与无限列表同构),
ruler = interleave (repeat 0)
(map (+1) ruler)
[ruler !! i | i <- [0..]] == concat . transpose $
[ repeat 0
, map (+1) ruler]
将ruler
分成两个交替的子序列以匹配,我们得到
[ruler !! 2*i | i <- [0..]] == repeat 0
== [0 | i <- [0..]] -- {0} --
[ruler !! 2*i+1 | i <- [0..]] == map (+1) ruler
== map (+1) $ concat . transpose $
[ [ruler !! 2*i | i <- [0..]]
, [ruler !! 2*i+1 | i <- [0..]]]
concat . transpose $ == concat . transpose $
[[ruler !! 2*i+1 | i <- [0,2..]] [ [1 | i <- [0..]]
,[ruler !! 2*i+1 | i <- [1,3..]]] , [1 + ruler !! 2*i+1 | i <- [0..]]]
再次分裂,
[ruler !! 4*i+1 | i <- [0..]] == [1 | i <- [0..]] -- {1} --
[ruler !! 4*i+3 | i <- [0..]] == concat . transpose $
[ [1 + ruler !! 2*i+1 | i <- [0,2..]]
, [1 + ruler !! 2*i+1 | i <- [1,3..]]]
然后再次,
[ruler !! 8*i+3 | i <- [0..]] == [2 | i <- [0..]] -- {2} --
[ruler !! 8*i+7 | i <- [0..]] == ....
你应该能够从这里看到它:
.... 16*i+7 ..... 3 -- {3} --
.... 32*i+15 ..... 4 -- {4} --
.... 64*i+31 .....
....
从而,
ruler !! 2^(k+1)*i + 2^k - 1 == k , k <- [0..] , i <- [0..]
0: i => 2i
1: 2i+1 => 4i+1
2: 4i+3 => 8i+3
3: 8i+7 => 16i+7
4: 16i+15 => ....
5: