Monads are Trees with Grafting
This is an attempt to collect together, in tutorial form, a few of the things I've said about monads going back as far as my field guide. It's probably not a good first tutorial, but it contains things I'd wish I'd known immediately after reading my first tutorial.
Unfortunately, I used a few more LaTeX features than I ought to have while drafting it making it hard to get back into HTML form cleanly. So here is a PDF: Monads are Trees with Grafting.
Probably the main inspiration was this post by Derek Elkins.
Unfortunately, I used a few more LaTeX features than I ought to have while drafting it making it hard to get back into HTML form cleanly. So here is a PDF: Monads are Trees with Grafting.
Probably the main inspiration was this post by Derek Elkins.
posted by sigfpe at Friday, January 01, 2010
14 Comments:
thanks for your tutorial, didn't know about the tree-comparison until now. Really helpful!
On page two in the monad tree instance you wrote
Leaf a >>= f = f a
shouldn't that be
Leaf a >>= f = Leaf (f a)
?
Dan, I haven't had a chance to read it yet, but thanks for everything. Your posts have taught me a lot. Happy new year!
Long time reader,first time commenter.
Your posts usually manage to give a tiny insight into really cool ideas,but most of the time are well above my head.Love your space.
Wish you a happy new year.
@onemillionmilesaway
Let me see whether i have got monads right.
The function f is of type (a -> Tree b).Applying the Leaf constructor will make the result Tree (Tree b).The function f probes the content of the leaf,makes a decision based on it and returns a replacement tree for the current leaf.It is the richness of the replacement tree type which gives monad a lot of power(i think).You can use the replacement trees as markers to terminate computational branches,grow them,etc etc.
onemillionmilesaway: it shouldn't.
Notice that, if it would, you'd never be able to replace a leaf with a fork -- because in your definition Leaf always transforms to another Leaf.
Or just look at the types:
(>>=) :: Tree a -> (a -> Tree b) -> Tree b
The second argument, f, already returns some Tree -- no need to wrap it into Leaf.
Dan, pictures look great. How did you create them?
I suspect I'm pretty close to your target audience, and I found this very useful. In the past I've found the unit/join formulation of a monad easier to understand than the Kleisli triple one. I found it easy to visualise join but didn't really have an intuition for Kleisli star.
Your paper gives me a nice feel for the Haskell bind operator (and presumably Kleisli star is something like "flip bind"), and makes the connection to substitution much clearer. (I guess I can see why the lifting of a substitution k to an operation on terms is usually written k*, as well.) Nice one.
Roman,
As I mention in the PDF, the source is here: https://dl.dropbox.com/u/828035/Monads/monads.lhs It has the LaTeX diagram source too.
Thanks for trying to clarify a confusing concept. I'm pretty new to Haskell so I imagine I'm close to your target audience. Some feedback below.
"The idea is that given a tree we’ll replace every leaf node with a new subtree"
This is a confusing jump. This is not something you typically want to do with trees, so I suspect this is when things stray into conceptually-specific-to-monads territory, but it's not clear. Why do we want to do this? If you're trying to explain that this is an operation we'll want later -- then say that instead. 'The idea' refers to some ambiguous motive that the reader doesn't know about, and potentially misleads me into thinking that you're claiming that's how the grafting operation will work, but in that case it's not obvious why a grafting operation has to replace all leaves instead of just a single one.
Also, it's not clear why the tree has a Nil type. This lets you have forks with only one filled in leaf, but why not just have a leaf in place of the fork then? The only thing you gain I think is if you want to express that the whole tree is empty, in which case wouldn't you prefer a Maybe Tree?
Another great post.
Fork u v >>= f = Fork (u >>= f) (v >>= f)
Is the stack depth proportional to the depth of the tree when this function is called? Or will the Haskell compiler/runtime eliminate the tail call recursion?
Aravind,
I don't think the compiler can turn that into a tail recursion on its own.
There are three things that come to my mind here:
1. the Tree structure isn't the one you'd use for combinatorial search. I'm using it as "conceptual scaffolding" but in practice you'd use the List monad. So the bad performance of >>= for Tree doesn't matter.
2. If, for some reason, you decided you really need to work with Tree then you need to know it's an example of a "free monad". These are known to be inefficient to use directly. But there is a nice (but tricky) paper on how to fix that: http://tinyurl.com/ygywnsl
3. If you really really want a tail recursion then Conor McBride tells you how to tail recurse over free monads in another nice paper: http://strictlypositive.org/CJ.pdf
That was probably a longer answer than you wanted :-)
Since Haskell and the Tree type is lazy, the definition of (>>=) for the Fork case will not consume stack. It will behave very nicely. In fact, it is probably more efficient in many cases to use the Tree monad followed by a depth-first pass at the end than to use the list monad, and, of course, we are not limited to only a depth-first pass, so using a Tree monad is more flexible in this case.
Hi Dan - any chance you could update the link in this post? The Dropbox file doesn't seem to exist any more.
@crnt
dropbox have changed their rules for sharing
I moved my pdf (and its source) to github.
https://github.com/dpiponi/grafting3/blob/master/monads.pdf
Post a Comment
<< Home