Why is my implementation of a map on a custom type not correct?
I'm following the List exercise from https://github.com/NICTA/course
The below snippet copied from part of 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
The above gives me the below error:
Couldn't match expected type 'b' with actual type 'List t0' 'b' is a rigid type variable bound by the type signature for map :: (a -> b) -> List a -> List b
I'm trying to achieve the below:
>>> map (+10) (1 :. 2 :. 3 :. Nil)
[11,12,13]
First, to explain the error message: you can't use filter in your definition, since
filter :: (a -> Bool) -> [a] -> [a]
has to do with regular Prelude lists, not your List s -- ie [a] not List a . The error message arises because filter expects a in
map f a = filter (listElement -> listElement /= Nil) a
to be a list of something, but the signature you supplied declares that a is a List of something. Similarly filter returns a Prelude list of something, but the signature requires that it return a List of something.
The natural implementation of map for List would distinguish the cases of List that you gave in the type declaration, that is, it would "pattern match":
mapList ::
(a -> b)
-> List a
-> List b
mapList f Nil = Nil
mapList f (t :. ls) = f t :. mapList f ls
Note that the program you wrote is perfectly valid, it just conflicts with the signature you gave it:
ghci> let mapX f a = filter (listElement -> listElement /= Nil) a
ghci> :t mapX
mapX :: Eq a => t -> [List a] -> [List a]
The Eq constraint is required because you presuppose that List s be tested for equality and thus that their elements can be. f is not used, so it just ends up as a 'could be anything' parameter, here t .
Of course, if you have your own filterList for List s it will also typecheck
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)
What this function does is delete null elements from a List of Lists, like Prelude.filter (not . Prelude.null) . Similarly, the actual function you defined (without the signature) deleted Nil Lists from a Prelude list of your Lists.
filter (listElement -> listElement /= Nil) a
Here's the source of type error. If your implementation of filter follows reasonable path, listElement should be an element of a , that is, since a has type List a , it is of type a . You compare it for inequality against Nil which is of type List a .
上一篇: 看起来正确的类型签名被拒绝在哪里
下一篇: 为什么我的自定义类型的地图实现不正确？