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 ]
Andy Fugard wrote:
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.
Definitely list comprehensions! I digged out some old code:
module Perms where
Permutations.
perms :: [a] -> [[a]] perms [] = [ [] ] perms (a : x) = [ z | y <- perms x, z <- insertions a y ]
insertions :: a -> [a] -> [[a]] insertions a [] = [ [a] ] insertions a x@(b : y) = (a : x) : [ b : z | z <- insertions a y ]
Using deletions instead of insertions; generates the permutations in lexicographic order, but is a bit slower.
perms' :: [a] -> [[a]] perms' [] = [ [] ] perms' x = [ a : z | (a, y) <- deletions x, z <- perms' y ]
deletions :: [a] -> [(a, [a])] deletions [] = [] deletions (a : x) = (a, x) : [ (b, a : y) | (b, y) <- deletions x ]
Cheers, Ralf
At 13:43 14/05/01 +0200, Ralf Hinze wrote:
Andy Fugard wrote:
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.
Definitely list comprehensions! I digged out some old code:
[ ... ] Thanks for the quick response; that's much nicer! I think I'll have a look at list comprehensions.... Cheers, Andy
participants (2)
-
Andy Fugard -
Ralf Hinze