Permutations of a list

[Andy Fugard]

Hi all,

I'm currently teaching myself a little Haskell.  This morning I coded the 
following, the main function of which, permutate, returns all the 
permutations of a list.  (Well it seems to at least!)


insertAt :: a -> Int -> [a] -> [a]
insertAt x i xs
     | i < 0 || i > length xs  = error "invalid position"
     | otherwise               = front ++ x:back
       where (front,back) = splitAt i xs

insertAtAll :: a -> (Int,Int) -> [a] -> [[a]]
insertAtAll x (i,j) xs
     | i > j      = error "PRE: i <= j"
     | i == j     = [insertAt x i xs]
     | otherwise  = (insertAt x i xs):(insertAtAll x (i+1,j) xs)

buildPermList :: a -> [[a]] -> [[a]]
buildPermList x xs
     | length xs == 0  = []
     | otherwise       = list ++ buildPermList x (tail xs)
       where list = insertAtAll x (0, length curr) curr;
             curr = head xs

permutate :: [a] -> [[a]]
permutate xs
     | length xs == 0 = [[]]
     | otherwise      = buildPermList (last xs) (permutate (init xs))


and some test runs....

Main> permutate ""
[""]
Main> permutate "a"
["a"]
Main> permutate "ab"
["ba","ab"]
Main> permutate "abc"
["cba","bca","bac","cab","acb","abc"]


My main question is really what facilities of the language I should be 
looking at to make this code more elegant!  As you can see I currently know 
only the basics of currying, and some list operations.

Also regarding the method of generating the permutations; is there a better 
way?  The current is just "Method 1" from Knuth's TAOCP, volume 1 (3rd 
edition), p45-46.


Thanks in advance,

Andy


--
[  Andy Fugard /'andi fju:ga:d/  ]
[  Phone:  +44 (0)7901 603075    ]