Enumerate All Finite Sequences of Integers?

Question

I want to write a Haskell list comprehension to enumerate all finite sequences of integers.

I'm pretty 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 list every finite path in the infinite array

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

Answer 1

This is, indeed, possible. But it is not easy. Imagine 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 "fairly" from those enumerations to be sure to hit each element of each. A similar problem will arise when you try even to enumerate all pairs of integers. I suggest you start with that problem, and then look into something like Control.Monad.Omega, or perhaps even Control.Monad.Logic.

Answer 2

I am not going to spoil your fun by attempting a full answer, so let me just demonstrate a handful of things through the simplified problem of enumerating all finite, non-empty, sequences of contiguous naturals starting from zero -- something that you seem close to achieving on your own already. The key steps are already amidst your enumIntSeqs, but you don't have to nest list comprehensions like that. If you begin with...

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

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

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

... and then returning those lists:

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

(Note that I didn't write ys <- [0..x]. Try to predict what would happen in that case, and then check it in GHCi.)

The separate let definition isn't necessary, nor does it add anything in terms of clarity in this simple comprehension, so we can just write:

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

And that's it.

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

P.S.: Two other ways of writing the enumeration. Using do-notation...

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

... and with a humble fmap (which in this case is the same as 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]]