Why the monad laws matter

The three laws

The type of >>= can be satisfied by many implementations, but only some of them behave like a sequence of steps. The three laws name the behaviour, in the notation of the class:

pure x >>= f == f x -- left identity m >>= pure == m -- right identity (m >>= f) >>= g == m >>= (\x -> f x >>= g) -- associativity

In words: pure adds a step that does nothing, pure at the end changes nothing, and grouping the steps does not change the answer. The compiler does not check the laws, so they are a promise the instance makes to every function written with the class. The whole point of do notation is that it reads like an imperative sequence, and that reading is only valid when the three laws hold.

Checking the laws for Maybe

A law with a free function cannot be proved by one example, but a few examples show the shape and catch a typo. The program writes each law as a function of the pieces and prints the result for Maybe, including the failing branch:

module Main (main) where leftIdentity :: Eq b => (a -> Maybe b) -> a -> Bool leftIdentity f x = (pure x >>= f) == f x rightIdentity :: Eq a => Maybe a -> Bool rightIdentity value = (value >>= pure) == value associative :: Eq c => Maybe a -> (a -> Maybe b) -> (b -> Maybe c) -> Bool associative value f g = (value >>= f >>= g) == (value >>= \x -> f x >>= g) half :: Int -> Maybe Int half n | even n = Just (n `div` 2) | otherwise = Nothing main :: IO () main = do print (leftIdentity half 8) print (leftIdentity half 7) print (rightIdentity (Just (3 :: Int))) print (rightIdentity (Nothing :: Maybe Int)) print (associative (Just (8 :: Int)) half half) print (associative (Just (10 :: Int)) (\n -> Just (n + 1)) half)

ghc -Wall -O1 -o laws laws.hs
./laws

True
True
True
True
True
True

Six True lines are the expected answer, including the two that pass through Nothing: the laws must hold for a failure as well, and they do, because a failure short-circuits both sides in the same way. Note that the last two lines are the same quantity grouped differently: the first binds f and then g, the second builds the composed step from the right, and the results agree.

The left and right identity

The two identities are the reason a do block can start with a plain value and end with a plain value without changing the meaning:

do x <- pure 3 -- left identity: pure 3 >>= \x -> ... f x do y <- action -- right identity: action >>= \y -> pure y pure y

Without the left law, pure could do something extra and the first block would differ from a plain call to f. Without the right law, a trailing pure y could do something extra and every do block that returns a value would change meaning when it is refactored. The laws are what make these rewrites safe, and a reader of the code relies on them without thinking about it.

A broken instance

A counter that increments on every bind is a small, type-correct example of an instance that breaks both identities. The constructor holds a value and a count, and >>= adds one to the count of every step:

module Main (main) where newtype Box a = Box (a, Int) deriving (Eq, Show) instance Functor Box where fmap f (Box (x, n)) = Box (f x, n) instance Applicative Box where pure x = Box (x, 0) Box (f, n) <*> Box (x, m) = Box (f x, n + m) instance Monad Box where Box (x, n) >>= f = let Box (y, m) = f x in Box (y, n + m + 1) step :: Int -> Box Int step x = Box (x + 1, 0) main :: IO () main = do print (pure (3 :: Int) >>= step) print (step 3) print (Box (3 :: Int, 0) >>= pure) print (Box (3 :: Int, 0))

ghc -Wall -O1 -o broken broken.hs
./broken

Box (4,1)
Box (4,0)
Box (3,1)
Box (3,0)

The first pair is the left identity: pure 3 >>= step should be step 3, and it differs in the count, because the bind added one. The second pair is the right identity: Box (3, 0) >>= pure should be Box (3, 0), and it is not. The program compiles and runs; only the laws tell you that the instance is wrong, which is why a library documents its laws and a test suite checks them with generated inputs when QuickCheck is available.

What a broken law breaks

The damage is not abstract. A computation written with the broken instance changes its answer when it is refactored:

hlint knows the three laws and rewrites pure x >>= f to f x and m >>= pure to m when it sees them, which is a quick way to notice that a piece of code is only a law in disguise. The instances in base and the libraries hold the laws; a hand-written one is your promise to keep them.

Exercises

  1. Check the three laws for the list monad with a function such as \x -> [x, x + 1].
  2. Break the association law instead of the identities and show the two results.
  3. Explain why the broken Box is still a valid Functor and Applicative and only the Monad instance is wrong.
  4. Write a helper lawful :: Box a -> Bool that checks the right identity and run it on both boxes above.
  5. Rewrite the first line of the broken program to the form hlint would produce and compare the printout.
  6. Explain what do notation assumes about the grouping of the steps.

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. What does the left identity law say?

    Answer

    pure x >>= f == f x

    The left identity says that pure adds no step before f.

  2. What does the right identity law say?

    Answer

    m >>= pure == m

    A trailing pure does not change the computation.

  3. Which law lets you regroup a chain of binds?

    Answer

    Associativity

    Associativity says the two groupings of a chain of binds agree.

  4. What does this program print? module Main (main) where main :: IO () main = print ((Just (3 :: Int) >>= \x -> Just (x + 1)) == Just 4)

    Answer

    True

    The bind applies the function to 3 and gives Just 4, so the comparison is True.

  5. What does the broken Box instance add to every bind?

    Answer

    One to the count

    The count is n + m + 1, and the extra one is what breaks both identities.

  6. What does pure 3 >>= step print for the broken Box when step 3 is Box (4, 0)?

    Answer

    Box (4,1)

    The bind adds one to the count, so the left identity fails by one.

  7. Who checks that a Monad instance follows the laws?

    Answer

    Nobody automatically: the compiler checks the types, and tests or review check the laws

    The laws are not part of the type system, so they are a promise the instance makes.

  8. What does this program print? module Main (main) where main :: IO () main = print ((Just (2 :: Int) >>= pure) == Just 2)

    Answer

    True

    The right identity holds for Maybe: binding pure at the end changes nothing.

  9. Why does a broken law make refactoring unsafe?

    Answer

    A rewrite that is valid for a lawful monad can change the result

    The laws are exactly the rewrites a reader and a tool assume, so without them a rewrite can change behaviour.

  10. Which law is used when a do block ends with pure y?

    Answer

    The right identity

    Dropping the trailing pure is the right identity law applied to the action before it.

The code on this page was built with GHC 9.10.3 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev