Get all permutations of a list in Haskell

Question

I'm trying to do this from scratch, without the use of a library outside the standard lib. Heres my code:

permutations :: [a] -> [[a]]
permutations (x:xs) = [x] : permutations' xs
    where permutations' (x:xs) = (:) <$> [x] <*> split xs
            split l = [[x] | x <- l]

The problem is that this only produces one fork of the non-deterministic computation. Ideally I'd want

(:) <$> [x] <*> ((:) <$> [x] <*> ((:) <$> [x] <*> ((:) <$> [x] <*> xs)))

But I can't find a way to do this cleanly. My desired result is something like this:

permutations "abc" -> ["abc", "acb", "bac", "bca", "cab", "cba"]

How do I do this?

Answer 1

Maybe you should use existing code:

import Data.List
permutations [1,2,3,4]

Answer 2

For a simple implementation without considering duplications in the input

permutations :: Eq a => [a] -> [[a]]
permutations [] = [[]]
permutations as = do a <- as
                     let l = delete a as
                     ls <- permutations l
                     return $ a : ls

Test:

λ> permutations [1,2,3]
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
λ> permutations "abc"
["abc","acb","bac","bca","cab","cba"]
λ> 

Algorithm Reference