Learn You a Haskell for Great Good! - Miran Lipovaca [101]
We figure out how the second law holds for some type by looking at the implementation of fmap for that type and then using the method that we used to check if Maybe obeys the first law. So, to check out how the second functor law holds for Maybe, if we use fmap (f . g) over Nothing, we get Nothing, because calling fmap with any function over Nothing returns Nothing. If we call fmap f (fmap g Nothing), we get Nothing, for the same reason.
Seeing how the second law holds for Maybe if it’s a Nothing value is pretty easy. But how about if it’s a Just value? Well, if we use fmap (f . g) (Just x), we see from the implementation that it’s implemented as Just ((f . g) x), which is Just (f (g x)). If we use fmap f (fmap g (Just x)), we see from the implementation that fmap g (Just x) is Just (g x). Ergo, fmap f (fmap g (Just x)) equals fmap f (Just (g x)), and from the implementation, we see that this equals Just (f (g x)).
If you’re a bit confused by this proof, don’t worry. Be sure that you understand how function composition works. Many times, you can intuitively see how these laws hold because the types act like containers or functions. You can also just try them on a bunch of different values of a type and be able to say with some certainty that a type does indeed obey the laws.
Breaking the Law
Let’s take a look at a pathological example of a type constructor being an instance of the Functor type class but not really being a functor, because it doesn’t satisfy the laws. Let’s say that we have the following type:
data CMaybe a = CNothing | CJust Int a deriving (Show)
The C here stands for counter. It’s a data type that looks much like Maybe a, but the Just part holds two fields instead of one. The first field in the CJust value constructor will always have a type of Int, and it will be some sort of counter. The second field is of type a, which comes from the type parameter, and its type will depend on the concrete type that we choose for CMaybe a. Let’s play with our new type:
ghci> CNothing
CNothing
ghci> CJust 0 "haha"
CJust 0 "haha"
ghci> :t CNothing
CNothing :: CMaybe a
ghci> :t CJust 0 "haha"
CJust 0 "haha" :: CMaybe [Char]
ghci> CJust 100 [1,2,3]
CJust 100 [1,2,3]
If we use the CNothing constructor, there are no fields. If we use the CJust constructor, the first field is an integer and the second field can be any type. Let’s make this an instance of Functor so that each time we use fmap, the function is applied to the second field, whereas the first field is increased by 1.
instance Functor CMaybe where
fmap f CNothing = CNothing
fmap f (CJust counter x) = CJust (counter+1) (f x)
This is kind of like the instance implementation for Maybe, except that when we do fmap over a value that doesn’t represent an empty box (a CJust value), we don’t just apply the function to the contents; we also increase the counter by 1. Everything seems cool so far. We can even play with this a bit:
ghci> fmap (++"ha") (CJust 0 "ho")
CJust 1 "hoha"
ghci> fmap (++"he") (fmap (++"ha") (CJust 0 "ho"))
CJust 2 "hohahe"
ghci> fmap (++"blah") CNothing
CNothing
Does this obey the functor laws? In order to see that something doesn’t obey a law, it’s enough to find just one counterexample:
ghci> fmap id (CJust 0 "haha")
CJust 1 "haha"
ghci> id (CJust 0 "haha")
CJust 0 "haha"
As the first functor law states, if we map id over a functor value, it should be the same as just calling id with the same functor value. Our example demonstrates that this is not true for our CMaybe functor. Even though it’s part of the Functor type class, it doesn’t obey this functor law and is therefore not a functor.
Since CMaybe fails at being a functor even though it pretends to be one, using it as a functor might lead to some faulty code. When we use a functor, it shouldn’t matter if we first compose a few functions and then map them over the functor