список перестановок в haskell

Question

Итак, я новичок в haskell, и я играл с ним некоторое время. Я хочу получить свою функцию, которая выводит все перестановки списков для работы. Я написал 2 реализации, один работает хорошо, другой дает мне ошибку. Любая помощь была бы потрясающей.

Это первая (работа) реализация:

permute [] = [[]] 
permute xs = [y| x <- xs, y <- map (x:) $ permute $ delete x xs] 

Это один дает мне ошибку:

permute [] = [[]] 
permute xs = map (\x -> map (x:) $ permute $ delete x xs) xs 

и вот сообщение об ошибке:

Occurs check: cannot construct the infinite type: t0 = [t0] 
Expected type: [t0] 
Actual type: [[t0]] 
In the expression: map (x :) $ permute $ delete x xs 
In the first argument of `map', namely 
`(\ x -> map (x :) $ permute $ delete x xs)' 

Я Если бы кто-то мог объяснить, почему я получаю эту ошибку. Спасибо

Answer 1

Используйте сигнатуры типов, чтобы облегчить жизнь компилятора.

permute :: Eq a => [a] -> [[a]], и теперь мы имеем:

Couldn't match type `a' with `[a]' 
    `a' is a rigid type variable bound by 
     the type signature for permute :: Eq a => [a] -> [[a]] 
     at perm.hs:4:1 
Expected type: [a] 
    Actual type: [[a]] 
In the expression: map (x :) $ permute $ xs 
In the first argument of `map', namely 
    `(\ x -> map (x :) $ permute $ xs)' 

Таким образом, кажется, что мы должны использовать concatMap вместо map.

permute :: Eq a => [a] -> [[a]] 
permute [] = [[]] 
permute xs = concatMap (\x -> map (x:) $ permute $ delete x xs) xs 

Answer 2

Вы можете использовать что-то вроде этого, если вы не уверены, что у вас есть тип deriving Eq (reqiured использовать delete):

perms :: [a] -> [[a]] 
perms [] = [[]] 
perms [a] = [[a]] 
perms [a,b] = [[a,b],[b,a]] 
perms xs = concatMap f [0..length xs - 1] where 
    f i = map ((xs!!i):) $ perms $ exclude i xs 
    exclude n xs = take (n) xs ++ drop (n+1) xs 

Может быть, это излишеством :)