为什么我在自定义类型上实现的地图不正确?

Question

我正在关注 https://github.com/NICTA/course 的列表练习

以下代码片段从部分 https://github.com/NICTA/course/blob/master/src/Course/List.hs 复制而来

data List t =
Nil
| t :. List t
deriving (Eq, Ord)
map ::
(a -> b)
-> List a
-> List b
map f a = filter (listElement -> listElement /= Nil) a

上面给了我以下错误：无法将预期的类型"b"与实际类型"列表 t0"匹配 "b"是一个刚性类型变量，受映射的类型签名约束：
： (

a -> b) -> 列表 a -> 列表 b我正在尝试实现以下目标：

>>> map (+10) (1 :. 2 :. 3 :. Nil)
[11,12,13]

Answer 1

首先，解释错误消息：您不能在定义中使用filter，因为

filter :: (a -> Bool) -> [a] -> [a]

与常规的前奏列表有关，而不是您的List- 即[a]不是List a.出现错误消息是因为filter期望a

map f a = filter (listElement -> listElement /= Nil) a

是某物的列表，但您提供的签名声明a是某物的List。类似地，filter返回某物的 Prelude 列表，但签名要求它返回某物的List。

Listmap的自然实现将区分您在类型声明中给出的List情况，即它将"模式匹配"：

mapList ::
(a -> b)
-> List a
-> List b
mapList f Nil = Nil
mapList f (t :. ls) = f t :. mapList f ls

请注意，您编写的程序是完全有效的，它只是与您给它的签名冲突：

ghci> let mapX f a = filter (listElement -> listElement /= Nil) a
ghci> :t mapX
mapX :: Eq a => t -> [List a] -> [List a]

Eq约束是必需的，因为您预先假定List要测试相等性，因此它们的元素可以相等。 没有使用f，所以它最终只是一个"可以是任何东西"参数，这里t.

当然，如果您有自己的ListfilterList，它也会进行类型检查

ghci> let filterList pred Nil = Nil; filterList pred (a :. as) = if pred a then a :. filterList pred as else filterList pred as
ghci> :t filterList
filterList :: (t -> Bool) -> List t -> List t
ghci> let mapY f a = filterList (listElement -> listElement /= Nil) a
ghci> :t mapY
mapY :: Eq a => t -> List (List a) -> List (List a)

此函数的作用是从列表列表中删除空元素，例如Prelude.filter (not . Prelude.null)。同样，您定义的实际函数(不带签名)从列表的前奏列表中删除了Nil列表。

Answer 2

filter (listElement -> listElement /= Nil) a

这是类型错误的源。如果你的实现filter遵循合理的路径，listElement应该是a的一个元素，也就是说，由于a具有类型List a，因此它是类型a。您将它的不等式与类型List a的Nil进行比较。