implementing a per-digit counter using the list monad

Question

So, I was looking at the question here, and built a rather ugly solution for the problem. While trying to clean it up, I started investigating list comprehensions and the list monad. What I decided to do was to implement a per-digit counter using the list monad. Given an input sequence of digits, [1, 2], I wanted to generate an output sequence that looked something like:

[ [ 0, 0],
  [ 0, 1 ],
  [ 0, 2 ],
  [ 1, 0 ],
  [ 1, 1 ],
  [ 1, 2 ] ]

That is, I'd iterate over all possible values of all elements in the list in that range.

The haskell.org list monad documentation says:

The bound function is applied to all possible values in the input list and the resulting lists are concatenated to produce a list of all possible results.

Great! Looks perfect... Here's the code I wrote to produce the solution:

count :: [Integer] -> [[Integer]]
count [] = []
count (x:xs) =
  -- get all possible sequences for the remaining digits
  let
    remDigits :: [[Integer]]
    remDigits = count xs
  in
  -- pull out a possible sequence for the remaining digits
  do nextDigits <- remDigits
     -- pull out all possible values for the current digit
     y <- [0..x]
     -- record that "current digit" : "remaining digits" is
     -- a valid output.
     return (y:nextDigits)

But calling count with anything produces the empty list, and I don't know why. What am I missing?

Answer 1

count = sequence . map (enumFromTo 0)

Yes, it's really as simple as that. Give it a try :)