Wyliczyć wszystkie skończone sekwencje liczb całkowitych?

Question

Chcę napisać zrozumienie listy Haskell, aby wyliczyć wszystkie skończone ciągi liczb całkowitych.

Jestem prawie pewny, że ten zestaw jest policzalny.

To, co mam tak daleko:

enumIntSeqs = [ (x, [ (x, [0..x]) | x <- [ x | x <- [0..x] ] ]) | x <- [0..] ] 

Innym pomysłem muszę to jakoś wymienić każdą skończoną ścieżkę w nieskończonym szeregu

Z * XZ * gdzie Z * = {0, 1 , -1, 2, -2, ...}

Answer 1

Jest to rzeczywiście możliwe. Ale to nie jest łatwe. Wyobraź sobie, że masz wyliczenie wszystkich liczb całkowitych, wyliczenie wszystkich par liczb całkowitych, wyliczenie wszystkich potrójnych liczb całkowitych itd. Następnie musisz wybrać "sprawiedliwie" z tych wyliczeń, aby upewnić się, że trafiłeś w każdy element każdego z nich. Podobny problem pojawi się, gdy spróbujesz wyliczyć wszystkie pary liczb całkowitych. Proponuję zacząć od tego problemu, a następnie zajrzyj do czegoś takiego jak Control.Monad.Omega, a może nawet Control.Monad.Logic.

Answer 2

Nie zamierzam psuć twojej zabawy, próbując pełnej odpowiedzi, więc pozwól mi zademonstrować garść rzeczy poprzez uproszczony problem wyliczenia wszystkich skończonych, niepustych sekwencji sąsiadujących ze sobą naturałów, począwszy od zera - coś że wydajesz się już bliska osiągnięcia na własną rękę. Kluczowe kroki są już zawarte w twoim enumIntSeqs, ale nie musisz zagnieżdżać takich wyrażeń na liście. Jeśli zaczynasz z ...

[ {- etc. -} | x <- [0..] ] 

... można wygenerować nową listę dla każdego x po prostu robi ...

[ {- etc. -} | x <- [0..], let ys = [0..x] ] 

... a wracając do tych list:

[ ys | x <- [0..], let ys = [0..x] ] 

(Zauważ, że nie napisałem ys <- [0..x]. Spróbuj przewidzieć, co by się stało w tym przypadku, a następnie sprawdzić w GHCi.)

Oddzielny let definicja nie jest konieczne, ani nie dodaje niczego pod względem jasności tego prostego zrozumienia, więc możemy po prostu napisać:

[ [0..x] | x <- [0..] ] 

I to wszystko.

Prelude> take 4 $ [ [0..x] | x <- [0..] ] 
[[0],[0,1],[0,1,2],[0,1,2,3]] 

P.S .: Dwa inne sposoby zapisu wyliczenia. Używanie do-notacji ...

someIntSeqs = do 
    x <- [0..] 
    return [0..x] 

... i ze skromnym fmap (który w tym przypadku jest taka sama jak map):

Prelude> take 4 $ fmap (\x -> [0..x]) [0..] 
[[0],[0,1],[0,1,2],[0,1,2,3]] 
Prelude> -- Or, equivalently... 
Prelude> take 4 $ (\x -> [0..x]) <$> [0..] 
[[0],[0,1],[0,1,2],[0,1,2,3]]