Haskell's Monad class is a foreign concept. There's nothing special
about it, and it's not very difficult conceptually, but there are
several layers of turning gears and it takes some time to develop
fluency with it. Just as with a foreign language, fluency comes in two
stages: recognition and creative usage. In the recognition stage, one
will understand Monads, how they're used, what they mean. In the
creative-usage stage, one will construct new programs freely using
Monads where appropriate.
Here, we do a few little things to improve the sample that begins on
page 262 of Paul Hudak's book, "The Haskell School of Expression"
(SOE).
First, we rename some variables. Hudak uses "a" for at least two
different purposes, once for a Tree containing elements of another
type, and again for that other type. Whilst renaming these variables
does not affect any computational aspect of the sample and only
improves exposition, it, well, improves exposition. I sometimes prefer
long, descriptive variable names, and I sometimes prefer short,
easy-on-the-eye variable names. It all depends on what stage of the
fluency ramp I find myself on. If I'm early in the recognition phase,
I want long names to remind me of what's going on here and there. If
I'm late in the creative-usage phase, I want terse, angry little
variable names that don't cloy my vision and clutter my mind with
reviews of long-since internalized concepts.
Second, rather than replacing the contents of a Tree with labels, we
augment the contents with labels, that is, replace the contents with
(label, contents) pairs.
As an aside, we shorten some base constructors and make them all the
same length. Tree -> Tr, Leaf -> Lf, Branch -> Br, State -> St. That
makes some tree expressions a tiny bit easier to wade through.
A Tree is either a Leaf containing data or a Branch with two Trees:
> data Tr a = Lf a | Br (Tr a) (Tr a)
> deriving Show
A reified example:
> tr1 = Br (Lf 'a') (Br (Br (Lf 'b') (Lf 'a')) (Lf 'd'))
As stated, a new tree is a tree of (label, oldContents) pairs, and
labels are of type St:
> type NuTr a = (Tr (St, a))
> type St = Int -- State, or "St", is just an Int
To get started, let's keep handy the non-monadic form of a tree
labeler:
"label" takes a tree and returns a NuTr. It does so by explicitly
picking the NuTr out of the second slot of a pair returned by a helper
function. It uses the built-in pair selector "snd" to do that. The
helper function threads the state counter around in the first slot of
the pair, where pattern-matching can fish it out for recursive
calls. So, we have another use of pairs: to hold the state variable
and the NuTr.
> label :: Tr a -> NuTr a -- the Int is the label
> label tr = snd (lab tr 0) -- lab tr int is the stateful helper
> where
Here is the stateful helper. It takes an old tree, a state counter
value, and returns a pair of state counter (potentially updated) and a
new tree, which is, itself, a tree of pairs:
> lab :: Tr a -> St -> (St, NuTr a)
> lab (Lf contents) n = ((n+1), (Lf (n, contents))) -- returned pair
> lab (Br l r) n0 = let (n1, l') = lab l n0 -- pat match in
> (n2, r') = lab r n1 -- recurive calls
> in (n2, Br l' r') -- returned pair
That was lovely and very simple, especially to those with Scheme and
Lisp backgrounds. To test it, type "label tr1", or make up some test
data of your own.
On to Act II of the saga:
The very first thing to notice is that "(lab tree)", "lab" applied to
a datum of type Tree, is of type (St -> (St, NuTr a)). That looks just
like the standard state-monad type, which is (State -> (State,
StatelessThing)). So the state monad abstracts the pattern of a
curried stateful helper function applied to a stateless object. Once
we pass the stateless object to the helper function, by currying, we
are left with a function from a state to a pair of a state and a
stateless object. That's the critter we're going to enshrine in a
State Monad.
In the pattern above, the resultant stateless object is of a different
type, NuTr, so the pattern not only glues on the state, it transforms
the type of the object. We add this wrinkle to the example in the
Hudak book. In the book, the resultant stateless object is of the same
type as the input stateless object.
So, let's make a new type for objects of type "Label" to hold curried,
partially applied helper functions, that is, functions from a "St" to
a "(St, any)" pair.
> newtype Label anytype = Label (St -> (St, anytype))
Make Label an instance of class Monad:
> instance Monad Label where
Supply implementations of "return" and "bind" or ">>=", which I prefer
to call "shove".
"Return" takes any contents and returns a Label monad, that is, a
St->(St,contents). It's just a functionizing wrapper, a thunkulator,
if you will.
> return contents = Label (\st -> (st, contents))
I will use the following variable-name shorthand for the St -> (St,
any) functions in the Label monads: read "fsti" as "function number i
of some state". So, I will have fst0, fst1, and so on for "function
number zero of some state," and "function number 1 of some state," and
so on.
"Shove" takes, as its first argument, one of our monads, which holds a
"St -> (St, any)", and, as its second argument, a function with
signature like "return"'s, that is, a function from "any" to a Label
monad. "Shove" returns a third Label monad. It is very important to
realize that the three monads are not all going to hold the same kinds
of things. We shall see that one of them holds a state updater and two
of them hold tree updaters. Keep this in mind as we go along, and
remember it when we get to applying the monad to our trees. Just
appreciate the point abstractly for the moment:
> -- ">>=" takes a Monad x and a (x -> Monad y) and returns a Monad y
> Label fst0 >>= fany1 = -- pat match, meaning fst0 is St->(St,any)
> Label $ \st0 -> -- return new monad holding anon func of st0
> let (st1, any1) = fst0 st0 -- pat match new st1 and contents
> Label fst1 = fany1 any1 -- shove contents into fany1,
> -- getting new monad fst1
> in fst1 st1 -- feed st1 into new monad, returning (St, any)
> -- and that's what we needed, a function from
> -- st0 to (St->Any) implemented through the new
> -- monad returned by fany1.
There are three monads at work in the definition of ">>=". The first
is its left-hand, or first, argument, fst0, that is, "function number
zero of some state". The second monad in ">>=" pertains to its second
argument, which is a function that returns a new monad given some
contents. So, we give the first monad a state, get a new state and
some contents, shove the contents into the second argument, getting a
new monad, our second one. The third monad in ">>=" is the monad it
returns. Now, why not just return the second monad coughed up when we
called the second argument? Because we will lose the updated state!
The state got updated, hopefully when we applied the first monad to
the initial state. We got a second monad by shoving the new contents
into the second argument of ">>=", but if we return this second monad
as the result of ">>=", the updated state will just fall into the
garbage collector. But, hey, we can make another monad that applies
the middle monad to the new state. So there is the third one. Once
again, the first one is the left-hand argument to ">>=". The second is
an internal one returned by the right-hand argument to ">>=" applied
to new contents. The third is the return value, which is a function
from the old state that applies the new, internal monad to the updated
state. Thats what we need, a function from a state -- the old state --
to a (updated-state, contents) pair.
We're almost done. Our old, non-monadic function was "label" from a Tr
to a NuTr. Our new one, "mlabel", has the same signature:
> mlabel :: Tr anytype -> NuTr anytype
> mlabel tr = let Label mt = makeMonad tr
> in snd (mt 0) -- apply the monad to initial state.
This is pretty obvious:
> makeMonad :: Tr anytype -> Label (NuTr anytype)
Now, remember that the "do" notation comprises shorthand for ">>=".
The following "do" is really just
updateState >>= (\n -> return (Lf (n,x)))
that is, the result of updateState, which better be a monad, shoved
into a function that returns a new leaf monad. Remember how "shove"
works -- it returns a function of an initial state that takes the
first monad, returned by updateState here, applies it to the initial
state resulting in an updated state and contents; shoves the contents
into the second argument, getting a second monad, specified by the
return statement, here; then applies the second monad to the updated
state to get the new (updated-state, contents) pair. The "return" in
our monad just wraps its argument in the appropriate St->(St,any)
clothing; it's pretty vapid. The whole thing looks easier using "do":
> makeMonad (Lf x)
> = do n <- updateState -- "n" is of type "St"
> return (Lf (n,x)) -- "return" does the heavy lifting
> -- of creating the Monad from a value.
So a call of makeMonad on a leaf node will make a monad that's ready
to take an initial state and return an updated-state, contents pair).
When we're all through with the tree, the top-level function will call
"snd" on the final pair, letting the last state variable, containing
whatever irrelevant value it contains, fall into the garbage
collector.
The recursive case is trivial:
> makeMonad (Br l r)
> = do l' <- makeMonad l
> r' <- makeMonad r
> return (Br l' r')
And now, for the piece de resistance: updateState, which is a function
of no arguments that returns a monad of a different type from the
monad holding the labeled tree! This monad just puts the old state
into the contents slots. When "shove" applies this monad to the
initial state, it gets the new state in the state slot and the old
state in the contents slot. That old state gets passed to the "return"
of the new Leaf, so the Leaf gets labeled with the old state, and the
Monad holding it gets applied to the new state in the next round of
calls.
Remember, "shove" takes a Monad x, a x -> Monad y, and returns a Monad
y. In our sample, x is St and y is NuTr anytype. Pretty cool. We've
used just about every feature of the Monad class.
> updateState :: Label St
> updateState = Label (\n -> ((n+1),n))
> main = mlabel tr1