Взяв конечную часть бесконечной структуры

Question

Мне нужно определить бесконечный велосипедист

enumInts::Cyclist Integer

, содержащий все целые числа в естественном порядке, где нулем является текущий элемент.

Что я сделал:

data Cyclist a=Elem (Cyclist a) a (Cyclist a) 

enumInts:: Cyclist Integer 
enumInts=Elem prev 0 next 
      where 
            prev=help2 enumInts 0 
            next=help1 enumInts 0 

-- Create positive part 
help1::Cyclist Integer -> Integer -> Cyclist Integer 
help1 prev n=present 
      where present=Elem prev (n+1) next 
                        where next=help1 present (n+1) 

-- Create negative part 
help2::Cyclist Integer -> Integer -> Cyclist Integer 
help2 next n=present 
      where present=Elem prev (n-1) next 
                        where prev=help2 present (n-1)

Он сам компилируется.Но я не уверен, работает ли он так, как должен ... поэтому я хотел бы увидеть его результат, например.11 шт.Должно быть: -5 -4 -3 -2 -1 0 1 2 3 4 5 значений.Можно ли это увидеть?(Я знаю, что это бесконечно), но, например,в последовательности Фибоначчи мы могли бы использовать «взять 11 фибров», и это дало их.Здесь опция 'take n ..' не работает (хм или она работает, но я не знаю, как ее использовать).Буду признателен за вашу помощь ..

Answer 1

Я уверен, что это уже далеко от твоего крайнего срока, поэтому мне было весело иметь дело с дважды бесконечными целыми числами:

Разрешение конечной части

Чтобы сделать функцию взятия, мне нужно отредактировать ваш тип так, чтобы он мог быть конечным:

data Cyclist a=Elem (Cyclist a) a (Cyclist a) | Empty
  deriving Show

takeToDepth :: Int -> Cyclist a -> Cyclist a
takeToDepth 0 _ = Empty
takeToDepth n (Elem c1 a c2) 
      | n >0 = Elem (takeToDepth (n-1) c1) a (takeToDepth (n-1) c2)
      | otherwise = Empty
takeToDepth n Empty = Empty

Но теперь мы можем увидеть ошибку в вашем типе данных:

*Main> takeToDepth 1 enumInts
Elem Empty 0 Empty
0 -- I've drawn the tree

и

*Main> takeToDepth 2 enumInts
Elem (Elem Empty (-1) Empty) 0 (Elem Empty 1 Empty)

  0   
  |       -- looks OK
 ---      -- see the end of the answer for how I pretty printed
/   \
-1  1

Пока все выглядит нормально, но:

*Main> takeToDepth 3 enumInts
Elem (Elem (Elem Empty (-2) Empty) (-1) (Elem Empty 0 Empty)) 
 0 (Elem (Elem Empty 0 Empty) 1 (Elem Empty 2 Empty))

Это не та структура, которую мы хотим - в ней три нуля!

     0     
     |     
   -----   
  /     \  
  -1    1  
  |     |  
 ---    -- 
/   \  /  \
-2  0  0  2    -- oops! We've re-created zero for 1 and -1

Есть два 0 с и два каждого числа в конце. Еще хуже, если мы пойдем глубже

*Main> takeToDepth 4 enumInts
Elem (Elem (Elem (Elem Empty (-3) Empty) (-2) (Elem Empty (-1) Empty)) (-1) 
 (Elem (Elem Empty (-1) Empty) 0 (Elem Empty 1 Empty))) 0 
 (Elem (Elem (Elem Empty (-1) Empty) 0 (Elem Empty 1 Empty)) 1 
 (Elem (Elem Empty 1 Empty) 2 (Elem Empty 3 Empty)))

                         0   
                         |                         
             --------------------------            
            /                          \           
            -1                         1           
            |                          |           
       -------------              -----------      
      /             \            /           \     
      -2            0            0           2     
      |             |            |           |     
   -------        -----        -----       -----   
  /       \      /     \      /     \     /     \  
  -3      -1     -1    1      -1    1     1     3  
  |       |      |     |      |     |     |     |  
 ---     ---    ---    --    ---    --    --    -- 
/   \   /   \  /   \  /  \  /   \  /  \  /  \  /  \
-4  -2  -2  0  -2  0  0  2  -2  0  0  2  0  2  2  4

Нам не нужны все эти вещи посередине. То, что мы хотим, больше похоже на

this = Elem (Elem (Elem (Elem Empty (-3) Empty) (-2) Empty) (-1) Empty) 
 0 (Elem Empty 1 (Elem Empty 2 (Elem Empty 3 Empty)))


  0  
  |  
 --- 
/   \
-1  1
|   |
-2  2
|   |
-3  3

Это хорошо, но есть так много Empty s, это сбивает с толку.

Создание типа данных, который соответствует вашим намерениям.

Что нам действительно нужно, так это текущий элемент, что-то вроде списка, растягивающегося вправо, и что-то вроде списка, растягивающегося назад влево. Компилятор не имеет смысла направления, поэтому мы будем использовать одну и ту же структуру для обоих, но не забудьте напечатать левую сторону назад на правой стороне.

Для начала нам нужен определенно бесконечный список:

data InfiniteList a = IL a (InfiniteList a)         deriving Show

tailIL (IL _ therest) = therest
headIL (IL a _      ) = a

fromList [] = error "fromList: finite list supplied"
fromList (x:xs) = IL x (fromList xs)

toList (IL a therest) = a:toList therest

Теперь мы можем сделать его бесконечным в обоих направлениях:

data DoublyInfiniteList a = DIL {left  :: InfiniteList a,
                                 here  :: a,
                                 right :: InfiniteList a}
   deriving Show

enumIntsDIL = DIL {left = fromList [-1,-2..], here = 0, right = fromList [1..]}

