tag:blogger.com,1999:blog-7094652.post6665377779047363335..comments2024-03-23T14:36:09.980+00:00Comments on Neil Mitchell's Blog (Haskell etc): Monads as GraphsNeil Mitchellhttp://www.blogger.com/profile/13084722756124486154noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-7094652.post-18854254467901090212019-10-19T20:03:05.625+01:002019-10-19T20:03:05.625+01:00@Christopher: There are two possible ways. You can...@Christopher: There are two possible ways. You can either encode the graph like https://www.reddit.com/r/haskell/comments/djfsyq/monads_as_graphs_and_a_relationship_to_the/f49qmrp, or assume that things are deduplicated at some other layer (as all build systems actually do).<br /><br />If you take your approach, then you would have to draw a tree with no sharing for Applicative, which isn't unreasonable, but that strongly suggests there is a type class that has sharing but no other powers. Keen to see what that type class looks like.Neil Mitchellhttps://www.blogger.com/profile/13084722756124486154noreply@blogger.comtag:blogger.com,1999:blog-7094652.post-39850321782038795902019-10-18T10:41:41.197+01:002019-10-18T10:41:41.197+01:00Is the graph for Applicative really accurate? (htt...Is the graph for Applicative really accurate? (https://3.bp.blogspot.com/-A8fyuxlE3qQ/XaOD_u7DMkI/AAAAAAAABe4/ePXkqtOqRkMt_D6DpYUWw8dKkzS0VwZFgCLcBGAsYHQ/s1600/Applicative.png) <br /><br />How would you write that graph with Applicative class's methods?<br /><br />I wrote up my view with diagrams here: https://www.reddit.com/r/haskell/comments/djfsyq/monads_as_graphs_and_a_relationship_to_the/f45rbi5/<br /><br />Wasn't sure how to do it in blogger.com's formatting.Christopher Donehttps://chrisdone.com/noreply@blogger.comtag:blogger.com,1999:blog-7094652.post-76366937325931622032019-10-16T08:59:05.603+01:002019-10-16T08:59:05.603+01:00Thanks for the comments Ondra, very interesting. Y...Thanks for the comments Ondra, very interesting. You can make a tree of functors of type m a, but for any particular value m a, it can only be generated in one way. Interesting connection to the hierarchy of languages, would be great to see a formal treatment of that - it seems about right, but I'd love to know what lemma shows the correspondence.Neil Mitchellhttps://www.blogger.com/profile/13084722756124486154noreply@blogger.comtag:blogger.com,1999:blog-7094652.post-39555164037947754012019-10-16T00:54:30.266+01:002019-10-16T00:54:30.266+01:00aww, blogger.com formating broke my beautiful grap...aww, blogger.com formating broke my beautiful graph :D but I hope you see what I mean<br /><br />anyway, thank you very much for this thought-provoking post!Ondrahttps://www.blogger.com/profile/12985191935520807414noreply@blogger.comtag:blogger.com,1999:blog-7094652.post-75617192306974545832019-10-16T00:52:19.005+01:002019-10-16T00:52:19.005+01:00I know this is not the point of this post, but the...I know this is not the point of this post, but the Functor class graph _can_ be a tree: if I have `m a` and `a -> b`, I can create `m b`; but if I also have `a -> c`, I can also create `m c` from that. Something like<br /><br /> m a<br /> / \<br /> / \<br />m b m c<br /><br />Also, it seems to me that it broadly aligns with the formal hierarchy of languages, where correspond<br /><br />(1) regular languages/grammars ≈ finite state automata ≈ regular expressions ≈ linear/string-like graphs<br /><br />(2) context-free languages/grammars ≈ pushdown automata ≈ μ-regular expressions ≈ tree graphs, and also Functor according to this blogpost<br /><br />(3) context-sensitive languages/grammars ≈ linear bounded automaton (≈ simply-typed lambda calculus, I guess???) ≈ directed acyclic graphs, and also Applicative according to this blogpost<br /><br />(4) recursively enumerable languages/unrestricted grammars ≈ Turing machine ≈ untyped lambda calculus ≈ any graph<br /><br />Question is, what would be the Type Class for (1)? And is Monad the right Type Class for (4) or should there be something different?<br /><br />Ondrahttps://www.blogger.com/profile/12985191935520807414noreply@blogger.com