Permutations in Haskell or "I feel old ..."
I was actually looking for someone who have made a simulation of the gravitational force between particles, but instead I came across another topic concerning haskell.
The author had tried to grok haskell a few times and was stuck again on his third attempt. He had a problem with understanding an implementation of calculating all possible permutations of a list of items.
His friend had given him one implementation which was difficult to grasp.
permute :: [a] -> [[a]]
permute = foldr (concatMap . ins) [[]]
where ins x [] = [[x]]
ins x (y:ys) = (x:y:ys):[ y:res | res <- ins x ys]
So I thought I would try implement a variant of permute. To understand this explanation it is useful to know basic haskell concepts including lists, functions and pattern matching and list comprehension.
First I tried some examples of permute on paper.
[a]
[a,b] [b,a] -- insert b in [a]
[c,a,b][a,c,b][a,b,c] [c,b,a][b,c,a][b,a,c] -- insert c in [a,b] and [b,a]
So for one item you are done. For two items you can switch the order to get the second permutation. For three items you can insert the third item (c) at three location in both of the permutations of the previous set of two permutations. This is actually what you do when going from one to two elements as well i.e. inserting b before and after a.
So it would be useful to have a function insert (ins) which insert an item at all possible locations in a list and return all these lists in a list. So how do you do that. Imagine the following function. We have a single item x and a list where the first item is y (head) and the rest of the list is ys (tail).
ins x (y:ys)
One list where x is inserted in (y:ys) is x:y:ys i.e. x inserted first in the list y:ys. ins x ys is x inserted in ys at all possible locations. Lets take a concrete example.
x = 'c'
(y:ys) = ['a','b'] -- y = 'a' and ys = ['b']
In this case x:y:ys would compute to the following.
x:y:ys -- ['c','a','b']
ins x ys -- ins 'c' ['b'] ==> [['c','b'],['b','c']]
So if you take y in front of each of ins x ys results you will have the rest of the results from ins x (y:ys). This can be expressed as list comprehension.
[y:res | res <- ins x ys]
So ins can really be implemented by taking x:y:ys as a first result and then insert y in front of the recursive result from ins x ys i.e. [y:res | res <- ins x ys]. The only thing to do is to define a base case for the recursion to finish. Insert x in a empty list is the most basic case which is trivially implemented.
ins x [] = [[x]]
So now we can understand why ins can be implemented as follows.
ins x [] = [[x]]
ins x (y:ys) = (x:y:ys):[y:res | res <- ins x ys]
From the examples of permutations above I would implement permute as follows. I also added a small main to test the function.
permute :: [a] -> [[a]]
permute [] = [[]]
permute (x:[]) = [[x]]
permute (x:y:[]) = [[x,y],[y,x]]
permute (x:ys) = concatMap (ins x) (permute ys)
main = do print $ permute ['a','b','c']
concatMap applies ins x on each list element of permute ys and concatenates its results. As ins x on a list produce a list of lists the concatenation of concatMap is used to collect the results as a single list.
runhaskell Permute.hs
["abc","bac","bca","acb","cab","cba"]
Because ins can handle the case where ys is empty in permute ys, the cases where the list parameter to permute has one or two elements is not required for the recursion to finalize. The simplified solution is as follows. ins is also implemented as a sub-function of permute.
permute :: [a] -> [[a]]
permute [] = [[]]
permute (x:ys) = concatMap (ins x) (permute ys) where
ins x [] = [[x]]
ins x (y:ys) = (x:y:ys):[y:res | res <- ins x ys]
main = do print $ permute ['a','b','c']
The original solution where foldr is used, instead of a recursive call to permute, is bit more difficult to grasp, but equivalent.