List all finite sequences of integers?

Question

I want to write an understanding of the Haskell list to list all finite sequences of integers.

I am sure that this set is countable.

This is what I have so far:

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

Another idea I have is to somehow enumerate each final path in an infinite array

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

Answer 1

It is really possible. But it is not easy. Imagine that you have an enumeration of all integers, an enumeration of all pairs of integers, an enumeration of all triples of integers, etc. Then you need to choose “fair” from these listings to hit every element of each. A similar problem will arise if you try to list all pairs of integers. I suggest you start with this problem, and then look into something like Control.Monad.Omega or perhaps even Control.Monad.Logic .

Answer 2

I'm not going to spoil your pleasure in trying to get a complete answer, so let me demonstrate a few things through the simplified problem of listing all finite, non-empty sequences of adjacent natural numbers, starting from zero - something that you are already close to achieving on your own. Key steps are already among your enumIntSeqs , but you do not need to insert such lists. If you start with ...

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

... you can create a new list for each x by simply doing ...

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

... and then return these lists:

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

(Note that I did not write ys <- [0..x] . Try to predict what will happen in this case, and then check it in GHCi.)

A separate definition of let not required and does not add anything in terms of clarity in this simple understanding, so we can simply write:

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

What is it.

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

PS: Two other ways to write an enumeration. Using do-notation ...

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

... and with a modest fmap (which in this case matches 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]]