Monad Laws

Welcome to the final part of our series on monads in Haskell! So far, we've learned most of the concrete details you'll need in order to use monads in your programs. But there's still one more abstract concept we should cover in relation to all these structures. This is the notion of structural “laws”. These are rules that these typeclasses should to follow to meet other programmers expectations about our code.

Each of the structures we've discussed has its own set of laws. If you need to review anything about these structures and the typeclass functions that comprise them, be sure to review part 1, part 2 and part 3 of this course.

Once you understand all this, you'll be all ready to kick your Haskell learning into high gear! Download our Production checklist for some ideas about libraries you can learn to perform common tasks.

If you've been following along with the series repository, you can take a look at the code for this section in this final module. There's a short example at the bottom where you can play around with QuickCheck and the Functor laws.

Life without Laws

Remember Haskell represents each of our abstract 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

That wraps up our series on monads! Remember that if any of these concepts are still fuzzy, don't hesitate to go back and check out some of the earlier parts of the series. We started by learning the basics about functors, applicative functors and monads. Then we went more in depth on monads and saw some of the more useful ones like the Reader, Writer, and State monads. Then we learned how to combine these together by using monad transformers.

Now that you understand perhaps the most important concept in Haskell, the sky is your limit! Check out our Production Checklist to learn about the many libraries you can use to supercharge your Haskell!