haskell列表排列

Question

所以我是新來的哈斯克爾，我一直在玩它一段時間了。我想讓我的函數輸出所有的列表排列工作。我寫了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 

也許是矯枉過正:)