CODEWITHSUNDEEP
haskellfunctor
Panos
Panos

Reputation: 627

Does the First Functor Law follow from the Second?

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

Upvotes: 10

Views: 608

Answers (2)

shachaf
shachaf

Reputation: 8930

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.

Upvotes: 10

Philip JF
Philip JF

Reputation: 28539

No 

data Break a = Yes | No

instance Functor Break where
   fmap f _ = No

clearly the second law holds

   fmap (f . g) = const No = const No . fmap g = fmap f . fmap g

but, the first law does not. The problem with your argument is not all x' are of the form fmap f x

Upvotes: 13

Related Questions