Monadic way for list comprehension

Question

I have the following function

combinations :: [[a]] -> [[a]]
combinations []       = [[]]
combinations (xs:xss) = concat [map (x:) yss | x <- xs]
  where yss = combinations xss

Which produces all combinations between its elements:

*Main> combinations [[1,2],[2,3,4],[5,6]]
[[1,2,5],[1,2,6],[1,3,5],[1,3,6],[1,4,5],[1,4,6],[2,2,5],[2,2,6],[2,3,5],[2,3,6]
,[2,4,5],[2,4,6]]

I some how feel there must be a monadic way to do this

foobar = do
    n <- [1,2]
    ch <- [3,4,5]
    return[n,ch]

This is how far I came. But I am stuck.

Answer 1

The best I've been able to come up with is

combinations [] = [[]]
combinations (xs:xss) = do
    x <- xs
    ys <- combinations xss
    return $ x : ys

---

The way I derived this was I first converted the list comprehension into monadic code (which also meant dropping the concat to get it to type check)

combinations (xs:xss) =
    let yss = combinations xss
    in do
        x <- xs
        map (x:) yss

Then I realized that map (x:) yss is exactly fmap (x:) yss, which is exactly yss >>= return . (x:), so I knew I could do

combinations (xs:xss) =
    let yss = combinations xss
    in do
        x <- xs
        ys <- yss
        return $ x : ys

And then it can be inlined as

combinations (xs:xss) = do
    x <- xs
    ys <- combinations xss
    return $ x : ys

Answer 2

Your function is sequence for the list monad.

> :t sequence
sequence :: Monad m => [m a] -> m [a]
> sequence [[1,2],[2,3,4],[5,6]]
[[1,2,5],[1,2,6],[1,3,5],[1,3,6],[1,4,5],[1,4,6],[2,2,5],[2,2,6],[2,3,5],[2,3,6],
[2,4,5],[2,4,6]]