Obey the (Type) Laws!

We should now have a decent grasp on functors, applicative functors, and monads. Be sure to check these articles out if you need a refresher! Now we understand the concepts, so it’s time to learn the laws around them.

Remember Haskell represents each of these mathematical classes by a type class. Each of these type classes has one or two main functions. So, as long as we implement those functions and it type checks, we have a new functor/applicative/monad, right?

Well not quite. Yes, your program will compile and you’ll be able to use the instances. But this doesn't mean your instances follow the mathematical constructs. If they don't, your instances won't fulfill other programmers’ expectations. Each type class has its own “laws”. For instance, let's think back to the GovDirectory type we created in the functor article. Suppose we made a different functor instance than we had there:

data GovDirectory a = GovDirectory {
  mayor :: a,
  interimMayor :: Maybe a,
  cabinet :: Map String a,
  councilMembers :: [a]
}

instance Functor GovDirectory where
  fmap f oldDirectory = GovDirectory {
    mayor = f (mayor oldDirectory),
    interimMayor = Nothing,
    cabinet = f <$> cabinet oldDirectory,
    councilMembers = f <$> councilMembers oldDirectory
  }

As we’ll see, this would violate one of the functor laws. In this case it would not be a true functor. Its behavior would confuse any other programmer trying to use it. We should take care to make sure that our instances make sense. Once you get a feel for these type classes, the likelihood is that the instances you’ll create follow the laws. So don’t sweat it if a few of these are confusing. This article will be very math-y, and we won’t dwell too much on the concepts. You can understand and use these classes without knowing these laws by heart. So without further ado, let’s dive into the laws!

Functor Laws

There are two functor laws. The first is an identity law. We’ll see some variation of this idea for each of the type classes. Remember how fmap "maps" a function over our container. If we map the identity function over a container, the result should be the same container object:

fmap id = id

In other words, our functor should not be applying any extra changes or side effects. It should only apply the function. The second law is a composition law. It states our functor implementation should not break the composition of functions:

fmap (g . f) = fmap g . fmap f

-- For reference, remember the type of the composition operator:
(.) :: (b -> c) -> (a -> b) -> (a -> c)

On one side we compose two functions, and map the resulting function over our container. On the other side, we map the first function, get the result, and map the second function over it. The functor composition law states these outcomes should be identical. This sounds complex. But you don't need to worry about it much. If you break the composition law in Haskell, you'll also likely break the identity law.

Those are the only two laws for functors! So let's move on to applicative functors.

Applicative Laws

Applicative functors are a little more complicated. They have four different laws. The first is easy though. It's another simple identity law. It says:

pure id <*> v = v

On the left side, we wrap the identity function. Then we apply it over our container. The applicative identity law states this should result in an identical object. Simple enough.

The second law is the homomorphism law. Suppose we wrap a function and an object in pure. We can then apply the wrapped function over the wrapped object. Of course, we could also apply the normal function over the normal object, and THEN wrap it in pure. The homomorphism law states these results should be the same.

pure f <*> pure x = pure (f x)

We should see a distinct pattern here. The overriding theme of almost all these laws is that our type classes are containers. The type class function should not have any side effects. All they should do is facilitate the wrapping, unwrapping, and transformation of data.

The third law is the interchange law. It’s a little more complicated, so don’t sweat it too much. It states that the order that we wrap things shouldn’t matter. One on side, we apply any applicative over a pure wrapped object. On the other side, first we wrap a function applying the object as an argument. Then we apply this to the first applicative. These should be the same.

u <*> pure y = pure ($ y) <*> u

The final applicative law mimics the second functor law. It is a composition law. It states that function composition holds across applications within the functor:

pure (.) <*> u <*> v <*> w = u <*> (v <*> w)

The sheer number of laws here can be a little overwhelming. Remember, the instances you make will probably follow the laws! Let’s move on to our final example: monads.

Monad Laws

Monads have three laws. The first two are simple identity laws, like our other classes have had:

return a >>= f = f
m >>= return = m

These are the left and right identities. They state effectively that the only thing the return function is allowed to do is to wrap the object (sound familiar?). It cannot manipulate the data in any way. Our main takeaway from these is that the following code samples are equivalent:

func1 :: IO String
func1 = do
  str <- getLine
  return str

func2 :: IO String
func2 = getLine

The third law is a bit more interesting. It tells us that associativity holds within monads:

(m >>= f) >>= g = m >>= (\x -> f x >>= g)

But we see this third law has a parallel structure to the other composition laws. In the first case, we apply two functions in two steps. In the second case, we compose the functions first, and THEN apply the result. These should be the same.

So in summary, there are two main ideas from all the laws. First, identity should be preserve over wrapper functions, like pure and return. Second, function composition should hold across our structures.

Checking the Laws

As I stated before, most of the instances that you come up with will naturally follow these rules. As you get more experience with the different type classes, this will be even more true. Yet, it also pays to be sure. Haskell has an excellent tool for verifying your instances pass a certain law.

This utility is QuickCheck. It can take any a certain rule, generate many different test cases on the rule, and verify the rule holds. In this section, we’ll run a few tests on our GovDirectory functor instance. We'll see how QuickCheck proves its initial failure, and ultimate success. First we need to implement the Arbitrary type class over our type. We can do this a long as the inner type is also Arbitrary, such as a built-in string type. Then we’ll use all the other Arbitrary instances that exist over our inner types:

instance Arbitrary a => Arbitrary (GovDirectory a) where
  arbitrary = do
    m <- arbitrary
    im <- arbitrary
    cab <- arbitrary
    cm <- arbitrary
    return $ GovDirectory
      { mayor = m
      , interimMayor = im
      , cabinet = cab
      , councilMembers = cm }

Once you have done that, you can write a test case over a particular rule. In this case, we check the identity function for functors:

main :: IO ()
main = quickCheck govDirectoryFunctorCheck

govDirectoryFunctorCheck :: GovDirectory String -> Bool
govDirectoryFunctorCheck gd = fmap id gd == gd

Now let’s test this on the faulty instance we used above. We can see that a particular test will fail:

*** Failed! Falsifiable (after 2 tests):
GovDirectory {mayor = "", interimMayor = Just "\156", cabinet = fromList [("","")], councilMembers = []}

It specifies for us an arbitrary instance that failed the test. Now suppose we correct the instance:

interimMayor = f <$> (interimMayor oldDirectory),

We’ll see the tests pass!

+++ OK, passed 100 tests.

Summary

We've discussed three major type classes: functors, applicative functors, and monads. They all have particular laws their instances should follow. Other programmers who use your code will expect any instances you make to follow these laws. Once you are familiar with the types, you will likely create instances that follow the laws. But if you are unsure, you can use the QuickCheck utility to verify them.

This concludes our series on monads! You should now have all the tools you need to start using them in practice. Remember that they are a difficult concept, and you'll likely have to review them a couple times. But eventually, you'll understand them!

If you're now inspired to get started with Haskell, make sure to check out our free Getting Started Checklist! It'll help kickstart your Haskell experience by helping you through the download process and making your first project with Stack!

If you're up for a bigger challenge, you should get our Recursion Workbook. It's also free! It has a couple chapters of material on recursion and higher order functions. It also has 10 practice problems for you to try out!