Что выглядит так:

  0  
  |  
 --- 
/   \
-1  1
|   |
-2  2
|   |
-3  3
|   |
-4  4

только с бесконечным числом элементов, а не только с 9.

Давайте сделаем способ передвигаться. Это можно сделать более эффективным с использованием reverse, toList и fromList, но таким образом вы увидите, как вы можете связываться с его частями:

go :: Int -> DoublyInfiniteList a -> DoublyInfiniteList a
go 0 dil = dil
go n dil | n < 0 = go (n+1) DIL {left  = tailIL . left $ dil,
                                 here  = headIL . left $ dil,
                                 right = IL (here dil) (right dil)}
go n dil | n > 0 = go (n-1) DIL {left  = IL (here dil) (left dil),
                                 here  = headIL . right $ dil,
                                 right = tailIL . right $ dil}

Теперь мы можем преобразовывать данные в другой тип данных каждый раз, когда мы хотим быть конечными.

data LeftRightList a = LRL {left'::[a],here'::a,right'::[a]}  -- deriving Show

toLRL :: Int -> DoublyInfiniteList a -> LeftRightList a
toLRL n dil = LRL {left'  = take n . toList . left $ dil,
                   here'  = here dil,
                   right' = take n . toList . right $ dil}

Что дает

*Main> toLRL 10 enumIntsDIL
LRL {left' = [-1,-2,-3,-4,-5,-6,-7,-8,-9,-10], here' = 0, right' = [1,2,3,4,5,6,7,8,9,10]}

но вы, вероятно, хотите напечатать это так, чтобы это выглядело так, как вы хотите:

import Data.List  -- (Put this import at the top of the file, not here.)

instance Show a => Show (LeftRightList a) where    
 show lrl =    (show'.reverse.left' $ lrl)    -- doesn't work for infinite ones!
            ++  ",   " ++ show (here' lrl) ++ "   ," 
            ++ (show' $ right' lrl)  where
    show' = concat.intersperse "," . map show 

Что дает

*Main> toLRL 10 enumIntsDIL
-10,-9,-8,-7,-6,-5,-4,-3,-2,-1,   0   ,1,2,3,4,5,6,7,8,9,10
*Main> toLRL 10 $ go 7 enumIntsDIL
-3,-2,-1,0,1,2,3,4,5,6,   7   ,8,9,10,11,12,13,14,15,16,17

Конечно, мы могли бы просто преобразовать в список и показать это, но мы потеряли бы способность указывать, где мы были.

Приложение: Как я красиво напечатал деревья

import Data.Tree
import Data.Tree.Pretty

Существует несколько разных типов деревьев и т. Д., Поэтому я дал себе класс для преобразования каждого из них в Дерево:

class TreeLike t where
  toTree :: t a -> Tree a

treeTake :: Int -> Tree a -> Tree a
treeTake 1 (Node a _) = Node a []
treeTake n (Node a ts) | n > 1 = Node a (map (treeTake (n-1)) ts)
                       | otherwise = error "treeTake: attemt to take non-positive number of elements"

see :: (TreeLike t,Show a) => Int -> t a -> IO ()
see n = putStrLn.drawVerticalTree.fmap show.treeTake n.toTree

Который мы используем так:

*Main> see 5 $ go (-2) enumIntsDIL
  -2  
  |   
 ---  
/   \ 
-3  -1
|   | 
-4  0 
|   | 
-5  1 
|   | 
-6  2 

Первый ваш велосипедист:

instance TreeLike Cyclist where
 toTree Empty = error "toTree: error - Empty"
 toTree (Elem Empty a Empty) = Node a []
 toTree (Elem Empty a c2) = Node a [toTree c2]
 toTree (Elem c1 a Empty) = Node a [toTree c1]
 toTree (Elem c1 a c2) = Node a [toTree c1,toTree c2]

Следующий дважды бесконечный список:

instance TreeLike InfiniteList where
 toTree (IL a therest) = Node a [toTree therest]

instance TreeLike DoublyInfiniteList where
 toTree dil = Node (here dil) [toTree $ left dil,toTree $ right dil]

А затем левый-правый список:

instance TreeLike [] where
 toTree [] = error "toTree: can't make a tree out of an empty list"
 toTree [x] = Node x []
 toTree (x:ys) = Node x [toTree ys]

instance TreeLike LeftRightList where
 toTree lrl = Node (here' lrl) [toTree $ left' lrl,toTree $ right' lrl]

Answer 2

Это мое решение:

enumInts :: Cyclist Integer
enumInts = Elem (goLeft enumInts) 0 (goRight enumInts)
    where
        goLeft this@(Elem left n _) = let left = Elem (goLeft left) (n-1) this in left
        goRight this@(Elem _ n right) = let right = Elem this (n+1) (goRight right) in right

, и вы можете использовать его следующим образом:

label . forward . backward . forward . forward $ enumInts

где:

label (Elem _ x _) = x
forward (Elem _ _ x) = x
backward (Elem x _ _) = x

Answer 3

Хотя он встроен, вы можете представить, что тип списка определен как

data [a] = [] | a : [a]

take можно определить так:

take 0 xs = []
take n (x:xs) = x:take (n-1) xs

Вы должны попытатьсяпосмотрите, как вы можете настроить определение take для вашего собственного типа.

Answer 4

Я думаю, что это можно решить следующим образом:

Наши бесконечные данные

myList = ([0] ++ ) $ conca­t $ [[x] ++  [-x] | x <- [1..]]

получение определенного количества элементов из этого списка:

takeOnly n = sort $ take n myList

Answer 5

Если вам нужны именно эти цифры, почему бы просто не использовать

enumInts :: Integer -> [Integer]
enumInts n = [-(n`div`2)..(n`div`2)]