permutations2.hs

split :: [a] -> [[a]]
split xs = f ([], []) xs
  where f :: ([a], [[a]]) -> [a] -> [[a]]
        f (seen, acc) [] = acc
        f (seen, acc) (x:xs) = f (seen ++ [x], acc ++ [x:(seen ++ xs)]) xs

perms :: [a] -> [[a]]
perms [] = [[]]
perms xs = foldl f [] $ split xs
      where f :: [[a]] -> [a] -> [[a]]
            f acc (x:xs) = acc ++ (map (x:) (perms xs))

main = print $ perms "abc"