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
1 2 

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 s
and 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 Reader Bool
.
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 a^{2.} 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 rary 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 rtuple of trees. In Haskell,
1 2 

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 runReader
and ask
functions:
1 2 3 4 5 

You can then then use this like any other reader:
1 2 3 4 

The local
function can be defined similarly, in terms of Ask
.
Thoughts
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 a^{4,} which gets mapped to a^{2} by monadic join. So join preserves the combinatorial interpretation of the tree.
This is related to some stuff I’m thinking about to do with combinatorial species and how they relate to functional programming. A comment by Brent Yorgey sparked the idea for this post.
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.