Chris Taylor

Mainly math and haskell

Trees and Readers

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
data Tree a = Leaf a
            | Node (Tree a) (Tree a)

This is both a functor and a monad –

1
2
3
4
5
6
7
8
instance Functor Tree where
    fmap f (Leaf a)   = Leaf (f a)
    fmap f (Node l r) = Node (fmap f l) (fmap f r)

instance Monad Tree where
    return = Leaf
    Leaf a   >>= f = f a
    Node l r >>= f = Node (l >>= f) (r >>= f)

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
runTree :: Tree a -> Bool -> a
runTree (Leaf a)   s = a
runTree (Node l r) s = runTree (if s then l else r) s

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 Rf using the normal bind operation for trees. Then take the equivalence class of the resulting tree. Symbolically,

$$ \newcommand{\bind}{\gg \!\!=} x\bind f = C( R(x) \bind R\circ f ) $$

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 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,

1
2
data Tree r a = Leaf a
              | Node (r -> Tree r a)

Again this is both a functor and a monad

1
2
3
4
5
6
7
8
instance Functor (Tree r) where
    fmap f (Leaf a) = Leaf (f a)
    fmap f (Node g) = Node (fmap f . g)

instance Monad (Tree r) where
    return = Leaf
    Leaf a >>= f = f a
    Node g >>= f = Node (\r -> g r >>= f)

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
runTree :: Tree r a -> r -> a
runTree (Leaf a) r = a
runTree (Node g) r = runTree (g r) r

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
data Reader r a = Return a
                | Ask (r -> Reader r a)

runReader = runTree
ask       = Ask Return

You can then then use this like any other reader:

1
2
3
4
greet name = do greeting <- ask
                return (greeting ++ ", " ++ name)

test = runReader (greet "Chris") "Hello" -- returns "Hello, Chris"

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 TT 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.

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.