Thanks for this nice analogy and explanation. This brings "monad transformers" to my mind. "without" monad transformers, the monads are bit crippled in their applicability (please correct me if I am wrong) and "with" monad transformers the code becomes to some extent ugly (again, please correct me if I am wrong)
I wonder, where and how the Monad transformers fit in here? Thanks and regards, -Damodar Kulkarni On Sat, Aug 17, 2013 at 1:07 AM, Mathijs Kwik <math...@bluescreen303.nl>wrote: > Thiago Negri <evoh...@gmail.com> writes: > > > I just stumbled upon the Applicative term. > > Arrows are quite difficult for me to understand at the moment. > > I guess it needs time to digest. > > > > But, as I understand so far, Applicative and Arrows looks like the same > > thing. > > > > Please, enlight me. > > I would like to point out this paper: > http://homepages.inf.ed.ac.uk/slindley/papers/idioms-arrows-monads.pdf > > In short: arrows are a bit more powerful than idioms (applicative) but a > bit less than monads. However, power sometimes comes at a price. > All 3 have to do with combining / sequencing effects, but they differ in > subtle but important ways. Every idiom is an arrow and every arrow is a > monad, but not the other way around. > > I will first give an overview of the differences, then try to explain > what I mean... (my terminology might be a bit awkward/wrong) > > Idiom: > Basic combining strategy: i (a -> b) -> i a -> i b > Sequencing: effects are applied in sequence > values (stuff "inside") are isolated > Shape depends on values: no > > Arrow: > Basic combining strategy: a b c -> a c d -> a b d > Sequencing: effects are applied in sequence > values are sequenced too > values can "see" upstream results > Shape depends on values: static choices only > > Monad: > Basic combining strategy: m a -> (a -> m b) -> m b > Sequencing: effects are applied in sequence > values are sequenced too > values can "see" upstream results > Shape depends on values: yes, fully dynamic > > > Now, what do I mean by all this? > Basically these 3 abstractions consist of 3 things: > - effects > - values > - shape > Effects can be things like "carries state around"(State), "can > fail"(Maybe), "multiple answers"(List) and more. Values are the pure > stuff "inside", and what I call 'shape' is the general control flow of a > computation. > Furthermore, I visualize these abstractions by thinking of a factory > hall with boxes (values), people (effects) and an assembly line > (shape). > > > Idioms are fully static: values cannot see/depend on each other or on > the result of effects. Basically the computation is split into 2 phases: > - effects+gather > - apply gathered results > example: > pure (+) <*> Just 3 <*> Just 5 > The first phase just works through the parts (in sequence) and collects > the (pure) contents. In this case (Maybe) this means looking for the > Just constructor to continue, or halting on Nothing. The content inside > is being treated like a black box. It is not made aware of the effects > (whether or not Nothing was found somewhere) and it is not being > examined to choose a different codepath. > Then if everything worked out (no Nothings were found), the collected > results are taken out of their black boxes and applied. In this phase > these results (the +, the 3 and the 5) don't know anything about the > effects that happened. > > In "factory visualization": every part of the computation (stuff between > <*>) is a person that will need to perform some task(effect) and deliver > some result in a box. They will only start performing their task when > they see a box passing by from the person upstream. They cannot look in > that box or make decisions based on it or take it off. At the end of the > line, some manager receives all the boxes and opens them to combine the > results. > > This is fine for a whole lot of applications and has the advantage that > the shape of the entire assembly line is clear even before starting > it. This means (static) optimization can be performed and it's easy to > reason about the program/costs. Garbage collection (sending workers > home) is easier, because it's very clear what data is needed where and > when. I will talk a bit more about these optimizations a bit further > down. Of course this assembly line is not flexible enough for more > advanced cases. > > Let's see an example of that(State): > pure const <*> get <*> put 8 > This is a perfectly fine idiom, albeit not very useful. > When run (with initial state 4) the first worker will package up a box > with "const" and send it downstream. The second worker gets the seeded > state from the "state cupboard" and put it in a box (4). When that box > passes by worker 3, he will walk to the state cupboard and put 8 in > it. Then to signal he's ready, he packs a box with (). At the end of the > line, someone opens the boxes "const" "4" and "()", which computes to > just 4. So we end up with the answer 4 and an updated cupboard > containing 8. > > Why is this not very useful? Well we would probably want to be able to > put state in that depends on certain stuff we got out earlier, instead > of just supplying a hard coded 8 that was known before starting the > line. Unfortunately, this is not possible with idioms as workers cannot > open each other's boxes. > > > Now, let's skip Arrows for a minute and move straight to Monads: > > > get >>= \x -> put (x + 1) >> return x > As you can see, monads tackle this issue by putting everything in > sequence. Not just the effects, but values too. Like this, they can > "see" upstream values and upstream effects and influence the effects and > shape of things to come further "downstream". > Another example (State again): > > do x <- get > if x > 100 > then do put 0 > return "overflow" > else do put (x+1) > executeBatch x > return "normal operation" > > This example shows nicely how the entire shape is dynamically chosen > when using a Monad, influencing both which effects will apply (will the > batch job run?) and result (status string). > > But let's look a bit closer at how Monad performs this trick: > get >>= (\x -> put (x + 1) >>= (\_ -> return x)) > get >>= (\x -> > if x > 100 then (put 0 >>= (\_ -> return "overflow")) > else (put (x+1) >>= (\_ -> > executeBatch x >>= (\_ -> > return "normal operation")))) > I've added parentheses to clearly show the "parts" involved. > Basically both these cases look like > get >>= xyz (only 2 parts, get and some unknown xyz) > So what can we say about xyz? Not a whole lot. xyz is a function that > will return a new monadic value when given an input. But we cannot > really statically inspect a function without applying it to an input > value. So basically we don't know what will happen next until we are > already running. > > To look at it from the factory-visualization perspective, we have > divided the assembly-line into a lot of separate parts. Worker 1 gets > the state from the state cupboard and puts it on the line. But the line > is very short and just flows to worker 2. Worker 2 then receives the > box, opens it and then starts to reorganize the factory to proceed. He > might need to place new pieces of assemly-line to new parts of the > factory, phone workers to come to work, whatever. Basically the entire > factory is 1 big black box except for the task/effect of worker 1. > > This is extremely powerful, as worker 2 can decide truly dynamically > what to do. But we lose our possibility to optimize things at compile > time and to reason about the shape and possible outcomes from the > language itself. Sure, by looking at the sources we (and the compiler) > can figure out a bit about what's going on, but far less well than with > idioms, as things really depend on runtime inputs now. > > > > Now, let's look at Arrows and how they tackle the same problem: > > get >>> arr (\x -> (x + 1, x) ) >>> first put >>> arr snd > or using arrow syntax: > proc _ -> do > r <- get -< () > put -< r + 1 > returnA -< r > In factory-visualization: workers can look inside each other's boxes or > take them off the line. > Worker 1 gets the state from the cupboard and puts it in a box. > Worker 2 looks at this box, calculates +1 and updates the state > cupboard. > When we run this, starting with 4 in the state cupboard, we get back the > result (4) at the end of the line, while the state cupboard now contains > 5 (a value that depended on a previous effect, which was not possible > with idioms). So what's up with these "arr" and tuples and > first/seconds/fst/snd parts in the normal (non-arrow) notation? I like > to think of it as flow control for the assembly line. Like tags being > put on the boxes to indicate which co-worker they are meant for. Simple > robotic parts of the line (arr snd) just throw out boxes that aren't > needed anymore so they don't have to travel all the way to the end of > the line. > > So from this example it's clear that arrows have some extra power over > idioms, without sacrificing the clarity of the entire factory-flow. > All static optimizations that are possible with idioms should still work > with arrows, so basically I think they are just plain better from all > technical points of view. But syntactically I cannot stand them :) > Shuffling tuples around constructing, deconstructing them everywhere > just doesn't lead to readable code and I'm not 100% sure that the > compiler can fully optimize them away. Arrow syntax helps a lot, but > compared to an elegant idiom (especially if you have idiom brackets > available like in idris or using SHE) it's just ugly. > > So how about making dynamic choices based on box contents? > This is possible using ArrowChoice. The existence of this separate class > probably implies that ArrowChoice cannot always be implemented for every > Arrow, but it might just be that the designers of the Arrow classes > wanted to keep things as modular as possible. > > I'm not going into the technical details of ArrowChoice (it's a bunch of > box labeling tricks once again) but in factory-visualization there is a > big difference between the if-then-else within Monad and the > if-then-else in Arrow. Remember, for Monad, after making the choice, the > rest of the factory had to be reorganized and connected before we could > continue. We, the programmers knew there were only 2 possible outcomes, > but at runtine everything was handled as if any random new factory setup > should be possible. > With Arrows, we can nicely see (before starting) that a certain part of > the assembly line will make a choice. It has 2 lines flowing from it so > it's clear that at runtime the worker will have to place the boxes on 1 > of these continuation lines. We can reason about both situations and see > the remaining layout of the factory and reason about that too. At > runtime it remains static. No moving heavy machinery around. > > I think that in 99% of all situations, this solution is way more elegant > than the monad solution. The full-dynamism that monads add really sounds > like overkill. Looking at most code, the possible code-paths *are* known > beforehand (to programmers), so it's a shame that knowledge gets > destroyed by monads by using a function (a -> m b) to "bind" the parts. > > However, in haskell, there are many nice libraries that provide monadic > interfaces and not a lot that have Arrow+ArrowChoice. Even when they > would be perfectly suitable and the dynamics of monad aren't needed. > So because of this, if you need a few of these libraries for your > application, you stick to monads, because you don't want to end up with > many different syntaxes everywhere. > > > Ok, nearing the end. This got a bit bigger than I planned =) > > > Yet another view at the arrow -> monad difference: > > class Arrow a => ArrowApply a where > app :: a (a b c, b) c > > ArrowApply is "the last step". If your arrow can implement ArrowApply > you basically are a monad and you've lost the nice static properties > that idiom and arrow gave. It's quite clear from the signature of 'app' > why this is. In this representation it's not a worker himself that > starts to reorganize the entire factory when he receives his input. In > this case he just receives a rather big box containing an entire new > assembly line to be placed in the next part of the factory, and a small > box to put into that new line. See? The same dynamism from an even more > extreme point of view :) > > > Another thing I want to point out, because it's closely related: > Alternative/ArrowPlus/MonadPlus > These provide the assembly lines with another form of > choice/combination. Of course you should note that not every > idiom(Applicative) is an Alternative, and the same is true for Arrow and > Monad. They all work when the effect has some notion of emptiness and > there is some way to combine stuff (Monoid). For Maybe, empty is Nothing > and when we have something (Just) we feel no need to combine. For lists, > [] is empty and combining is just concatenation. > So why do I mention this at all? Because it can act like a kind of > choice (if/then/else) or as a way to traverse multiple codepaths, which > is especially useful for idioms, as we've just seen these have no > native ways to do this. Of course you have to remember that this isn't > really a dynamic choice "inside". But it's not completely steered from > outside of the factory either. It's somewhat nicely halfway and of > course limited to "is it empty? / did it succeed?" type of choices only, > but in many cases (parsing for example) it can just give idioms that > extra boost it misses, without having to move to arrows/monads. > I haven't bothered thinking of a factory-visualization analogy for these > yet, because I'm afraid nobody wants to work there anymore if they have > to worry of Monoids sneaking around. > > > > Lastly: what about these static optimizations I keep mentioning? > It is explained in http://www.cse.chalmers.se/~rjmh/Papers/arrows.pdf > chapter 3. > Another nice example, which is more about reasoning about code: > http://blog.downstairspeople.org/2010/06/14/a-brutal-introduction-to-arrows > > Both examples build up static information about a computation/assembly > line without starting it yet. This information can then be used to > optimize certain parts (not run an expensive computation if we already > know the outcome), combine parts (do 2 things at once if we know they > are closely related) or to refuse to run at all unless certain > conditions (performance/security) aren't met. > > > But while having worked with dependently typed languages for some time > now, both these examples feel redundant in a way. > They both just combine a piece of static data with some dynamic data > (function). Then on startup, they collapse the static stuff, act upon > what they've learned(optimize,report back) and leave the dynamic part as > a result, to run. So in a way they are all about an ordinary function, > with some fancy extra knowledge about it that needs to be stored > somewhere, and a phase where this knowledge is used to deliver an > optimized runtime thingy. Sounds an awful lot like what compilers do, > right? Now, when these cases were worked out, haskell's type system was > not sufficient to store the static knowledge and to apply it, but > currently, with all modern extensions it's getting awfully close, if > it's not there already. > > So perhaps in the near future, we can just supply Monad with advanced > static knowledge+reasoning to give it all the nice properties that arrow > and idiom have. > > Have a nice weekend, > Mathijs > > > > _______________________________________________ > > Haskell-Cafe mailing list > > Haskell-Cafe@haskell.org > > http://www.haskell.org/mailman/listinfo/haskell-cafe > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe >
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
