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:
- Pulling a common tail into a helper changes the number of binds, and with this instance the count changes too.
- Replacing a do block that ends in pure with the expression it returns adds a step.
- A loop written once with >>= and once with a fold over a list gives two different counts for the same work.
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
- Check the three laws for the list monad with a function such as \x -> [x, x + 1].
- Break the association law instead of the identities and show the two results.
- Explain why the broken Box is still a valid Functor and Applicative and only the Monad instance is wrong.
- Write a helper lawful :: Box a -> Bool that checks the right identity and run it on both boxes above.
- Rewrite the first line of the broken program to the form hlint would produce and compare the printout.
- 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.
-
What does the left identity law say?
Answer
pure x >>= f == f xThe left identity says that pure adds no step before f.
-
What does the right identity law say?
Answer
m >>= pure == mA trailing pure does not change the computation.
-
Which law lets you regroup a chain of binds?
Answer
Associativity
Associativity says the two groupings of a chain of binds agree.
-
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.
-
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.
-
What does
pure 3 >>= stepprint for the broken Box whenstep 3isBox (4, 0)?Answer
Box (4,1)The bind adds one to the count, so the left identity fails by one.
-
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.
-
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.
-
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.
-
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