tag:blogger.com,1999:blog-11295132.post4539954972800523926..comments2014-04-03T09:41:41.120-07:00Comments on A Neighborhood of Infinity: Monads are Trees with GraftingDan Piponihttps://plus.google.com/107913314994758123748noreply@blogger.comBlogger12125tag:blogger.com,1999:blog-11295132.post-8398174695563007042010-01-07T23:53:59.538-08:002010-01-07T23:53:59.538-08:00Since Haskell and the Tree type is lazy, the defin...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.Derek Elkinshttp://www.blogger.com/profile/13447153951050085981noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-71776403165158205472010-01-07T11:10:25.283-08:002010-01-07T11:10:25.283-08:00Aravind,
I don't think the compiler can turn ...Aravind,<br /><br />I don't think the compiler can turn that into a tail recursion on its own.<br /><br />There are three things that come to my mind here:<br /><br />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.<br /><br />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<br /><br />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<br /><br />That was probably a longer answer than you wanted :-)sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-14490976948727496172010-01-07T10:53:01.650-08:002010-01-07T10:53:01.650-08:00Fork u v >>= f = Fork (u >>= f) (v >...<b>Fork u v >>= f = Fork (u >>= f) (v >>= f)</b><br /><br />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?Aravindhttp://www.blogger.com/profile/02672919327579148504noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-1979314919333828022010-01-03T01:45:51.811-08:002010-01-03T01:45:51.811-08:00Another great post.Another great post.greenlybluehttp://www.blogger.com/profile/12650799716897815432noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-42107360209218862482010-01-02T16:24:20.183-08:002010-01-02T16:24:20.183-08:00Thanks for trying to clarify a confusing concept. ...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.<br /><br />"The idea is that given a tree we’ll replace every leaf node with a new subtree"<br /><br />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.<br /><br />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?josephhttp://joseph.garvin.myvidoop.com/noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-62394268232774575222010-01-02T08:02:23.539-08:002010-01-02T08:02:23.539-08:00Roman,
As I mention in the PDF, the source is her...Roman,<br /><br />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.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-60384284618664507872010-01-02T04:01:57.187-08:002010-01-02T04:01:57.187-08:00I suspect I'm pretty close to your target audi...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.<br /><br />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.Roly Pererahttp://www.blogger.com/profile/10168144731270158487noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-20402268312567887592010-01-02T03:40:53.553-08:002010-01-02T03:40:53.553-08:00Dan, pictures look great. How did you create them?...Dan, pictures look great. How did you create them?Roman Cheplyakahttp://www.blogger.com/profile/07189392968519496723noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-39234686137072362752010-01-02T03:35:05.849-08:002010-01-02T03:35:05.849-08:00onemillionmilesaway: it shouldn't.
Notice that...onemillionmilesaway: it shouldn't.<br />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.<br /><br />Or just look at the types:<br />(>>=) :: Tree a -> (a -> Tree b) -> Tree b<br /><br />The second argument, f, already returns some Tree -- no need to wrap it into Leaf.Roman Cheplyakahttp://www.blogger.com/profile/07189392968519496723noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-24639406406915638322010-01-02T01:00:44.314-08:002010-01-02T01:00:44.314-08:00Long time reader,first time commenter.
Your posts...Long time reader,first time commenter.<br /><br />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.<br /><br />Wish you a happy new year.<br /><br />@onemillionmilesaway <br />Let me see whether i have got monads right.<br />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.Thiagarajanhttp://www.blogger.com/profile/13553744552007824713noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-40778124251155139212010-01-01T20:09:17.518-08:002010-01-01T20:09:17.518-08:00Dan, I haven't had a chance to read it yet, bu...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!andrewkish.namehttp://andrewkish.name/noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-38175908262026510852010-01-01T15:56:43.188-08:002010-01-01T15:56:43.188-08:00thanks for your tutorial, didn't know about th...thanks for your tutorial, didn't know about the tree-comparison until now. Really helpful!<br />On page two in the monad tree instance you wrote<br /><br /> Leaf a >>= f = f a<br /><br />shouldn't that be<br /><br /> Leaf a >>= f = Leaf (f a)<br /><br />?onemillionmilesawayhttp://www.blogger.com/profile/12178848271430253107noreply@blogger.com