haskell - 在 Haskell 中调试类型错误

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]。

perms (list_without ...) 因此是 [[a]]

所以 concat_each y (perms ...) 得到 a 和 [[a]]，结果是 [[a]]

所以 map 的函数是 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:\Users\Philipp\Desktop\permutations.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 的结果是一个列表，其中每个元素对应于以固定元素 y xs 中的。最后，您不关心排列以哪个元素开始；你可以忘记使用 concat 进行分隔:

perms = concat (map (\y -> ...) xs)

-- or

perms = concatMap (\y -> ...) xs

-- or

perms = xs >>= \y -> ...