Haskell's "permutation" function defined weird

Question

If I wanted to find permutations in the list, I know that the number of permutations is specified using the polynomial. For example, “MISSISSIPPI” has 11 letters, “S” appears 4 times, “I” appears 4 times, “P” appears twice, and “M” appears once. Therefore, the number of permutations of "MISSISSIPPI" is 11! / (4! 4! 2!) = 34650.

If I download GHCi and write:

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

He will return

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

as was expected.

But if I write

 ghci> permutations [1,0,0] 

now he will return

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

... which is very disappointing. Since there are three elements, and two of them occur twice, it is hoped that there will only be 6! / 2! = 3, namely

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

not six created by treating each list item as a separate one.

1) Why does Haskell implement “permutations” in the manner described above (that is, treating all elements of the list as different?)

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

Answer 1

Remember that permutations is of type

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

This 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 really should be a function of the indices of the original list, not the elements.

So what permutations really does - what it should do - computes all permutations of the indexes of the argument list, then applies each of these permutations to the list and returns the results. (I.e.,

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

for finite xn ).

Math application:

FROM

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

for all xn , any function with the permutations type must satisfy

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

the above equation for xn and the free theorem for permutations . Therefore, any function with the permutations type should work only on the indices of the input list [1].

[1] Technically, you can break this by using seq . But only for input lists containing undefined as an element, which is not appropriate for your case.

Answer 2

1 - Why does Haskell implement “permutations” in the manner described above (ie, treats all list items as different?)

This is a design issue and should be studied deeply. permutation treats list items as if they were all different from each other. You can do permutations [0, 0, 0] , and you still get a list of lists of size 6 .

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

Yes, you have Math.Combinat.Permutations , but you can easily create your own filtering of unique combination definitions with O(n * log n) complexity using sets, given that nub is famous for 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 xs) 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 manner described above (that is, treating all elements of the list as different?)

Otherwise, the type must be:

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

and then we can rearrange only those things that have an instance of Eq. But I remember that I had something like

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

in the Euler project code ....

Answer 4

Here is a slightly redesigned Daniel Fischer 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