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(烫发...)获取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:\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 -> ...