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