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

Question

我正在关注来自https://github.com/NICTA/course的List练习

以下代码片段是从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'是由map ::(a - > b) - > List的类型签名绑定的刚性类型变量a - >列表b

我正在努力实现以下目标:

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

Answer 1

首先,解释错误信息:你不能filter在你的定义中使用,因为

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

与常规的Prelude列表有关,而不是你List的 - 即[a]不是List a.错误消息的出现是因为filter预计a在

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

作为一个东西的列表,但你提供的签名声明这a是一个List东西.类似地filter返回一个Prelude列表的东西,但签名要求它返回List一些东西.

mapfor 的自然实现List将区分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,因为你的前提都是约束要求ListS代表平等,因此,他们的元素可以进行测试. f没有使用,所以它最终只是一个'可能是任何东西'参数,在这里t.

当然,如果你有自己filterList的Lists,那么它也会出现问题

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)

这个函数的作用是从List of Lists中删除null元素,比如Prelude.filter (not . Prelude.null).同样,您定义的实际功能(没有签名)Nil从列表的前奏列表中删除了列表.