Permutations.hs

permutations :: [a] -> [[a]]
permutations [] = [[]]
permutations (x:xs) = concatMap (insertions x) (permutations xs)
    where
        insertions x [] = [[x]]
        insertions x zs@(y:ys) = (x:zs) : [y:ins | ins <- insertions x ys]