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

First off, you need a base case for the singleton list as an argument. Try this:

count :: [Integer] -> [[Integer]]
count [] = []
count [n] = map (\x -> [x]) [0..n]
count (x:xs) =
     do y <- [0..x]
        nextDigits <- count xs
        return (y:nextDigits)

 main = do
   print $ count [1]
   print $ count [1,2]

Answer 2

count = sequence . map (enumFromTo 0)

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

Answer 3

For completeness, you can also express the logic as a list comprehension, which is probably the best way to use the list monad for simple functions:

count (x:xs) = [ (y:ys) | y <- [0..x], ys <- count xs ]

Answer 4

even shorter

count = mapM (enumFromTo 0)