Haskell prove List satisfies two Functor laws
Show Functor List or [] that satisfied two Functor laws:
class Functor f where
fmap:: (a -> b) -> f a -> f b
instance Functor [] where
fmap g [] = [] -- g = (a -> b), [] = f a
fmap g (x:cx) = (g x):(fmap g cx)
Two Functor laws:
1. fmap id = id
2. fmap (f . g) = (fmap f).(fmap g)
Prove:
1. fmap id = id
fmap id [] = [] (from def. of fmap)
id [] = [] (from def. of identity function)
=> fmap id [] = id []
=> fmap id = id
fmap id (x:cx) = (id x):(fmap id cx)
(x:cx) = (x:cx)
=> fmap id = id
2. fmap(f . g) = (fmap f).(fmap g)
fmap(f . g) (x:cx) = (fmap f) . (fmap g) (x:cx)
(fmap f)(fmap g x:cx)
(fmap f)((g x:fmap g cx))
(f g x): (fmap f (fmap g cx))
(f (g x)):(fmap f (fmpa g cx))
fmap f (g x : fmap g cx) = (f g x): (fmap f (fmap g cx))
fmap f (fmap g x:cx)
(fmap f) . (fmap g) (c:cx)
=> fmap (f . g) = (fmap f).(fmap g)
1. 2. => List or [] is Functor