使用 `streamInterleave` 实现标尺功能

Question

我正在做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....] 吗？

任何帮助将不胜感激。谢谢！！

Answer 1

首先，我们将这样表示 Stream：

a1 a2 a3 a4 a5 ...

现在，让我们拆开ruler的定义：

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

在Haskell中，重要的一点是懒惰；也就是说，东西在需要时才需要评估。这一点在这里很重要：这就是使这个无限递归定义起作用的原因。那么我们如何理解这一点呢？我们将从 streamRepeat 0 位开始：

0 0 0 0 0 0 0 0 0 ...

然后将其送入 streamInterleave，将其与来自 streamMap (+1) ruler（用 xs 表示）的（目前未知的）流交错：

0 x 0 x 0 x 0 x 0 x 0 x ...

现在我们将开始填写那些 x。我们已经知道 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，因此 [=21= 的对应元素] 必须是 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 像这样无限，方法是将 ruler 的每个 n/2, 3n/2, 5n/2, ... 编号值替换回去。

Answer 2

在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:

使用 `streamInterleave` 实现标尺功能

Implementing the ruler function using `streamInterleave`

haskell

stream

infinite

self-reference

interleave