[Haskell-beginners] list monad question

[Daniel Fischer]

Am Freitag 30 Oktober 2009 12:44:41 schrieb Matthias Guedemann:
> Hi,
>
> a friend of mine wanted to write function (in Perl) that creates all tuples
> of length 3 of the elements of a given list,
> e.g. [(0,0,0),(0,0,1),(0,0,2),...,(5,5,5)] for the list [0..5]. Trying to
> get better at Haskell, I wrote a small function using the list monad for
> this (tuples replaced with lists)
>
> all3 ls = do
>   a <- ls
>   b <- ls
>   c <- ls
>   return [a,b,c]
>
> Now I want to make it capable to create all combinations of length n
> instead of fixed length 3 (that's why list instead of tuple), but I don't
> really see how. As the do notation translates to
>
> ls >>= \a ->  etc.
>
> I thought it should be possible to have some sort of "foldr (>>=)" over a
> list of length n, but I can't figure out how to collect the variable number
> of results in a list for the "return".

Recursive version first:

combinations 0 _ = [[]]    -- whatever the list, there's one way to pick 0 elements
combinations n xs = do
    h <- xs
    t <- combinations (n-1) xs
    return (h:t)

(check for n < 0 omitted)

So, what are we doing? We have one list of a (xs) and one list of [a] (ys = combinations 
(n-1) xs) and cons each element of xs to each element of ys:

f xs ys = [h:t | h <- xs, t <- ys]
        = concat [[h:t | t <- ys] | h <- xs]
        = concat [map (h:) ys | h <- xs]
        = concat (map (\h -> map (h:) ys) xs)
        = xs >>= \h -> map (h:) ys

That gives

combinations n xs = foldr f [[]] (replicate n xs)

pointfree, for extra goodness:

-- pointfree f inline
combinations n xs = foldr ((. (. (:)) . flip map) . (>>=)) [[]] (replicate n xs)
-- eliminate xs
combinations n = foldr ((. (. (:)) . flip map) . (>>=)) [[]] . replicate n
-- completely pointfree
combinations = (foldr ((. (. (:)) . flip map) . (>>=)) [[]]  .) . replicate

>
> Any hints for that?
>
> best regards
> Matthias