In this post I want to explain the relationship between trees and the reader monad. In particular, how trees generalize readers.
Consider the type of binary trees with values at the leaves
This is both a functor and a monad –
1 2 3 4 5 6 7 8
We want a way to get a value out of the tree. One way to do this is to pick a direction, either left or right, and then keep taking that branch until you reach a leaf.
1 2 3
There are many different trees
t that all return the same value when you call either
runTree t True or
runTree t False. If two trees
t return the same value under
runTree for all values of the boolean argument, say that
s is equivalent to
t and write
s ~ t.
This satisfies the axioms for an equivalence relation – reflexivity (every tree is equivalent to itself), symmetry (if
s ~ t then
t ~ s) and transitivity (if
r ~ s and
s ~ t then
r ~ t). So it makes sense to consider the set of equivalence classes of binary trees under this relation.
What may be surprising is that the type of “equivalence classes of binary trees” is also a monad. To define the monad we have to define return and bind for it. It’s nontrivial to do this in Haskell, but relatively easy mathematically.
Let C (for class) be the operation that maps a tree to its equivalence class, and R (for representative) be the operation that selects a particular tree from an equivalence class. Then it must be true that C(R(x)) = x. It isn’t true in general R(C(t)) = t, but we will always get a tree that’s equivalent to the one we put in.
We define ‘return a’ for the monad to be the equivalence class C(Leaf a).
To define x ≫= f first choose a representative of x and bind it to the function R ○ f using the normal bind operation for trees. Then take the equivalence class of the resulting tree. Symbolically,
So we have a monad - but what monad is it? Interestingly, it is exactly equivalent to
To see why, note that two trees whose far left branch and far right branch are the same are equivalent (because
runTree either traverses all the way down the left of the tree, or all the way down the right). So specifying an equivalence class of trees just requires specifying a pair of values of type a, i.e. the type a2. This is equivalent to the type 2 → a, which is the same as functions
Bool -> a, which is the same as
Reader Bool a.
Generalizing to all readers
To generalize to arbitrary readers we should consider r-ary trees
Tree r a rather than binary trees – that is, trees that have r branches at each node. To deal with fact that r might be infinite we work with functions
r -> Tree r a, which are equivalent to
(Tree r a)^r, an r-tuple of trees. In Haskell,
Again this is both a functor and a monad
1 2 3 4 5 6 7 8
and again we can write a function
runTree that, given an
r, takes the same branch of the tree repeatedly until it reaches a value:
1 2 3
Consider two trees equivalent if they give the same result when fed to
runTree r, for all values of
r. Then the equivalence class of trees is a monad in the same way as before, and this monad is exactly the
Reader r monad. To make this really obvious we could rename the data type and constructors, and define the
1 2 3 4 5
You can then then use this like any other reader:
1 2 3 4
local function can be defined similarly, in terms of
One reason for thinking of readers as trees rather than using the more familiar definition is that the monadic join operator on trees T maps T ○ T structures of size n to T structures of size n (where by ‘size’ I mean the number of leaves in the tree). This isn’t true for monads in general – for example, two layers of
Reader Bool a is isomorphic to a4, which gets mapped to a2 by monadic join. So join preserves the combinatorial interpretation of the tree.
It seems likely that given any monad T and a family of equivalence relations ~a on Ta, the set of equivalence classes under the relation ~ is always a monad, but I haven’t thought much about it.
I think this is all extremely similar to a post written a few years back by Dan Piponi where he worked throught he details for the state monad instead of reader.