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