<div dir="ltr"><div><div></div>You just made my day.<br>I was trying to understand these things so hard and couldn&#39;t get it.<br>Your analogies were brilliant.<br><br></div><div>I&#39;ll read all links/papers posted here to get a deeper understanding of these things.<br>

</div><div>I&#39;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">&lt;<a href="mailto:mathijs@bluescreen303.nl" target="_blank">mathijs@bluescreen303.nl</a>&gt;</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 &lt;<a href="mailto:evohunz@gmail.com">evohunz@gmail.com</a>&gt; writes:<br>

&gt; I just stumbled upon the Applicative term.<br>
&gt; Arrows are quite difficult for me to understand at the moment.<br>
&gt; I guess it needs time to digest.<br>
&gt; But, as I understand so far, Applicative and Arrows looks like the same<br>
&gt; thing.<br>
&gt; Please, enlight me.<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>
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>
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>
Basic combining strategy: i (a -&gt; b) -&gt; i a -&gt; i b<br>
Sequencing: effects are applied in sequence<br>
            values (stuff &quot;inside&quot;) are isolated<br>
Shape depends on values: no<br>
Basic combining strategy: a b c -&gt; a c d -&gt; a b d<br>
Sequencing: effects are applied in sequence<br>
            values are sequenced too<br>
            values can &quot;see&quot; upstream results<br>
Shape depends on values: static choices only<br>
Basic combining strategy: m a -&gt; (a -&gt; m b) -&gt; m b<br>
Sequencing: effects are applied in sequence<br>
            values are sequenced too<br>
            values can &quot;see&quot; upstream results<br>
Shape depends on values: yes, fully dynamic<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 &quot;carries state around&quot;(State), &quot;can<br>
fail&quot;(Maybe), &quot;multiple answers&quot;(List) and more. Values are the pure<br>
stuff &quot;inside&quot;, and what I call &#39;shape&#39; is the general control flow of a<br>
Furthermore, I visualize these abstractions by thinking of a factory<br>
hall with boxes (values), people (effects) and an assembly line<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>
pure (+) &lt;*&gt; Just 3 &lt;*&gt; 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&#39;t know anything about the<br>
effects that happened.<br>
In &quot;factory visualization&quot;: every part of the computation (stuff between<br>
&lt;*&gt;) 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>
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&#39;s easy to<br>
reason about the program/costs. Garbage collection (sending workers<br>
home) is easier, because it&#39;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>
Let&#39;s see an example of that(State):<br>
pure const &lt;*&gt; get &lt;*&gt; 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 &quot;const&quot; and send it downstream. The second worker gets the seeded<br>
state from the &quot;state cupboard&quot; 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&#39;s ready, he packs a box with (). At the end of the<br>
line, someone opens the boxes &quot;const&quot; &quot;4&quot; and &quot;()&quot;, which computes to<br>
just 4. So we end up with the answer 4 and an updated cupboard<br>
containing 8.<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&#39;s boxes.<br>
Now, let&#39;s skip Arrows for a minute and move straight to Monads:<br>
get &gt;&gt;= \x -&gt; put (x + 1) &gt;&gt; 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>
&quot;see&quot; upstream values and upstream effects and influence the effects and<br>
shape of things to come further &quot;downstream&quot;.<br>
Another example (State again):<br>
do x &lt;- get<br>
   if x &gt; 100<br>
     then do put 0<br>
             return &quot;overflow&quot;<br>
     else do put (x+1)<br>
             executeBatch x<br>
             return &quot;normal operation&quot;<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>
But let&#39;s look a bit closer at how Monad performs this trick:<br>
get &gt;&gt;= (\x -&gt; put (x + 1) &gt;&gt;= (\_ -&gt; return x))<br>
get &gt;&gt;= (\x -&gt;<br>
  if x &gt; 100 then (put 0 &gt;&gt;= (\_ -&gt; return &quot;overflow&quot;))<br>
             else (put (x+1) &gt;&gt;= (\_ -&gt;<br>
                    executeBatch x &gt;&gt;= (\_ -&gt;<br>
                    return &quot;normal operation&quot;))))<br>
I&#39;ve added parentheses to clearly show the &quot;parts&quot; involved.<br>
Basically both these cases look like<br>
get &gt;&gt;= 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&#39;t know what will happen next until we are<br>
already running.<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>
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&#39;s going on, but far less well than with<br>
idioms, as things really depend on runtime inputs now.<br>
Now, let&#39;s look at Arrows and how they tackle the same problem:<br>
get &gt;&gt;&gt; arr (\x -&gt; (x + 1, x) ) &gt;&gt;&gt; first put &gt;&gt;&gt; arr snd<br>
or using arrow syntax:<br>
proc _ -&gt; do<br>
  r &lt;- get -&lt; ()<br>
  put -&lt; r + 1<br>
  returnA -&lt; r<br>
In factory-visualization: workers can look inside each other&#39;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>
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&#39;s up with these &quot;arr&quot; 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&#39;t<br>
needed anymore so they don&#39;t have to travel all the way to the end of<br>
the line.<br>
So from this example it&#39;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&#39;t lead to readable code and I&#39;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&#39;s just ugly.<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>
I&#39;m not going into the technical details of ArrowChoice (it&#39;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&#39;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>
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&#39;s a shame that knowledge gets<br>
destroyed by monads by using a function (a -&gt; m b) to &quot;bind&quot; the parts.<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&#39;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&#39;t want to end up with<br>
many different syntaxes everywhere.<br>
Ok, nearing the end. This got a bit bigger than I planned =)<br>
Yet another view at the arrow -&gt; monad difference:<br>
class Arrow a =&gt; ArrowApply a where<br>
    app :: a (a b c, b) c<br>
ArrowApply is &quot;the last step&quot;. If your arrow can implement ArrowApply<br>
you basically are a monad and you&#39;ve lost the nice static properties<br>
that idiom and arrow gave. It&#39;s quite clear from the signature of &#39;app&#39;<br>
why this is. In this representation it&#39;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>
Another thing I want to point out, because it&#39;s closely related:<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&#39;ve just seen these have no<br>
native ways to do this. Of course you have to remember that this isn&#39;t<br>
really a dynamic choice &quot;inside&quot;. But it&#39;s not completely steered from<br>
outside of the factory either. It&#39;s somewhat nicely halfway and of<br>
course limited to &quot;is it empty? / did it succeed?&quot; 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&#39;t bothered thinking of a factory-visualization analogy for these<br>
yet, because I&#39;m afraid nobody wants to work there anymore if they have<br>
to worry of Monoids sneaking around.<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>
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&#39;t met.<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&#39;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&#39;s type system was<br>
not sufficient to store the static knowledge and to apply it, but<br>
currently, with all modern extensions it&#39;s getting awfully close, if<br>
it&#39;s not there already.<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>
Have a nice weekend,<br>
<div class="HOEnZb"><div class="h5"><br>
&gt; _______________________________________________<br>
&gt; Haskell-Cafe mailing list<br>
&gt; <a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
&gt; <a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>