调试类型错误在哈斯克尔

Question

我正在尝试编写一个函数，从 Haskell 中的列表中返回所有排列：

perms :: [a] -> [[a]]
perms [] = [[]]
perms xs = map (y -> concat_each y (perms (list_without y xs))) xs
list_without :: (Eq a) => a -> [a] -> [a]
list_without x xs =
filter (y -> not (y==x)) xs
concat_each :: a -> [[a]] -> [[a]]
concat_each x xs =
map (y -> x:y) xs

我认为在第 3 行会发生什么： y 是a和 x 是[a]，所以 list_without y xs 是[a].

因此，烫发(list_without...(是[[a]]

所以concat_each y(烫发...(变得a和[[a]]，导致[[a]]

所以地图的功能是a -> [[a]]的，一切都应该没问题。

但是编译器似乎有不同的看法：

Couldn't match type `a' with `[a]'
`a' is a rigid type variable bound by
the type signature for perms :: [a] -> [[a]]
at C:UsersPhilippDesktoppermutations.hs:1:10
Expected type: [a]
Actual type: [[a]]
Relevant bindings include
y :: a (bound at permutations.hs:3:18)
xs :: [a] (bound at permutations.hs:3:7)
perms :: [a] -> [[a]]
(bound at permutations.hs:2:1)
In the expression: concat_each y (perms (list_without y xs))
In the first argument of `map', namely
`( y -> concat_each y (perms (list_without y xs)))'

如何正确调试此错误消息？我真的不知道从哪里开始检查我的类型。

Answer 1

map :: (x -> y) -> [x] -> [y]

你给map的第一个参数有类型a -> [[a]]，即x = a和y = [[a]]所以

:: [x] -> [  y  ]
map (y -> ...) :: [a] -> [[[a]]]
--  ^      ^^^^^
-- x = a,  y = [[a]]

---

在这种情况下，该map (y -> ...) xs的结果是一个列表，其中每个元素对应于以xs中的固定元素y开头的排列。最后，您不在乎排列以哪个元素开头;你可以忘记使用concat分离：

perms = concat (map (y -> ...) xs)
-- or
perms = concatMap (y -> ...) xs
-- or
perms = xs >>= y -> ...