Haskell combinations and permutation

Question

I have three word in a list ["a","b","c"]. i want to find all possible combination in set 5,6 etc.

for example for set of 5 i would have

**[ [aaaaa],[aaaab],[aaaac], [aaabc] , ..... ]** etc 3 ^ 5 = 243 combinations

aaaaaa above will basically be "a","a","a","a","a" ....

Answer 1

Of course, nanothief's answer gives the shortest solution, but it might be instructive and fun to do it yourself.

There are many ways to write a function for the cartesian product. E.g. you can use list comprehensions:

prod :: [[a]] -> [[a]] -> [[a]]
prod as bs = [a ++ b | a <- as, b <- bs]

Where (++) :: [a] -> [a] -> [a] -- see Data.List. Another possibility is to use the Applicative instance of list:

import Control.Applicative

prod as bs = (++) <$> as <*> bs

Now you need to apply this operation repeatedly. A fold can do this, e.g.:

rep :: Int -> [[a]] -> [[a]]
rep n as = foldr1 prod $ replicate n as

rep 3 ['a','b','c']
--["aaa","aab","aac","aba","abb","abc","aca","acb","acc","baa","bab",
--"bac","bba","bbb","bbc","bca","bcb","bcc","caa","cab","cac","cba",
--"cbb","cbc","cca","ccb","ccc"]

Understanding this solution might be more valuable than taking the replicateM short cut. That said, you could have found the latter easily using Hoogle.

--

For more on Functors and Applicative see definitions fmap (<$>) and ap (<*>). Functors, Applicatives, And Monads In Pictures can also be a good resource.

Answer 2

replicateM does what you want:

> import Control.Monad
> replicateM 5 ["a", "b", "c"]
[["a","a","a","a","a"],["a","a","a","a","b"],["a","a","a","a","c"],["a","a","a","b","a"],["a","a","a","b","b"],["a","a","a","b","c"],["a","a","a","c","a"],["a","a","a","c","b"],["a","a","a","c","c"],["a","a","b","a","a"],["a","a","b","a","b"],["a","a","b","a","c"],["a","a","b","b","a"],["a","a","b","b","b"],["a","a","b","b","c"]...]