0

所以我是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)'

如果有人能解释我为什么会收到此错误，我将不胜感激。谢谢

4

2 回答 2

5

使用类型签名使编译器的工作更轻松。

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
于 2012-07-06T09:04:12.480 回答
0

如果你不确定你有一个类型deriving Eq（需要使用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

也许这是一个矫枉过正:)

于 2017-07-03T16:43:11.433 回答