All combinations

gistfile1.hs

import Control.Arrow

combine :: [a] -> [[a]]
combine = sequence . uncurry replicate . (length &&& id)

{- 

Test run:
Prelude Control.Arrow> combine ['A', 'C', 'G']
["AAA","AAC","AAG","ACA","ACC","ACG","AGA","AGC","AGG","CAA","CAC","CAG","CCA","CCC","CCG","CGA","CGC","CGG","GAA","GAC","GAG","GCA","GCC","GCG","GGA","GGC","GGG"]

-}


{-

The version that I came up with before:
combine xs = sequence $ replicate (length xs) xs

-}

Just checked with lambdabot, and it produced an even compacter version!

combine = sequence . (replicate =<< length)

This is how the arrow version works:

&&& takes two functions* of types (a -> b) and (a -> c) and composes them into one function of type (a -> (b, c)). In our case length has type [a] -> Int and id has type a -> a. So (length &&& id) has type [a] -> (Int, [a]). The signature of replicate is Int -> [a] -> [[a]]. So we need to uncurry replicate in order to be able to compose it with (length &&& id). And the final part is easy. The implementation of sequence function for list monad gives its Cartesian product. And there we have it, all combinations of elements of the list.

* Actually &&& works on arrows, and functions are arrows.