[Haskell-cafe] Explaining monads

[Tillmann Rendel]

Ronald Guida wrote:
> Here's a toy language, described by a regular expression:
>  0(10)*110
> 
> I want to read characters, one at a time, and eventually decide to
> "Accept" or "Reject" a string.
> 
> Let me try to understand my options.
> 
> * With a simple Arrow, I can create a fixed sequence of "read"
>   operations, and I can't act on the results (i.e. by choosing
>   whether or not to keep reading) at run-time.

Nothing stops your Arrow-based RegExp-library from defining suitable 
combinators to implement choices in RegExp's without using ArrowChoice 
or ArrowApply. But if your Arrow-type is abstract, the users of your 
library can only use the combinators you provided, so you can safely 
assume they do only RegExp parsing, and optimize your Arrows in the 
runRegExp-function for the special case of RegExp-matching.

But if you decide to expose ArrowApply-functionality to the users of 
your RegExp-library, they are able to define arbitrary string matching 
on top of your RegExp library, so you can't do any optimizations because 
you never know what your users decided to do.

 From a software engineering point of view, the idea of 
Arrow-and-only-Arrow is to encode the whole computation in the internal 
structure of the arrow, independent of the interpreting language 
Haskell. This internal structure could be as expressible as Haskell. In 
contrast, ArrowApply and Monad use regular Haskell expressions for 
everything Haskell can do (like if-then-else, recursion, ...) and only 
encode special operations into the internal structure (like access to 
state, nondeterminism, ...).

This distinction is reflected in the treatment of variables in 
arrow-based vs. monadic code. monadic code can use normal Haskell 
variables, arrow-based code has to keep the variables "inside" the arrow 
in some structure.

   Tillmann