Haskell's "permutations" function defined oddly

Question

If I wanted to find the permutations of a list, I know that the number of permutations is given by the multinomial coefficient. For example, "MISSISSIPPI" has 11 letters, 'S' appears 4 times, 'I' appears 4 times, 'P' appears twice and 'M' appears once. So the number of permutations of "MISSISSIPPI" is equal to 11!/(4!4!2!) = 34650.

If I load up GHCi and write:

ghci> import Data.List
ghci> permutations [1,2,3]

It will return

[[1,2,3],[2,1,3],[3,2,1],[2,3,1],[3,1,2],[1,3,2]]

as expected.

But if I write

ghci> permutations [1,0,0]

it will now return

[[1,0,0],[0,1,0],[0,0,1],[0,0,1],[0,1,0],[1,0,0]]

... which is very disappointing. As there are three elements, and two of them occur twice, one would hope for there only to be 6!/2! = 3 permutations, namely

[[1,0,0],[0,1,0],[0,0,1]]

rather than the six generated by treating each element of the list as distinct.

1) Why does Haskell implement "permutations" in the way described above (i.e. treating all elements of a list as distinct?)

2) Are there any standard library functions that calculate the permutations of a list in the "true" sense of permutations?

Answer 1

Remember that permutations has type

permutations :: [a] -> [[a]]

That means that it satisfies the free theorem

permutations . map f = (map . map) f . permutations

for all functions f. Since you can change the elements of the argument list arbitrarily without affecting the structure of the result list, permutations must really be a function on the indices of the original list, rather than the elements.

So what permutations is really doing --- what it must do --- is calculate all permutations of the indices of the argument list, then apply each of those permutations to the list and return the results. (I.e.,

permutations xn = (map . map) (xn!!) (permutations [0..length xn - 1])

for finite xn).

Mathematical appendix:

Since

xn = map (xn!!) (zipWith const [0..] xn)

for all xn, any function with permutations's type must satisfy

permutations xn
  = permutations (map (xn!!) (zipWith const [0..] xn)
  = (map . map) (xn!!) (permutations (zipWith const [0..] xn))

by the equation above for xn and the free theorem for permutations. So any function with permutations's type must operate only on the indices of the input list[1].

[1] Technically you can violate this by using seq. But only for input lists that contain undefined as an element, which isn't true in your case.

Answer 2

1 - Why does Haskell implement "permutations" in the way described above (i.e. treating all elements of a list as distinct?)

It is a design question and should be studied in deep. permutation treats the elements of the list as if they were all different from each other. You can do permutations [0, 0, 0] and you'll yet get a list of lists of size 6.

2 - Are there any standard library functions that calculate the permutations of a list in the "true" sense of permutations?

Yes, you have the Math.Combinat.Permutations, but you can easily create your own definition filtering the unique combinations with a complexity of O(n * log n) using sets, taking account that nub is known by being very slow:

module Main where
import Data.List (permutations)
import qualified Data.Set as Set

nubOrd :: (Ord a) => [a] -> [a]
nubOrd xs = go Set.empty xs where
  go s (x:xs)
   | x `Set.member` s = go s xs
   | otherwise        = x : go (Set.insert x s) xs
  go _ _              = []

permutations' :: (Ord a) => [a] -> [[a]]
permutations' = nubOrd . permutations

Where permutations' [1, 0, 0] gives [[1, 0, 0], [0, 1, 0], [0, 0, 1]].

Answer 3

Why does Haskell implement "permutations" in the way described above (i.e. treating all elements of a list as distinct?)

Because otherwise, the type would have to be:

permutations :: Eq a => [a] -> [[a]]

and then we could permute only things that have an Eq instance. But I remember I had something like

permutations [(+), subtract, (*), (/)]

in some Project Euler code ....

Answer 4

Here is a slightly rearranged Daniel Fischer's solution:

inserts :: [a] -> [a] -> [[a]]
inserts (x:xs) (y:ys) = map (x:) (inserts xs (y:ys)) ++ map (y:) (inserts (x:xs) ys)
inserts  xs     ys    = [xs ++ ys]

uniqPerms :: Ord a => [a] -> [[a]]
uniqPerms = foldM inserts [] . group . sort