module List where -- permutations xs returns the list of all permutations of xs. -- e.g., permutations "abc" == ["abc","bac","bca","acb","cab","cba"] permutations :: [a] -> [[a]] permutations [] = [[]] permutations (x:xs) = [zs | ys <- permutations xs, zs <- interleave x ys ] where interleave :: a -> [a] -> [[a]] interleave x [] = [[x]] interleave x (y:ys) = [x:y:ys] ++ map (y:) (interleave x ys)