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 

也许是矫枉过正:)