tag:blogger.com,1999:blog-1777990983847811806.post9164355965022050153..comments2015-07-25T16:28:33.744-07:00Comments on Haskell for all: Why free monads matterGabriel Gonzaleznoreply@blogger.comBlogger23125tag:blogger.com,1999:blog-1777990983847811806.post-57177244707641052652015-03-01T12:47:26.963-08:002015-03-01T12:47:26.963-08:00So usually `Game` is almost always `IO`. I was ju...So usually `Game` is almost always `IO`. I was just playing it safe by leaving it unspecified.<br /><br />However, note that you don't gain much by translating the free monad to some type classed monad (i.e. some `MonadGame` type class). The reason why is that the type class encodes the same amount of semantic information as the original free monad: none at all. Actually, the type class is a little less powerful because now you no longer have access to the syntax tree any longer once you translate it to the type class and you can't perform manipulations on the syntax tree.<br /><br />Most of the time you don't really need to manipulate the syntax tree anyway, so it's not a huge loss, but there are some cases where it does come in handy. An example of a library that heavily takes advantage of syntax tree manipulation is my `pipes` library, where all `pipes` are basically syntax trees of `Request`/`Respond` commands, and when you compose two pipes together it is fusing the two syntax trees together into a new syntax tree.Gabriel Gonzalezhttp://www.blogger.com/profile/01917800488530923694noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-30071704848206917302015-02-20T14:38:27.172-08:002015-02-20T14:38:27.172-08:00Hi Gabriel,
I cannot figure out what you mean wit...Hi Gabriel,<br /><br />I cannot figure out what you mean with sort of "Game" monad. The only thing I was able to do was:<br />type Game = IO<br />but I would like to have a way to define the functions "collectImage", "sendBullet", etc ... in a type class and then provide the instance with the implementation.<br /><br />Could you make a short example?<br /><br />Thanks for the beautiful article!<br />Matteo<br />Matteo Provenzanohttp://www.blogger.com/profile/03389987080980202438noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-38925030271896334922015-02-05T03:00:28.513-08:002015-02-05T03:00:28.513-08:00Hi Gabriel,
Regarding:
ringBell :: IO () -- some ...Hi Gabriel,<br /><br />Regarding:<br />ringBell :: IO () -- some obnoxious library would provide this<br /><br />Here is a working implementation (at least on OS X) based on a not so obnoxious library ;)<br />ringBell = putStr "\a"<br /><br />Thanks for this enlightening article!<br />DanielUnknownhttp://www.blogger.com/profile/15792078694746191822noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-13348629912266903582014-04-11T03:45:39.656-07:002014-04-11T03:45:39.656-07:00This comment has been removed by the author.Павел Платтоhttp://www.blogger.com/profile/07458619616929064384noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-74411442528828909842014-04-09T17:37:07.972-07:002014-04-09T17:37:07.972-07:00The best resource I have read for fixed points of ...The best resource I have read for fixed points of functors is this one:<br /><br />http://homepages.inf.ed.ac.uk/wadler/papers/free-rectypes/free-rectypes.txt<br /><br />However, even that is a bit dense. I am slowly working on writing up an explanation of my own.Gabriel Gonzalezhttp://www.blogger.com/profile/01917800488530923694noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-49097659325603551902014-03-28T12:38:36.664-07:002014-03-28T12:38:36.664-07:00It's named Fix because it is "the fixed p...It's named Fix because it is "the fixed point of a functor".<br /><br />I'd never heard the term "fixed point of a functor" before this article, FYI. I'm off googling it now, but you might want to explain that here.<br /><br />(Update after a few minutes with google: the articles you get when you google "fixed point of a functor" are pretty beginner-hostile.)James Moorehttp://www.blogger.com/profile/00881846109577158489noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-58362320706442714912014-01-11T20:57:03.635-08:002014-01-11T20:57:03.635-08:00Yes, I agree that seeing the fully formed solutio...Yes, I agree that seeing the fully formed solution is not as helpful as seeing the thought-process that led to it. It also helps motivate why the solution exists in the first place.<br /><br />Free monad interpreters are definitely one approach to modeling effects, but this is not a subject I'm an expert on. The last time I checked, one of Conor McBride's students, Stevan Andjelkovic was working seriously on taking this to its logical conclusion but I haven't followed up on that. There are lots of subtle details.Gabriel Gonzalezhttp://www.blogger.com/profile/01917800488530923694noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-14024168921768585072014-01-08T06:07:28.382-08:002014-01-08T06:07:28.382-08:00Fantastic article. I appreciate your "histori...Fantastic article. I appreciate your "historic" approach mimicking a incremental line of reasoning . That is how people learn and the knowledge can be transmitted, by example and incrementally, not by enumeration of mathematical results. The latter is good to store knowledge, not to transmit it. The process of discovery must be reconstructed in each one's mind to fully gasp the meaning. Why force people to rediscover the path if the author know it and can transmit it? Maybe one day transmission of knowledge can be formalized.<br /><br />Less philosophical: I suppose that free monad interpreters is what Oleg and others use to modelize effects itsn't it?. Do you plan to explain effects that way if you didn't already? <br />Alberto Gómez Coronahttp://www.blogger.com/profile/11962281728014883353noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-18861652946287294772013-07-11T09:29:30.435-07:002013-07-11T09:29:30.435-07:00You are echoing the same line of thinking that led...You are echoing the same line of thinking that led me to formulate my `pipes` library. I was trying to figure out how to use the same abstraction for both building the DSL and consuming the DSL. The result was to use a free monad to produce events (i.e. a Producer) and a free monad to consume events (i.e. a Consumer) and both were special cases of a Pipe.<br /><br />However, there is some loss of power as a result, so take this answer with a grain of salt.Gabriel Gonzalezhttp://www.blogger.com/profile/01917800488530923694noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-75680155089293708082013-07-11T09:22:59.290-07:002013-07-11T09:22:59.290-07:00The section on Interaction deserves its own post. ...The section on Interaction deserves its own post. What do we do when we want to implement a UI for the game instead of an AI? I imagine we'd do something like the following:<br /><br />Define a type of Plans over some other computation, like Program above<br /><br />type Plan = FreeT Interaction<br /><br />Provide syntactic sugar for building a Plan:<br /><br />liftMethod :: (Functor f, Monad m) => ((a -> FreeT f m a) -> f (FreeT f m a)) -> FreeT f m a<br />liftMethod f = FreeT (return (Free (f return)))<br /><br />look :: (Monad m) => Direction -> Plan m (Image)<br />look direction = liftMethod (Look direction)<br /><br />liftFT :: (Functor f, Monad m) => (FreeT f m () -> f (FreeT f m ())) -> FreeT f m ()<br />liftFT a = FreeT (return (Free (a (return ()))))<br /><br />fire :: (Monad m) => Direction -> Plan m ()<br />fire direction = liftFT (Fire direction)<br /><br />readLine :: (Monad m) => Plan m (String)<br />readLine = liftFT (ReadLine)<br /><br />writeLine :: (Monad m) => String -> Plan m (Bool)<br />writeLine message = liftMethod (WriteLine message)<br /><br />I thing liftFT could be rewritten in terms of liftF, or fire could be defined as:<br /><br />fire direction = liftF (Fire direction id)<br /><br />I haven't figured out a more elegant liftMethod.<br /><br />Then our UI could be written as<br /><br />ui :: Direction -> Plan IO ()<br />ui initialDirection = do ...<br /> Code to look, display an image, check for a chat message, display a chat, get input, and decide to change what direction we are looking / fire / or send a chat<br /><br />I'm not sure how we can poll for a new incoming chat message with ReadLine, since it seems like it would block until there is a String to pass to next. Perhaps it should be:<br /><br />data Interaction next =<br /> Look Direction (Image -> next)<br /> | Fire Direction next<br /> | ReadLine (Maybe String -> next)<br /> | WriteLine String next<br />cirdechttp://cirdec.myopenid.com/noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-5403680155874731622013-05-22T12:19:59.001-07:002013-05-22T12:19:59.001-07:00The target audience of my post is people who have ...The target audience of my post is people who have never been introduced to the idea of using a recursive data type, particularly a functor, to model commands. These people typically come from an imperative background that distinguishes statements and expressions. This is why the introduction explicitly dwells on that particular wrong way of doing things.Gabriel Gonzalezhttp://www.blogger.com/profile/01917800488530923694noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-76787242826956008942013-05-22T01:03:13.401-07:002013-05-22T01:03:13.401-07:00Your initial example is distracting to me. You sa...Your initial example is distracting to me. You say you can't add commands to the program because the type always changes but actually the only reason the type changes is that you specify "nextstep" as a type parameter when it will actually only ever be Toy a. So the way you could "cheat" would be to define Toy in the normal way:<br /><br />Toy a = Output a (Toy a) | Bell (Toy a) | DoneAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-29992092730463142042013-03-19T08:10:48.579-07:002013-03-19T08:10:48.579-07:00You're welcome!You're welcome!Gabriel Gonzalezhttp://www.blogger.com/profile/01917800488530923694noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-85401082373606060452013-03-18T09:08:19.493-07:002013-03-18T09:08:19.493-07:00Great article, thanks!Great article, thanks!Mikhail Glushenkovhttp://www.blogger.com/profile/16766775468165268210noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-7459122127048187532012-10-18T17:32:49.582-07:002012-10-18T17:32:49.582-07:00Actually, it does change the Toy b x. Note that t...Actually, it does change the Toy b x. Note that the functor definition is not recursive.Gabriel Gonzalezhttp://www.blogger.com/profile/01917800488530923694noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-27776679062239369302012-10-18T16:34:42.877-07:002012-10-18T16:34:42.877-07:00The instance definition of fmap for Toy b seems to...The instance definition of fmap for Toy b seems to reduce to saying that fmap f is just the identity function for any f. Is that right?basmanhttp://www.blogger.com/profile/00669434237846574559noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-72308804096376034752012-09-17T12:54:22.228-07:002012-09-17T12:54:22.228-07:00No, it is correct. I think it is more clear if I ...No, it is correct. I think it is more clear if I expand out the definition a little bit:<br /><br />(Free x) >>= f = Free (fmap (\m -> m >>= f) x)<br /><br />Haskell's section syntax says that if (*) is some operator, then:<br /><br />(* b) = \a -> a * b<br />(a *) = \b -> a * b<br /><br />This can be a bit confusing because if you were to instead put the parentheses around the operator, then the operator is interpreted using prefix notation instead of section notation:<br /><br />(*) a b = a * b<br /><br />... which is confusing since `(* a)` and `(*) a` look very similar, but have different meanings:<br /><br />(* a) = \x -> x * a<br />(*) a = \x -> a * xGabriel Gonzalezhttp://www.blogger.com/profile/01917800488530923694noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-27204643011237805142012-09-17T12:05:37.822-07:002012-09-17T12:05:37.822-07:00In ` (Free x) >>= f = Free (fmap (>>...In ` (Free x) >>= f = Free (fmap (>>= f) x)`, shouldn't there be a 'flip' before >>= ?Ittay Drorhttp://www.blogger.com/profile/06786072335349487451noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-24020828162535053442012-09-13T02:48:25.219-07:002012-09-13T02:48:25.219-07:00Excellent topic. Excellent writing. Every time I c...Excellent topic. Excellent writing. Every time I come back to haskell I generally spend a few days hammering boilerplate monad instantiation back into my head. I was also unaware that deriving functors was possible. You saved me a few days and then some :). Jessehttp://www.blogger.com/profile/18324998635607736552noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-48780140930666475802012-08-24T16:21:59.155-07:002012-08-24T16:21:59.155-07:00It forks the current context. For example, let...It forks the current context. For example, let's say I write:<br /><br />forkPlus :: Free Expr Bool<br />forkPlus = liftF $ Plus False True<br /><br />Then it would behave just like C's fork implementation, where the return value tells you which branch of the computation you are on:<br /><br />do<br /> bool <- forkPlus<br /> if bool<br /> then ... -- On the right branch<br /> else ... -- On the left branch<br /><br />Of course, you don't have to do it that way. You can always still use the conventional way to build the AST without the monad instance, by just defining:<br /><br />plus :: Free Expr a -> Free Expr a -> Free Expr a<br />plus e1 e2 = Free $ Plus e1 e2Gabriel Gonzalezhttp://www.blogger.com/profile/01917800488530923694noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-58220207358075310422012-08-24T16:21:26.835-07:002012-08-24T16:21:26.835-07:00Glad I finally bit the bullet and read my tabs on ...Glad I finally bit the bullet and read my tabs on Free monads. I think they're what I've been looking for for a number of applications. Great writing!jberrymanhttp://www.blogger.com/profile/11505410150377453045noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-79826663026254458642012-08-24T15:32:01.657-07:002012-08-24T15:32:01.657-07:00This is awesome. How does the machinery work for n...This is awesome. How does the machinery work for non-linear languages, for example data Expr a = Value a | Plus a a?Unknownhttp://www.blogger.com/profile/01055204032970253748noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-41036048734562061192012-08-03T15:32:36.163-07:002012-08-03T15:32:36.163-07:00Great Article! The best I've found regarding a...Great Article! The best I've found regarding an explanation of how the Free monad worksromanandreg.comhttp://www.romanandreg.com/noreply@blogger.com