Alex Rivera | Logout

Does the First Functor Law follow from the Second?

Asked 2012-11-24T07:40:55.800
10

According to this question the 2nd Functor law is implied by the 1st in Haskell: 

1st Law: fmap id = id
2nd Law : fmap (g . h) = (fmap g) . (fmap h)

Is the reverse true? Starting from 2nd law, and setting g equal to id, can I reason the following and get the 1st law?

fmap (id . h) x = (fmap id) . (fmap h) x
fmap h x = (fmap id) . (fmap h) x
x' = (fmap id) x'
fmap id = id

where x' = fmap h x

haskell functor
Edit
Report

1 Answer

10

No, it only works in one direction.

Consider this Functor instance:

data Foo a = Foo Int a

instance Functor Foo where
    fmap f (Foo _ x) = Foo 5 (f x)

It satisfies the second law but not the first one.

The last step in your proof is invalid -- you showed that fmap id x' = x', but this is restricted to x's that are returned from fmap in the first place, not arbitrary values.

answered 2012-11-24T07:59:36.540

Your Answer