Реализация функции линейки с использованием `streamInterleave` - PullRequest
Новая
       31

Реализация функции линейки с использованием `streamInterleave`

1 голос
/ 25 марта 2019

Я делаю домашнюю работу по СНГ 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....]?

Любая помощь будет принята с благодарностью.Спасибо !!

Ответы [ 2 ]

1 голос
/ 26 марта 2019

В нотации 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:
1 голос
/ 25 марта 2019

Во-первых, мы представим 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.

...