One Haskell VFAQ is "What is a monad?"

Well, that's kind of like asking "What is a number?" Imagine you're in 
the steamy jungles of some distant land, when you meet a wild tribe of 
natives, who you are inexplicably able to communicate with. Suppose 
these people don't know anything at all about numbers, and one of them 
asks you "what is a number?"

Now, we use numbers all the time, right? *Everybody* knows what a number 
is. But if you meet somebody who has never encountered this concept, 
where would you even *start*? How can you explain what a number is? How 
can you even begin to explain why that's useful?

Now try explaining what a number is *briefly*.

Hard, isn't it? You either end up saying something so abstract that it's 
utterly cryptic, or you end up writing a huge long complex-sounding 
example. Either way, numbers sound like an amazingly complicated idea... 
but they aren't.

A similar thing can be said about monads. A quick Google search will 
reveal an entire cottage industry of people trying to explain them. If 
anything, this makes it seems like they *are* hard to understand. But 
really, they aren't. It's just that they're not "like" anything else 
familiar that I can easily point at. They are a really abstract concept, 
which makes them kind of hard to grasp.



The short version: A monad is one specific way of chaining operations 
together.

When all the fuss and the hype and the endless tutorials are over, 
that's all monads really come down to. They're just a particular way of 
linking operations together.



(Some people incorrectly think that a monad is for /sequencing/ 
operations. This is not correct. They /can/ be used for that, but that's 
not what they're "for", as such. Other people think that monads are for 
managing mutable state. Again, you /can/ use them to do that, but that's 
not all they do. It isn't their fundamental purpose.)



The medium version:

A monad is something that has a "bind function" which links calculation 
steps together. (In Haskell it's named ">>=", but I'm going to call it 
"the bind function", because that's a damned-site easier to read.) All 
the bind function actually does is to extract the result from the 
previous step, and feed it into the next step.

Pretty simple, eh?

Now, if the bind function /just/ does that, the result isn't very 
interesting. In fact, you could achieve exactly the same thing yourself 
without bothering with all this monad malarkey. And that brings me to a 
very important point:

   Merely BEING A MONAD isn't especially useful.

   Every USEFUL monad does something else IN ADDITION to just being a monad.

(A monad that "does nothing" is called the identity monad. Rather like 
the identity function, this /sounds/ completely pointless, yet turns out 
not to be...)

In "normal code", you might call one function, pass its result to 
another function, and then pass the result of that to a third function. 
In "monadic code", instead of each function returning a "result", it 
returns some sort of construct which /contains/ a result. And between 
each pair of functions, you insert this bind function, which fetches the 
result out of one construct and squirts it into the next function.

In Haskell, you can explicitly write out the bind function, such as

   foo x >>= bar >>= baz

Or you can write a so-called "do block", such as

   do
     y <- foo x
     z <- bar y
     baz z

Here the compiler automatically inserts all the ">>=" calls for you 
behind the scenes. So the two examples are actually identical. All a 
do-block does is insert these extra function calls for you, so you don't 
have to do it manually.

Like I said, if the bind function just passed the result along, nothing 
especially interesting would happen. The *interesting* part is that you 
can write a bind function so that it does hoopy processing between 
statements. That's where the fun begins.



The long version:

As you know, in Haskell all variables are immutable. For the moment, 
we'll pretend that all data structures are immutable too. Basically, 
once you create something, it becomes read-only.

Suppose I'm writing a "solve" function, which takes an equation, and 
returns a bool indicating whether the function can be solved or not.

   solve :: Equation -> Bool

Suppose that I've got two equations, and I want to check whether /both/ 
of them are solvable. That's pretty easy:

   (solve eq1) & (solve eq2)

Suppose that in addition to the equation to solve, you also need to pass 
some kind of table containing the equation's context (e.g., the 
definitions of any variables it mentions, or whatever). That's still 
pretty easy:

   solve :: State -> Equation -> Bool

   (solve s eq1) & (solve s eq2)

[Assuming that "s" holds whatever state it is that the "solve" function 
requires as input.]

So far, so good. Now assume that the "solve" function /changes/ the 
state as it processes each equation... Ah. OK, now we've got a bit of a 
problem.

Basically, the way to handle this is that the "solve" function needs to 
return the new, updated state back to the caller, /as well as/ the 
actual result it's trying to calculate.

   solve :: State -> Equation -> (State, Bool)

The function where I'm trying to solve both equations also presumably 
needs to return the latest version of the state to its own caller, so we 
end up writing something like this:

   let
     (s1, b1) = solve s0 eq1
     (s2, b2) = solve s2 eq2
   in (s2, b1 & b2)

On the one hand, this is all simple, straight-forward code, with nothing 
particularly complicated happening.

On the other hand... yuck! Our simple 1-line expression has degenerated 
into 4 lines of code. And imagine if I wanted to make a dozen calls to 
"solve"; I'd end up with a dozen "s"-variables. And in each function 
call, I need to make sure I use the correct "s"-variable. You just 
/know/ that at some point I'm going to make a typo, or copy-paste 
something from somewhere else and forget to tweak the variable numbers...

In short, this is a mess. (I can almost hear the Java programmers at the 
back of the room muttering "told you so".) Surely we can do better.

Well, it turns out we can. We can write a monad where the bind function 
feeds the /result/ from one function to the next, but /also/ 
automatically feeds the latest version of the state across too. So now 
our functions don't need to /explicitly/ take the state as a parameter, 
and don't need to /explicitly/ return it as a result. The monad hides 
the plumbing. With that done, I can now write

   do
     b1 <- solve eq1
     b2 <- solve eq2
     return (b1 & b2)

It's still three lines instead of one. But at least I don't have lots of 
little "s"-variables scattered all over the place now. I can't possibly 
muddle them up and introduce strange bugs because my code is looking at 
an out-of-date version of the state. The bind function takes care of 
passing along the correct version of the state at each step.

It's still more text than the original. But notice, if "solve" 
*modifies* the state, then it potentially *matters* which call happens 
first - whether we solve eq1 first or eq2 first. The original 
expression, where the state doesn't get altered, didn't specify an 
order. Heck, you could solve both equations /in parallel/ if you want. 
But if solving the second equation /depends on/ information gleaned from 
solving the first one, then it is no longer logically possible to do 
that. So the code above is longer because it specifies an execution order.



Right now, I can just hear the Java guys sneering at me.

"So let me get this straight. You had to modify your compiler to accept 
a special new syntax which you then convert into a bunch of extra calls 
to this complicated new function you wrote... just so you can have 
mutable state?... The same mutable state that every REAL programming 
language automatically supports out-of-the-box? HAHAHA! Haskell sucks, man!"

In Java of course, you can simply do

   bool b1 = solve(s, eq1);
   bool b2 = solve(s, eq2);
   return (b1 && b2);

and be done with it. Since Java passes everything by reference, solve() 
is quite capable of altering "s" just as it is. It doesn't need any 
special "monad" to do that. Heck, Java will even let you do

   return solve(s, eq1) && solve(s, eq2);

although now the execution order (I believe) isn't guaranteed any more. 
But hey, that's a hell of a lot simpler and easier, right? You know, 
using ACTUAL MUTABLE DATA to implement mutable data. :-P

Well, stick this in your pipe and smoke it: Suppose that "solve" can 
return MULTIPLE SOLUTIONS. What now? Well, every time you call solve(), 
you're going to have to loop over all of the solutions it returns, 
right? So the Java code is now going to look something like

   Solution[] s = solve(in, eq1);

   ArrayList<Solution> out = new ArrayList<Solution>();
   for (int lp=0; lp<s.length; lp++)
     out.addAll(solve(s[lp], eq2));

   return out;

Clear as mud, right?

And the Haskell version...? Well, you know what? If you put the 
foreach-loop into the bind function itself, the Haskell code remains 
EXACTLY THE SAME. All of the existing code still compiles, still runs, 
AND DOES THE RIGHT THING. Boom, head shot.

If that doesn't sound like a big deal, try cascading a dozen solve() 
calls in Java. Not funny any more, is it? Manually writing a brand new 
loop for every individual call. Oh, you could probably do something with 
the reflection API to allow you to write the code containing the 
foreach-loop just once, and pass it the name of the function you're 
trying to call next. But it's still a fair bit of work.

The Haskell code, on the other hand, remains unchanged. Because "going 
from step A to step B" has been abstracted out into this "bind 
function", we can change how it happens in just one place - the bind 
function! So all our code still works the same, we just need to change 
the implementation of the monad.



Here's an interesting thing: We can now represent an unsolvable equation 
by just RETURNING ZERO SOLUTIONS. You know what happens if you iterate 
over an empty container? It means you run the loop body ZERO TIMES. 
Running something zero times means NOT RUNNING IT.

In other words, if one of the solve() calls returns zero solutions, the 
remaining calls get AUTOMATICALLY SKIPPED.

We can actually extend this a bit. If we make it so the monad can hold a 
failure description, we can have bind check the previous result, and run 
the next step if and only if the previous one succeeded. In other words, 
WE CAN IMPLEMENT EXCEPTION THROWING AS A LIBRARY.

We can also write a function which runs one block of code, checks 
whether the result was a success or failure, and runs another block of 
code if it was a failure. In other words, WE CAN IMPLEMENT EXCEPTION 
CATCHING AS A LIBRARY.

Now C++ and Java already /have/ exception handling. But you know what? 
If /you/ implement the exception handling, then /you/ can decide how it 
should work.

For example, if solve() throws an exception, does that abort /all/ the 
solutions being computed, or just the one that threw an exception? Well, 
YOU DECIDE. You can implement it the first way, or you can implement it 
the second way. Heck, you can have DIFFERENT SORTS OF EXCEPTIONS and 
implement each one differently.

You can also do things like make the first four exceptions non-fatal, 
but the fifth exception aborts the thread and returns all five 
exceptions to the caller.

You can write a function that "decorates" exceptions as they go past, 
and in this way you can ADD A CALL STACK to your exceptions.

You can make it so that there is one monad that allows you to throw 
exceptions. Or you can make it so that all the types of exceptions that 
can be thrown show up in the type signature. In other words, you can 
implement UNCHECKED EXCEPTIONS, or you can implement CHECKED EXCEPTIONS. 
You can choose which style you fancy.

It's not just exceptions either. You can write code that emits warnings, 
and gather these up and log them at the end. (Why not just write the 
warnings directly to a log file? Well, because then if you decide you 
wanted to do something else with them, you'd have to change your solve() 
code. It's better to abstract that out.) Going the opposite way, there 
are parsing monads which feed a stream of INput INto a computation, 
rather than collecting output from it.



Using a monad allows us to simulate destructive updates in Haskell 
without actually *doing* destructive updates. People often sneer and say 
"what's the point?" Well you know what? Because it doesn't /really/ do 
destructive updates, it makes it trivial to implement features like... 
reverting to an older version of the state, without explicitly storing 
it and passing it around.

I can take my solve() code, tweak the monad a bit, and now I can insert 
a "go back to an older state" command into one branch of my function, 
without having to modify the whole damned thing to pass the old state 
around. Try doing *that* in a language were destructive updates /really 
are/ destructive updates. :-P



Writing some code that can solve an equation is one thing. Writing some 
code where you can pause the program half way through and see what it's 
doing is much, much more complicated.

But you know what? You can tweak the bind function to make a monad which 
supports PAUSING AND RESUMING.

Literally. You can tweak the monad a little, and not alter the main 
program at all, and now you can pause the main program at any point and 
have a nose around inside to see what's happening. Or even alter its 
internal data, and then resume it. And it's all in a library!

(Also: Holy ****, I just discovered coroutines! o_O Who knew it was this 
useful?!)



Now, to be clear: Everything I have done in Haskell with my monads can 
also be done in normal languages using other techniques. (They call it 
"Turing completeness".) The difference, IMHO, is that monads make a lot 
of this stuff DRASTICALLY EASIER TO DO than it would be in other languages.

If you have a large Java codebase and you suddenly decide that every 
time you call a certain function you want to iterate over the multiple 
results it returns... good luck with that. In Haskell, on the other 
hand, it's pretty simple. I don't even need to alter my existing code, 
because I've already factored out the sequencing.

There is one obvious potential problem: If monad X lets me throw 
exceptions, and monad Y lets me produce multiple results, how the heck 
do I combine those together? Well, the answer is that you can't. You can 
write a NEW monad that has both of these features, but you can't combine 
the two existing monads.

That sounds like a pretty epic failure of code reuse, right?

However, while you can't combine two *monads* together, what you *can* 
do is write "monad transformers". A transformer takes an existing monad 
and adds an extra feature to it. And this is where the identity monad 
comes in: You can start with the identity monad, which does nothing. You 
can implement everything else as transformers rather than monads. You 
can then "stack" the monads one on top of the other to implement all the 
features you want.

So, for example, you can take the identity monad, apply an exception 
transformer to it, and them apply a list transformer to that. You can 
now return multiple results, and throw exceptions.

Notice very carefully: If you throw an exception, it terminates ONE 
THREADS OF COMPUTATION. That's because the list transformer is running 
on top of the exception transformer. If you swap them around, then 
throwing an exception terminates ALL THREADS OF COMPUTATION. So it 
*matters* which order you stack the transformers in. Different orderings 
produce different behaviour, and you need to check that you're stacking 
them in the order that produces the feature set you actually want.

There are a couple of problems with transformers. First, they require 
unusual Haskell features. (If you want the code to be flexible enough to 
be worth making into a reusable library, you need some fairly advanced 
type system features.)

Second, if you want to access a command at level 3 in the transformer 
stack, you have to "lift" it from level 1 to level 2, and then from 
level 2 to level 3. You end up having to remember what level each 
command is at, and therefore how many times you need to "lift" it. All 
of which is very tedious, and breaks horribly as soon as you change the 
transformer stack.

The solution is to define classes which do the lifting automatically. 
This requires yet /more/ advanced type trickery. (It also doesn't work 
if you've got the same transformer at two different levels in the stack 
- which is sometimes useful.) It also means a combinatorial explosion of 
class instances as you define more transformers. (!)

And finally... monad transformers just make people's brains explode. So 
it's not really surprising that actually, most people seem to just end 
up implementing every monad they need from scratch again. It's easier 
that way.



Of course, sometimes you don't need a whole monad. Sometimes just an 
"applicative" is sufficient. Or sometimes you can use an "arrow". Or... 
Wait! Come back!! >_<

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> One Haskell VFAQ is "What is a monad?"

  Would it be extremely wrong to say that a monad is like a barrier?
(http://en.wikipedia.org/wiki/Barrier_%28computer_science%29)

-- 
                                                          - Warp

Post a reply to this message

On 20/04/2012 03:21 PM, Warp wrote:
> Invisible<voi### [at] devnull>  wrote:
>> One Haskell VFAQ is "What is a monad?"
>
>    Would it be extremely wrong to say that a monad is like a barrier?

Not really. Monads aren't particularly related to threading.



More like... I can write this in C:

   {
     foo();
     bar();
     baz();
   }

Obviously, this calls three functions, one after the other.

In Haskell, I can write this:

   do
     foo
     bar
     baz

What /this/ does is that between each of the function calls you can see, 
it invisibly inserts a new call to this magical "bind function" that I 
keep talking about. So it's like writing

   {
     foo();
     bind();
     bar();
     bind();
     baz();
   }

In fact, it's not even like that, because each time bind() is called, 
the entire rest of the code block is passed to it as an argument. And 
that means that bind() can decide to /not run it/, or to /run it 
multiple times/ or whatever else it feels like doing.

So, it's actually something like this:

   foo();
   bind(
     bar();
     bind(
       baz();
     );
   );

[Obviously, if that were actually valid syntax in some known programming 
language.]

Actually, it's even more complicated than that, because each call to 
bind() gets the result from the previous function call as an argument 
too. So it's more like

   ResultInfo i1 = foo();
   bind(i1,
     ResultInfo i2 = bar();
     bind(i2,
       baz();
     );
   );

Each function, even if it doesn't "return anything", is actually 
returning some kind of data structure representing the actions that the 
function took. And bind() can look at that data and decide whether or 
not it feels like running the rest of the code block.

So when I say that "a monad is a programmable semicolon", what I /mean/ 
is that everywhere there's a semicolon, the compiler is calling a 
user-defined function, which can make the code do quirky, unexpected things.

When you say it like /that/, suddenly it's not so surprising that 
monadic code can be configured to run lines multiple times, or pass 
secret data around invisibly, or whatever.

Post a reply to this message

Am 20.04.2012 15:41, schrieb Invisible:
> One Haskell VFAQ is "What is a monad?"
> ...

Somehow I get the impression that people who have never come across the 
term "monad" would be much better suited to explain the conceptual 
idea... All I understand is bollocks, but something tells me the concept 
is probably so trivial that a handful of well-chosen words could explain 
it all, if they just avoided the technical blurb and "Haskellisms".

Post a reply to this message

On 21/04/2012 03:18 PM, clipka wrote:

> All I understand is bollocks, but something tells me the concept
> is probably so trivial that a handful of well-chosen words could explain
> it all

When I write Haskell code "in a monad", the compiler is automatically 
inserting a bunch of invisible function calls to the "bind function" of 
the monad in question.

The bind function gets given two arguments: The result from the previous 
statement, and a function representing /all/ of the following 
statements. So it gets to decide if and how the rest of the code block 
executes.

In short, between every pair of statements, a bunch of user-defined code 
is invisibly being executed, allowing it to do totally hoopy things to 
how your code runs.

And that's basically /it/.

(Now wasn't that such an anti-climax? Everybody makes such a Big Deal 
out of monads, that sometimes when a person finally understands what 
they are, it doesn't seem all that impressive, so they go away thinking 
they missed something...)

Post a reply to this message

clipka <ano### [at] anonymousorg> wrote:
> All I understand is bollocks, but something tells me the concept 
> is probably so trivial that a handful of well-chosen words could explain 
> it all, if they just avoided the technical blurb and "Haskellisms".

  Most of the mathematical background in Haskell and purely functional
languages reminds me of the theory of electronics: The people in the
know seem to consider many of the topics trivial and self-evident, but
for some reason are usually unable to explain them in an understandable
manner.

  The difference is that in eletronics the concepts feel very complicated
when they try to explain them, while in Haskell they feel pretty trivial,
yet the real understanding of it always escapes the layman. For instance,
I still don't understand what currying *really* is about, and every time
I try to suggest "is like this?" the answer is "not really". It's like
some trivial-sounding but still ethereal concept that's impossible for
a mere mortal to grasp.

  And then they wonder why functional programming isn't mainstream.

-- 
                                                          - Warp

Post a reply to this message

On 21/04/2012 9:01 PM, Orchid Win7 v1 wrote:
> And that's basically /it/.

Well it tells me nothing.

-- 
Regards
     Stephen

Post a reply to this message

On 21/04/2012 09:56 PM, Stephen wrote:
> On 21/04/2012 9:01 PM, Orchid Win7 v1 wrote:
>> And that's basically /it/.
>
> Well it tells me nothing.

Heh, man... I thought "it inserts user-defined code between each pair of 
statements" would a pretty simple idea. I guess not... ;-)

Post a reply to this message

On 21/04/2012 09:24 PM, Warp wrote:

>    The difference is that in eletronics the concepts feel very complicated
> when they try to explain them, while in Haskell they feel pretty trivial,
> yet the real understanding of it always escapes the layman.

Haskell is like Go: The rules are trivial. The game IS NOT.

As far as I know, the only way to really comprehend how to play Go is to 
actually... you know... play Go. Only then do you start to understand 
what the strategy and tactics are all about.

Haskell is similar. On the surface it looks pretty easy. The entire 
language consists of a handful of simple yet very general concepts. The 
way you APPLY those concepts to solve a problem? Well, that's an art. An 
art you only really learn by doing. (ESPECIALLY since half this stuff 
isn't written down anywhere, unfortunately.)

> For instance,
> I still don't understand what currying *really* is about, and every time
> I try to suggest "is like this?" the answer is "not really".

1. You can take a 5-argument function, pass it 2 argument, and get a 
3-argument function as the result.

Examples:

- (+1) takes a number and adds one to it.

- (5 ==) takes a number and returns True if it's 5.

- "map" takes a function and a list. "map abs" takes a list of numbers 
and returns a list of positive numbers.

2. Suppose foo is a 1-argument function. If you do "foo x y", then x is 
the argument to foo itself, and y is the argument to whatever foo 
returns (which must be a function).

Example: "head" takes a list and returns the first element. If you give 
it a list OF FUNCTIONS, then obviously the result of calling "head" will 
itself be another function. So it is legal to write

   head function_list 7

It looks like we're calling "head" with 2 arguments, yet "head" is a 
1-argument function. But what is /really/ happening is that 
function_list is the argument to "head", and the 7 is then passed as an 
argument to whatever "head" RETURNS.

(Notice how the result of calling "head" would not normally be a 
function. There are lots of other examples of where a result wouldn't 
usually be a function, but under sufficiently unusual circumstances it is.)

3. If you write a class which works one way for functions, and another 
way for non-functions, then you can polymorphically handle functions 
with ANY NUMBER OF ARGUMENTS. If it weren't for currying, you'd have to 
write a separate version of the class for every size of function. And 
that would violate DRY.

For example, QuickCheck allows you to turn any function into a "test", 
provided that

- The function returns true/false values.

- All of the function's arguments support automated test data generation.

In particular, it works for 0-argument functions (i.e., constants), 
unary functions, binary functions, ternary functions, etc. Basically 
there's a class instance that says "this is how you test a Bool", and 
another that says "this is how you test a function that takes one 
argument and returns something testable". A Bool is testable, but so is 
a 1-argument function. And, by induction, an N-argument function.

>    And then they wonder why functional programming isn't mainstream.

Oh, I think that's due to a little bit more than just the ethereal 
nature of advanced concepts. It's probably more "man, this stuff is too 
different to what I'm used to; I can't be bothered with it". That and 
(most especially in the case of Haskell) a supreme lack of quality 
documentation.

Post a reply to this message

Just for giggles, what would monads look like in C++?

Well, let's pretend for a minute that C++ has a Function<X, Y> type, 
which represents a function that takes an X as input, and produces a Y 
as output. (Yes, I realise that isn't the real syntax C++ uses. Just 
pretend, for a minute.)

Further, let's pretend that you can create an anonymous function just by 
writing

   int function(int x) {return 2*x;}

Again, this obviously doesn't actually work in C++, but it makes the 
example code much easier to write.

(Actually, C++ is one of only a few languages where you probably /can/ 
implement monads "for real". But this made-up syntax makes it easier to 
quickly explain what's happening.)

Listing #1:
   Type1 x = foo();
   Type2 y = bar(x);
   Type3 z = baz(y);
   return z;

This code needs little explanation. You can write the same thing in 
Haskell as

Listing #2:
   let
     x = foo
     y = bar x
     z = baz y
   in z

Now consider this seemingly identical code:

Listing #3:
   do
     x <- foo
     y <- bar x
     z <- baz y
     return z

It seems like listing #2 and listing #3 should both be identical, right? 
Well, no. If I translate listing #3 into C++, you'll see it's 
drastically different:

Listing #4:
   Box<Type1> box_x = foo();
   return Bind(box_x,
     Box<Type3> function(Type1 x)
     {
       Box<Type2> box_y = bar(x);
       return Bind(box_y,
         Box<Type3> function(Type2 y)
         {
           Box<Type3> box_z = baz(y);
           return Bind(box_z,
             Box<Type3> function(Type3 z) {return Return(z);}
           );
         }
       );
     }
   );

Clearly, this /looks/ totally different. If you can actually /follow/ it 
all, you'll see that every statement is now followed by a call to this 
Bind() function, taking the rest of the code block as an argument. 
Important things to notice:

* The return type of foo() has changed from Type1 to Box<Type1>. This 
means that the implementation of foo() has to be changed.

* The first argument to Bind() is a Box<Type1>, but the input to its 
second argument is a Type1.

The Box<> class "forms a monad" if and only if it provides the following 
functions:

   template <typename X>
   Box<X> Return(X);

   template <typename X, typename Y>
   Box<Y> Bind(Box<X>, function<X, Box<Y>>);

(In the interests of good OO design, these should probably be /class 
methods/ rather than stand-alone functions. After all, their 
implementation is completely different for each class that behaves as a 
monad. But I will keep them as normal functions for now...)

Notice how what the Return() function does is NOTHING LIKE what a return 
statement usually means. (!) Arguably this is a rather bad naming 
choice. [You'll also notice how, in this example, Return() is completely 
redundant. Taking it out wouldn't change a thing. I only put it there 
for completeness.]

It's not hard to figure out how to implement this:

   template <typename X>
   class Box
   {
     private:
       X Datum;
     public:
       Box(X in) {Datum = in;}
       X GetDatum() {return Datum;}
   };

   template <typename X>
   Box<X> Return(X in) {return Box<X>(in);}

   template <typename X, typename Y>
   Box<Y> Bind(Box<X> in, Function<X, Box<Y>> next)
   {return next(in.GetDatum());}

(I'm guessing my syntax is wonky - even admitting that we're using 
pretend language extensions. It probably also contains at least a dozen 
incorrect or at least dubious characteristics. But the gist of it should 
be clear.)

This is a monad, but it doesn't "do" anything particularly special. With 
Box implemented this way, Listing #4 now does exactly the same thing as 
Listing #1, but 8x more complicated. Why bother?

This implementation makes Box the "identity monad". Like the identity 
function, the identity monad does... nothing. (And, like the identity 
function, this sounds like a very useless thing, but actually isn't.)

So let's try another implementation:

   template <typename X>
   class Box
   {
     private:
       std::vector<X> Data;
     public:
       Box(std::vector<X> in) {Data = in;}
       std::vector<X> GetData() {return Data;}
   };

   template <typename X>
   Box<X> Return(X in)
   {
     std::vector<X> out;
     out.push_back(in);
     return out;
   }

   template <typename X, typename Y>
   Box<Y> Bind(Box<X> box_in, Function<X, Box<Y>> next)
   {
     std::vector<X> in = box_in.GetData();
     std::vector<Y> out, temp;
     std::vector<X>::iterator iti;
     std::vector<Y>::iterator ito;
     for (iti = in.begin(); iti < in.end(); iti++)
     {
       Box<Y> box_out = next(*it);
       temp = box_out.GetData();
       for (ito = temp.begin(); ito < temp.end(); ito++)
       out.push_back(ito*);
     }
     return Box<Y>(out);
   }

Now Box<X> contains a std::vector<X> instead of just one X value. The 
Return() function now generates a 1-element vector. And the Bind() 
function now executes next() MULTIPLE TIMES, once for each element in 
the input. It then collects all the outputs from each call, and gathers 
them into a single giant vector.

(Incidentally, I couldn't figure out a direct way to just append the 
entire contents of one vector to another. Obviously there /is/ a way, 
and I'm just not looking hard enough...)

Notice how the code for foo(), bar() and baz() HAS NOT CHANGED, and the 
code that calls them HAS NOT CHANGED. And yet, now each function can 
potentially generate multiple results!

(Of course, for foo() to produce more than one output given a single 
input, then either foo() itself or some function it calls would have to 
be modified to actually make USE of this feature. But, for example, some 
function that foo() calls might change, while foo() itself remains 
unaffected, and foo() could still use this new feature of having 
multiple results.)

This is what Haskellers call the "list monad", basically. (With the 
added twist that Haskell lists are lazy, so it's possible for functions 
to produce "infinity results".)

It shouldn't be too hard to see that you could alter [the first] Box 
implementation such that it contains a success marker, and that Bind() 
only runs the next step in the chain if the previous one succeeded. You 
could also modify it to contain an error description in the case of 
failure. Then, if bar() decides to return an error-in-a-Box rather than 
a value-in-a-Box, baz() gets completely skipped. But baz() ITSELF 
doesn't need to do any explicit error checking. Bind() does that for you.

In this way, baz() returning an error-in-a-Box aborts the entire Box 
computation. A bit like... THROWING AN EXCEPTION. Except it's a library, 
not a language feature, so you can change the design of it at will. 
(E.g., make it so you have to throw three exceptions before the code 
aborts.) This is what Haskellers call the "failure monad", "error monad" 
or "exception monad".

You can also design Box to store various other auxiliary information as 
it goes along. You could have a table of data, for example, and provide 
commands to replace that table with a new one. This is how Haskell 
simulates destructive updates without ACTUALLY doing destructive updates.

(This is the difference between the State monad and the ST monad. The 
former allows you to simulate destructive updates, in the way described. 
The latter ACTUALLY DOES destructive updates, in the manner of C++ or 
Java or whatever.)

It's not hard to see how a Box could contain a string buffer and a 
character index, and you could write functions that take a Box and 
return a new Box after reading data from the string buffer. This is how 
you write parser monads.

I could continue at length, but by now you probably get the picture. 
User-defined code invisible inserted between the visible statements you 
actually wrote leads to all sorts of interesting possibilities.



Incidentally, since C++ REALLY DOES have a function type (or at least, 
function POINTER type) which can be passed as an argument, it's one of 
the few languages where it ought to be possible to implement a monad 
"for real". I might try it if I get the time.

The problem, of course, is that it's going to be so hellishly verbose 
that no sane person would ever, EVER write their C++ code like this...

Saying that, I hear C++ lets you override operator(). So perhaps the 
simplest way to describe a monad is as "override operator;". ;-)

Post a reply to this message

Le 21/04/2012 23:37, Orchid Win7 v1 nous fit lire :
> "override operator;".

are you sure you do not want "operator," instead ?
For once, I'm glad C++ does not allow such!

The overloading (?) of << and >> is already enough trauma when dealing
with streams... or not.

c = ceo << eke ;
d = kaz << ekk ;

one is a shift operation, the other is write in a stream... can you say
which one ? (and either c is an integer or a stream...)

in fact, monade seems to be the << with polymorphic type added.

(for streams, << returns a reference to updated stream (sort of), so
  cout << "hello " << "world" << endl;
is in fact ((cout << "hello") << "world ) << endl;


Now, if << is specified to return not the same reference type as the one
on the left, it can become "interesting".

But of course, then, we need a template to declare the << for the part
on right... or a lot of overloading.

I wonder if there is a deep difference between haskell & forth... or a
bit of lisp. Just that haskell dropped all ()...

Post a reply to this message

On 21/04/2012 10:17 PM, Orchid Win7 v1 wrote:
> On 21/04/2012 09:56 PM, Stephen wrote:
>> On 21/04/2012 9:01 PM, Orchid Win7 v1 wrote:
>>> And that's basically /it/.
>>
>> Well it tells me nothing.
>
> Heh, man... I thought "it inserts user-defined code between each pair of
> statements" would a pretty simple idea. I guess not... ;-)

I should have said that I am none the wiser. I still do not know what a 
monad is.

-- 
Regards
     Stephen

Post a reply to this message

On Sat, 21 Apr 2012 16:18:46 -0500, Orchid Win7 v1 <voi### [at] devnull> wrote
:

>
> 1. You can take a 5-argument function, pass it 2 argument, and get a  

> 3-argument function as the result.
>
> Examples:
>
> - (+1) takes a number and adds one to it.
>
> - (5 ==) takes a number and returns True if it's 5.
>
> - "map" takes a function and a list. "map abs" takes a list of numbers
  

> and returns a list of positive numbers.

I think I understand monads—I'll likely never try Haskell to fin
d out for  

sure.
I'm pretty sure I understand currying—at least as far as it goes
 in Python.

But I don't understand how any of these are taking a 5 argument function
,  

passing it 2 arguments, and getting a 3 argument function as a result.

  -Shay

Post a reply to this message

Orchid Win7 v1 <voi### [at] devnull> wrote:
> > For instance,
> > I still don't understand what currying *really* is about, and every time
> > I try to suggest "is like this?" the answer is "not really".

> 1. You can take a 5-argument function, pass it 2 argument, and get a 
> 3-argument function as the result.

  But that's the thing: It sounds so trivial as to defy sense. Why give
a particular name to such a trivial thing? It's like calling the act of
taking a 3-dimensional vector and expanding it to a 4-dimensional one
"potatoing", or taking two integers and adding them together "bananaing",
or taking a class and adding another class as its member "orangeing".
Why give an obscure name to such a trivial operation?

  But then when one starts asking questions like "so it's like giving
default values to function parameters?" or "so it's like writing another
function with less parameters that calls the first function by giving it
some default values as the rest of the parameters?", the answer is something
like "not really".

-- 
                                                          - Warp

Post a reply to this message

Le_Forgeron <jgr### [at] freefr> wrote:
> The overloading (?) of << and >> is already enough trauma when dealing
> with streams... or not.

> c = ceo << eke ;
> d = kaz << ekk ;

> one is a shift operation, the other is write in a stream... can you say
> which one ?

  People keep repeating that, and there's never any substance to the claim.

  I have been programming in C++ both as a hobby and professionally for
over 15 years now, and I have yet to encounter a piece of code where it's
confusing which operation is being performed.

> (and either c is an integer or a stream...)

  That's an especially dishonest example because it won't actually compile
if c is a stream because streams are not assignable.

-- 
                                                          - Warp

Post a reply to this message

Orchid Win7 v1 <voi### [at] devnull> wrote:
> Further, let's pretend that you can create an anonymous function just by 
> writing

>    int function(int x) {return 2*x;}

  You can create anonymous functions. The syntax is:

    [](int x) { return 2*x; }

  (Of course that alone won't do anything because you can't call it, as
it has no name. However, you can eg. create a variable that represents
the function, like: "auto func = [](int x) { return 2*x; };". If you need
to eg. return that function from another function, you'll have to use the
std::function wrapper. Likewise if you need to give one as parameter to
a non-templated or anonymous function.)

-- 
                                                          - Warp

Post a reply to this message

Orchid Win7 v1 <voi### [at] devnull> wrote:
> Listing #1:
>    Type1 x = foo();
>    Type2 y = bar(x);
>    Type3 z = baz(y);
>    return z;

  Btw, I don't know if this is exactly what you are looking for, but I think
it achieves at least close to what you are attempting:

    auto x = [](int i) { return i*2; };
    auto y = [x](int i) { return x(i*3); };
    auto z = [y](int i) { return y(i*5); };
    std::cout << z(3) << std::endl;

  (Capturing the other functions by value is far easier than taking them
as function parameters because this way you don't have to care about the
type of the anonymous function. Unfortunately lambda functions cannot yet
be templated, which is a bummer.)

  If you wanted to return that 'z' from a function, it's slightly less
intuitive (because function return values cannot be 'auto'). You have
to do it like this:

//--------------------------------------------------------------------
#include <iostream>
#include <functional>

std::function<int(int)> gimmeTheFunction()
{
    auto x = [](int i) { return i*2; };
    auto y = [x](int i) { return x(i*3); };
    auto z = [y](int i) { return y(i*5); };
    return z;
}

int main()
{
    auto func = gimmeTheFunction();
    std::cout << func(3) << std::endl;
}
//--------------------------------------------------------------------

-- 
                                                          - Warp

Post a reply to this message

On 04/21/2012 06:14 PM, Stephen wrote:
> On 21/04/2012 10:17 PM, Orchid Win7 v1 wrote:
>> On 21/04/2012 09:56 PM, Stephen wrote:
>>> On 21/04/2012 9:01 PM, Orchid Win7 v1 wrote:
>>>> And that's basically /it/.
>>>
>>> Well it tells me nothing.
>>
>> Heh, man... I thought "it inserts user-defined code between each pair of
>> statements" would a pretty simple idea. I guess not... ;-)
>
> I should have said that I am none the wiser. I still do not know what a
> monad is.
>

Oh that's easy ... it's just the singular form of gonad ... THUD ... 
couldn't resist ;-)

Post a reply to this message

Orchid Win7 v1 <voi### [at] devnull> wrote:
> 1. You can take a 5-argument function, pass it 2 argument, and get a 
> 3-argument function as the result.

  Would this be currying in C++?

    std::function<int(int)> multiplierFunction(int multiplier)
    {
        return [multiplier](int value) { return value * multiplier; };
    }

  The above function returns a function that takes an integral as parameter
and returns it multiplied by the specified multiplier. To better understand
it, it's used eg. like this:

    auto doubler = multiplierFunction(2);
    auto tripler = multiplierFunction(3);
    auto nMultiplier = multiplierFunction(n);

    std::cout << doubler(5); // Will print "10"
    std::cout << tripler(5); // Will print "15"
    std::cout << nMultiplier(5); // Will print the result of 5*n

-- 
                                                          - Warp

Post a reply to this message

On 22/04/2012 1:38 PM, James Holsenback wrote:
> On 04/21/2012 06:14 PM, Stephen wrote:

>>
>> I should have said that I am none the wiser. I still do not know what a
>> monad is.
>>
>
> Oh that's easy ... it's just the singular form of gonad ... THUD ...
> couldn't resist ;-)

That calls for a kick in both monads. :-P

-- 
Regards
     Stephen

Post a reply to this message

On 22/04/2012 05:33 AM, Shay wrote:
> On Sat, 21 Apr 2012 16:18:46 -0500, Orchid Win7 v1 <voi### [at] devnull> wrote:
>
>>
>> 1. You can take a 5-argument function, pass it 2 argument, and get a
>> 3-argument function as the result.
>>
>> Examples:
>>
>> - (+1) takes a number and adds one to it.
>>
>> - (5 ==) takes a number and returns True if it's 5.
>>
>> - "map" takes a function and a list. "map abs" takes a list of numbers
>> and returns a list of positive numbers.
>
> I think I understand monads—I'll likely never try Haskell to find out
> for sure.
> I'm pretty sure I understand currying—at least as far as it goes in Python.
>
> But I don't understand how any of these are taking a 5 argument
> function, passing it 2 arguments, and getting a 3 argument function as a
> result.

I couldn't find an example of a 5-argument function to demonstrate with. 
Generally, if you find yourself writing a function with that many 
arguments, you're doing it wrong.

So instead, I demonstrated with a couple of 2-argument functions 
generating 1-argument functions.

Post a reply to this message

On 22/04/2012 11:40 AM, Warp wrote:

>    But that's the thing: It sounds so trivial as to defy sense. Why give
> a particular name to such a trivial thing?

One could argue that "calling a function" is a pretty trivial idea. But 
it's still useful to have a name for it.

>    But then when one starts asking questions like "so it's like giving
> default values to function parameters?" or "so it's like writing another
> function with less parameters that calls the first function by giving it
> some default values as the rest of the parameters?", the answer is something
> like "not really".

Providing default arguments is /kind of/ similar. The difference is that 
usually you /can/ still provide explicit values which override the 
defaults. With a curried function, you /cannot/ change the arguments 
that have already been given. (Or even know if any arguments /have/ been 
give yet. All you can see is what arguments remain.)

Writing a new function that takes one fewer arguments than an existing 
one is like currying. Except that the idea behind "currying" is that 
this is /automatic/. You don't have to code it yourself. It's 
automatically available for all functions.

Finally, like I said, currying works backwards too: If a function call 
happens to return a function as its result, you can just keep appending 
arguments. "head function_list 7" and all that.

Curried functions mean that, at the language level, there is 
fundamentally no difference between taking several arguments, and 
functions that return functions that return functions.

As you say, it's /not/ an especially wild concept. But it's [usually] 
not a feature that you can add without changing the language design.

That said, you could probably design some sort of object that has 
methods for adding arguments, N at a time, and when it gets enough 
arguments, it yields an answer. And that might reasonably be described 
as currying.

Post a reply to this message

On 21/04/2012 10:53 PM, Le_Forgeron wrote:
> Le 21/04/2012 23:37, Orchid Win7 v1 nous fit lire :
>> "override operator;".
>
> For once, I'm glad C++ does not allow such!

Well, you'll notice that Haskell only does all this magical stuff IF YOU 
EXPLICITLY REQUEST IT. So any block of monadic code either has a big 
"do" right at the front of it, or all the ">>=" calls are written 
explicitly. Either way, it's pretty obvious that "hey man, something 
weird is going to happen here".

Haskell allows you to override many, many things: You can change what 
number literals mean. You can change what string literals mean. 
Obviously you can change what the various comparison and arithmetic 
operators do. Monad in a sense allow you to override the semicolon 
operator. You can even override pattern matching. But you know what? It 
/doesn't/ let you override function call syntax.

> The overloading (?) of<<  and>>  is already enough trauma when dealing
> with streams... or not.

You know, considering that C++ demands an explicit type signature on 
every tiny little thing... I'm having a hard time imagining how this 
would ever be a problem. Especially given that the argument to << is 
very, very likely to consist of at least one literal value.

> in fact, monade seems to be the<<  with polymorphic type added.

There is a (<<) function in Haskell, in fact, and yes, it's to do with 
monads. (It's the same as (>>), but with the arguments swapped around.)

> I wonder if there is a deep difference between haskell&  forth... or a
> bit of lisp. Just that haskell dropped all ()...

Haskell dropped the brackets because

1. Functions are first-class, so a "named function" is merely an 
ordinary variable who's "value" happens to be a function. So 
distinguishing between foo and foo() is not needed.

2. Functions are curried, so foo(1, 2, 3) might run the function and 
yield a result, or it might just yield a new, smaller function.

Post a reply to this message

On 22/04/2012 11:59 AM, Warp wrote:
> Orchid Win7 v1<voi### [at] devnull>  wrote:
>> Further, let's pretend that you can create an anonymous function just by
>> writing
>
>>     int function(int x) {return 2*x;}
>
>    You can create anonymous functions. The syntax is:
>
>      [](int x) { return 2*x; }
>
>    (Of course that alone won't do anything because you can't call it, as
> it has no name. However, you can eg. create a variable that represents
> the function, like: "auto func = [](int x) { return 2*x; };". If you need
> to eg. return that function from another function, you'll have to use the
> std::function wrapper. Likewise if you need to give one as parameter to
> a non-templated or anonymous function.)

Mmm, interesting.

So how do you call such a function? Does it just override the usual 
function call notation?

Post a reply to this message

>> Heh, man... I thought "it inserts user-defined code between each pair of
>> statements" would a pretty simple idea. I guess not... ;-)
>
> I should have said that I am none the wiser. I still do not know what a
> monad is.

If you have a set of things which can be "added" and "subtracted" in a 
certain technical sense, this is called a monoid.

(The technical rules say things like "if you add X and Y, and then 
subtract Y, the result has to be X". Stuff like that.)



A monad is a little more complicated, but essentially, if you have

- A "box" type of some sort.

- A "return" function that takes a value and sticks it in a box.

- A "bind" function that takes a box and a function that returns a box, 
and calls that function with the thing(s) in the input box.

then that's a monad.

(Once again, there's a bunch of technical rules that make this 
mathematically rigorous. Technically the functions have to obey certain 
rules - the "monad laws" - such as "bind x id == x". But usually any 
sane way of implementing the two functions about will satisfy the 
requirements.)

Post a reply to this message

On 22/04/2012 01:43 PM, Warp wrote:
> Orchid Win7 v1<voi### [at] devnull>  wrote:
>> 1. You can take a 5-argument function, pass it 2 argument, and get a
>> 3-argument function as the result.
>
>    Would this be currying in C++?
>
>      std::function<int(int)>  multiplierFunction(int multiplier)
>      {
>          return [multiplier](int value) { return value * multiplier; };
>      }
>
>    The above function returns a function that takes an integral as parameter
> and returns it multiplied by the specified multiplier.

Yeah, I think that would satisfy my idea of "curried function".

The question is, does

   multiplierFunction(3)(4)

or similar yield a 12?

Post a reply to this message

Am 22.04.2012 17:40, schrieb Orchid Win7 v1:
> On 22/04/2012 11:40 AM, Warp wrote:
>
>> But that's the thing: It sounds so trivial as to defy sense. Why give
>> a particular name to such a trivial thing?
>
> One could argue that "calling a function" is a pretty trivial idea. But
> it's still useful to have a name for it.
>
>> But then when one starts asking questions like "so it's like giving
>> default values to function parameters?" or "so it's like writing another
>> function with less parameters that calls the first function by giving it
>> some default values as the rest of the parameters?", the answer is
>> something
>> like "not really".
>
> Providing default arguments is /kind of/ similar. The difference is that
> usually you /can/ still provide explicit values which override the
> defaults. With a curried function, you /cannot/ change the arguments
> that have already been given. (Or even know if any arguments /have/ been
> give yet. All you can see is what arguments remain.)
>
> Writing a new function that takes one fewer arguments than an existing
> one is like currying. Except that the idea behind "currying" is that
> this is /automatic/. You don't have to code it yourself. It's
> automatically available for all functions.

Maybe that's what scrambles my mind whenever I read "Haskellists'" 
explanations of stuff: They're so proud that Haskell does it 
automatically for you, that they tend to deny the obvious parallels.

So yes: Currying *is* like writing a function that takes fewer 
arguments, calling the original one and supplying (unchangeable) 
defaults for the missing arguments.

And yes, apparently Haskell provides syntactic sugar for that. Wow. Big 
deal.

> Finally, like I said, currying works backwards too: If a function call
> happens to return a function as its result, you can just keep appending
> arguments. "head function_list 7" and all that.

Again, nice-to-have syntactic sugar, but nothing conceptually 
fascinating (as you noted yourself).

> That said, you could probably design some sort of object that has
> methods for adding arguments, N at a time, and when it gets enough
> arguments, it yields an answer. And that might reasonably be described
> as currying.

No. That might reasonably be described as nothing but bullshit.

Post a reply to this message

Am 22.04.2012 17:56, schrieb Orchid Win7 v1:
> On 22/04/2012 01:43 PM, Warp wrote:
>> Orchid Win7 v1<voi### [at] devnull> wrote:
>>> 1. You can take a 5-argument function, pass it 2 argument, and get a
>>> 3-argument function as the result.
>>
>> Would this be currying in C++?
>>
>> std::function<int(int)> multiplierFunction(int multiplier)
>> {
>> return [multiplier](int value) { return value * multiplier; };
>> }
>>
>> The above function returns a function that takes an integral as parameter
>> and returns it multiplied by the specified multiplier.
>
> Yeah, I think that would satisfy my idea of "curried function".
>
> The question is, does
>
> multiplierFunction(3)(4)
>
> or similar yield a 12?

Sure, why not? multiplierFunction(3) returns a valid function, so 
invoking its () operator calls the function with the respective 
parameter(s).

(You could achieve the same syntax by having multiplierFunction() return 
an object with an overridden () operator rather than a function, but of 
course that would be cheating.)

Post a reply to this message

clipka <ano### [at] anonymousorg> wrote:
> So yes: Currying *is* like writing a function that takes fewer 
> arguments, calling the original one and supplying (unchangeable) 
> defaults for the missing arguments.

  I think that the difference is that the new function is not static,
but it's generated dynamically. (In other words, what you end up is a
new function which fixes some of the parameters of the original function,
but the values to which they are fixed is determined at runtime rather
than at compile time.)

  This means, if I understand correctly, that you could for example create
such functions in a loop (or, as we are talking about functional languages,
in a recursive manner), which is quite difficult to achieve with static,
compile-time functions. (I suppose you could try to emulate this in a
statically typed language with no lambda functions, but you would need
some kind of stack or something where the fixed parameter values are
stored.)

  There are probably even deeper implications.

-- 
                                                          - Warp

Post a reply to this message

Orchid Win7 v1 <voi### [at] devnull> wrote:
> The question is, does

>    multiplierFunction(3)(4)

> or similar yield a 12?

  Yes.

-- 
                                                          - Warp

Post a reply to this message

clipka <ano### [at] anonymousorg> wrote:
> (You could achieve the same syntax by having multiplierFunction() return 
> an object with an overridden () operator rather than a function, but of 
> course that would be cheating.)

  That's kind of what the C++ lambda does internally: It puts the captured
variables in some kind of internal struct, which the function then operates
with (similarly to how a class member function operates with the object
using the 'this' pointer). You could achieve a similar behavior by writing
a class, but a lambda achieves this with significantly less effort.

  There is a significant difference to a class, though. In this example
std::function<int(int)> can manage *any* lambda function that takes an
int and returns an int, not just ones that have captured a 'multiplier'
variable and perform a "value * multiplier" on it.

  If you implemented the functionality of the example I wrote with a
class, you would be fixing the "lambda" function to be only and exactly
a multiplier function that has to be used with exactly your class and
nothing else. std::function<int(int)> has no such limitation. Any function
(be it a static function or a lambda) that takes an int and returns one
will do.

  This can make a difference especially with non-templated functions that
take a std::function as parameter. (One advantage of std::function over a
generic functor is that the former does not require for the code that uses
it to be templated and thus doesn't suffer form the few limitations that
templated code has.)

-- 
                                                          - Warp

Post a reply to this message

Orchid Win7 v1 <voi### [at] devnull> wrote:
> >    You can create anonymous functions. The syntax is:
> >
> >      [](int x) { return 2*x; }
> >
> >    (Of course that alone won't do anything because you can't call it, as
> > it has no name. However, you can eg. create a variable that represents
> > the function, like: "auto func = [](int x) { return 2*x; };". If you need
> > to eg. return that function from another function, you'll have to use the
> > std::function wrapper. Likewise if you need to give one as parameter to
> > a non-templated or anonymous function.)

> Mmm, interesting.

> So how do you call such a function? Does it just override the usual 
> function call notation?

  A variable that points to such an anonymous function works like any
function pointer, which means you can call it like a regular function.
Thus if you have, for example:

    auto func = [](int x) { return 2*x; };

then you can simply call it like

    func(5);

  Templates taking a functor as parameter work the same way. You could
have something like:

    template<typename T, typename Comparator>
    bool compare(const T& value1, const T& value2,
                 const Comparator& comparatorFunction)
    {
        return comparatorFunction(value1, value2);
    }

  In the above example any comparator function will do (a comparator
function is something that behaves like a function taking two parameters
and returns a boolean). This can be a regular function, a functor (a class
that behaves like a function), a lambda, or an object of type std::function.
Thus you can call it eg. like:

    compare(1, 3, [](int v1, int v2) { return v1 < v2; })

-- 
                                                          - Warp

Post a reply to this message

On 04/22/2012 09:06 AM, Stephen wrote:
> On 22/04/2012 1:38 PM, James Holsenback wrote:
>> On 04/21/2012 06:14 PM, Stephen wrote:
>
>>>
>>> I should have said that I am none the wiser. I still do not know what a
>>> monad is.
>>>
>>
>> Oh that's easy ... it's just the singular form of gonad ... THUD ...
>> couldn't resist ;-)
>
> That calls for a kick in both monads. :-P
>

hmmmm ... nonads (well that's self explanatory) better yet faux-nads ... 
someone who thinks that gotta pair. OK I'll stop now ;-)

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> One Haskell VFAQ is "What is a monad?"

http://byorgey.files.wordpress.com/2011/05/monad_tutorial.jpg

-- 
                                                          - Warp

Post a reply to this message

>> The question is, does
>
>>     multiplierFunction(3)(4)
>
>> or similar yield a 12?
>
>    Yes.

Right. So if you implemented all your stuff to take one argument at a 
time like this [which would presumably be a little bit of work], IMHO 
you could perfectly well call that "curried functions".

Post a reply to this message

On 22/04/2012 06:03 PM, Warp wrote:
>    That's kind of what the C++ lambda does internally: It puts the captured
> variables in some kind of internal struct, which the function then operates
> with (similarly to how a class member function operates with the object
> using the 'this' pointer). You could achieve a similar behavior by writing
> a class, but a lambda achieves this with significantly less effort.

Oh, so it can capture local variables too? That's even better than I 
thought...

Post a reply to this message

On 22/04/2012 05:34 PM, clipka wrote:

> Maybe that's what scrambles my mind whenever I read "Haskellists'"
> explanations of stuff: They're so proud that Haskell does it
> automatically for you, that they tend to deny the obvious parallels.
>
> So yes: Currying *is* like writing a function that takes fewer
> arguments, calling the original one and supplying (unchangeable)
> defaults for the missing arguments.
>
> And yes, apparently Haskell provides syntactic sugar for that. Wow. Big
> deal.
>
>> Finally, like I said, currying works backwards too: If a function call
>> happens to return a function as its result, you can just keep appending
>> arguments. "head function_list 7" and all that.
>
> Again, nice-to-have syntactic sugar, but nothing conceptually
> fascinating (as you noted yourself).

You seem to be missing the third point: Function currying allows you to 
write code that polymorphically accepts functions with ANY number of 
arguments.

That can be a Big Deal.

That said, yeah, of all the things that Haskell does, function currying 
is one of the less exciting ones.

Post a reply to this message

>> One Haskell VFAQ is "What is a monad?"
>
> http://byorgey.files.wordpress.com/2011/05/monad_tutorial.jpg

Post a reply to this message

Attachments:
Download '960526421_mnnqb-o-1.jpg' (24 KB)

Preview of image '960526421_mnnqb-o-1.jpg'

On 22/04/2012 6:44 PM, James Holsenback wrote:
> hmmmm ... nonads (well that's self explanatory) better yet faux-nads ...
> someone who thinks that gotta pair. OK I'll stop now ;-)

I think, for everyone's sake, that you had better. ;-)

-- 
Regards
     Stephen

Post a reply to this message

On 22/04/2012 08:44 PM, Stephen wrote:
> On 22/04/2012 6:44 PM, James Holsenback wrote:
>> hmmmm ... nonads (well that's self explanatory) better yet faux-nads ...
>> someone who thinks that gotta pair. OK I'll stop now ;-)
>
> I think, for everyone's sake, that you had better. ;-)

Christ knows what happens if I ever try to explain group 
homomorphisms... o_O

Post a reply to this message

On 22/04/2012 8:52 PM, Orchid Win7 v1 wrote:
> On 22/04/2012 08:44 PM, Stephen wrote:
>> On 22/04/2012 6:44 PM, James Holsenback wrote:
>>> hmmmm ... nonads (well that's self explanatory) better yet faux-nads ...
>>> someone who thinks that gotta pair. OK I'll stop now ;-)
>>
>> I think, for everyone's sake, that you had better. ;-)
>
> Christ knows what happens if I ever try to explain group
> homomorphisms... o_O

LOL
And I think, for everyone's sake, that you had better not. ;-)

-- 
Regards
     Stephen

Post a reply to this message

On 4/21/2012 13:24, Warp wrote:
> I try to suggest "is like this?" the answer is "not really".

That's part of the problem. Occasionally there will be relatively simple 
concepts that aren't "like" anything else. You just have to learn the concept.

It's like I read someone wrote about quantum computers. Someone asked "can 
you give an example of how that quantum computer algorithm would be written 
for a normal computer?"  And the person said "No. That's the point. If you 
could write it for a normal computer, you wouldn't need a quantum computer."

In the case of currying, the simple concept is that a function F that takes 
arguments X, Y, and Z, is the same as a function G that takes argument X and 
returns a function that takes Y and Z, such that for all X, F(X,Y,Z) 
returning G_x(Y,Z) implies G_x(Y,Z) returns the same as F(X,Y,Z). It's a 
simple mathematical statement, not "like" anything in an imperative language 
that doesn't do currying.

-- 
Darren New, San Diego CA, USA (PST)
   "Oh no! We're out of code juice!"
   "Don't panic. There's beans and filters
    in the cabinet."

Post a reply to this message

On 4/22/2012 9:51, Warp wrote:
> but the values to which they are fixed is determined at runtime rather
> than at compile time.)

You'd wind up having something closer to "objects" with an "invoke" method 
(or functors, if I recall the C++ term).  It's just that Haskell makes that 
automatic, in the same way the new C++ makes class definitions automatic 
when you type a lambda expression. Given enough convenience, you get a 
qualitative difference.

>    There are probably even deeper implications.

In all honesty, currying was created for computer science, not for computer 
programming. It was invented so you could prove things about a one-argument 
function that returns one value and apply those proofs to functions that 
take multiple arguments and return multiple values. I.e., it was invented 
for the same reason it was useful to invent UTMs, or to prove that any 
2-tape TM can be emulated by a one-tape TM.

-- 
Darren New, San Diego CA, USA (PST)
   "Oh no! We're out of code juice!"
   "Don't panic. There's beans and filters
    in the cabinet."

Post a reply to this message

On 4/22/2012 11:34, Orchid Win7 v1 wrote:
> Oh, so it can capture local variables too? That's even better than I thought...

It can capture values of local variables, or references to non-local (to the 
lambda) variables. It doesn't really capture variables.

-- 
Darren New, San Diego CA, USA (PST)
   "Oh no! We're out of code juice!"
   "Don't panic. There's beans and filters
    in the cabinet."

Post a reply to this message

On 4/21/2012 14:37, Orchid Win7 v1 wrote:
> Again, this obviously doesn't actually work in C++, but it makes the example
> code much easier to write.

Note that both of these are perfectly fine in C#. :-)

> Incidentally, since C++ REALLY DOES have a function type (or at least,
> function POINTER type) which can be passed as an argument, it's one of the
> few languages where it ought to be possible to implement a monad "for real".
> I might try it if I get the time.

There are lots of languages that let you can pass a function as an argument.

-- 
Darren New, San Diego CA, USA (PST)
   "Oh no! We're out of code juice!"
   "Don't panic. There's beans and filters
    in the cabinet."

Post a reply to this message

On 23/04/2012 04:51 AM, Darren New wrote:
> On 4/21/2012 14:37, Orchid Win7 v1 wrote:
>> Again, this obviously doesn't actually work in C++, but it makes the
>> example code much easier to write.
>
> Note that both of these are perfectly fine in C#. :-)

I'd be surprised if I just happened to guess the right syntax for it. ;-)

>> Incidentally, since C++ REALLY DOES have a function type (or at least,
>> function POINTER type) which can be passed as an argument, it's one of
>> the
>> few languages where it ought to be possible to implement a monad "for
>> real".
>
> There are lots of languages that let you can pass a function as an
> argument.

Heh. I bet most of them are scripting languages though. :-P

Post a reply to this message

On 22/04/2012 07:19 PM, Warp wrote:
> http://byorgey.files.wordpress.com/2011/05/monad_tutorial.jpg

Coming back to what I said earlier... Monads aren't actually that 
complicated. It's just that it's a rather abstract idea, and it's not 
really "like" anything else most programmers will be familiar with.

I think the huge profusion of monad tutorials just reinforces the idea that

1. Monads are really, really hard.

2. Monads are incredibly important. (I.e., if you don't understand them, 
you can never use Haskell.)

3. Once you understand them, it will fundamentally change your life.

None of these statements are actually true...

Post a reply to this message

Am 23.04.2012 10:05, schrieb Invisible:

>>> Incidentally, since C++ REALLY DOES have a function type (or at least,
>>> function POINTER type) which can be passed as an argument, it's one of
>>> the
>>> few languages where it ought to be possible to implement a monad "for
>>> real".
>>
>> There are lots of languages that let you can pass a function as an
>> argument.
>
> Heh. I bet most of them are scripting languages though. :-P

Meh. Even good old Turbo Pascal had function pointers.

Post a reply to this message

>>> There are lots of languages that let you can pass a function as an
>>> argument.
>>
>> Heh. I bet most of them are scripting languages though. :-P
>
> Meh. Even good old Turbo Pascal had function pointers.

O RLY?

Because, I was actually *looking* for that feature, and couldn't find 
it. It would have been quite helpful...

Post a reply to this message

OK, so "magma" consists of a set S and a binary operator #. The # 
operator takes any two elements of S (including the possibility of two 
copies of the same element), and yields a new element of S (possibly the 
same one you started with).

   ∀ x, y ∈ S, x # y ∈ S.

The only "rules" as such are picky, hair-splitting ones. Stuff like "x # 
y" must have a single, definite value for all possible inputs. (If, for 
example, # stands for division, then if y=0, there is no defined result. 
If we're working with integers only, 2/3 isn't an integer. And so on.)

A magma isn't especially interesting by itself. However, if we add the 
rule that # must be /associative/, then we got a "semigroup".

   ∀ x, y, z ∈ S, (x # y) # z = x # (y # z).

Already this begins to have interesting mathematical properties. But if 
we add a special /identity element/, we get a "monoid".

   ∃ i ∈ S: ∀ x ∈ S, i # x = x # i = x.

So what are we really saying? We're saying that a monoid is a set of 
things that have a procedure for combining them, and that there has to 
be a special one where combining it does nothing.

There are many possible examples of this. For example, if S is a set of 
numbers and # denotes addition, then 0 is our identity element. (Every 
child knows that x + 0 = x.) Less obviously, if # denotes 
multiplication, our identity element is 1. (Since 1 * x = x.)

But there are other examples too. If S is the set of all possible text 
strings, and # denotes concatenation, then the identity element is the 
empty string. (Appending or prepending an empty string does nothing.) If 
S is the set of all 1-argument functions [with the same return type as 
their argument type], and # denotes function composition, then the 
identity FUNCTION is the identity ELEMENT. (Bet you can't work out how 
/that/ naming scheme came about. :-P )

If you now take your monoid and give every element a corresponding 
/inverse element/, then you have a "group".

   ∀ x ∈ S, ∃ y ∈ S: x # y = y # x = i.

For example, in the monoid of numbers where # is addition, the inverse 
of (say) 5 would be -5. And hence, numbers and addition actually form a 
/group/, not just a monoid.

Considering strings, however, there is no string that you can append to 
something which "undoes" the act of appending an earlier string. So 
strings with concatenation form a monoid, but not a group.



All of this is fascinating, of course, but not directly related to MONADS.

If somebody asks "what is a monad?", the stereotypical response is

   "A monad is just a monoid in the category of endofunctors - what's 
the problem?"

The problem, obviously, is that if you don't know category theory, this 
makes not one shred of sense.

A less abstract way to think about it is this: If you have a value like 
x, you can put that inside a "box", which I will denote as [x]. Any 
value can be put in a box; in particular, you can put a /box/ in a box, 
for example [[x]].

Every /monad/ is also a /functor/. This merely means that there's a 
function (usually called "map"):

   map :: (x -> y) -> ([x] -> [y])

In other words, it takes a function that works an x-values, and turns it 
into a function that works on boxes containing x-values. (And instead of 
returning y-values, it now returns boxes containing y-values.) In 
summary, it "lifts" a function from working on values, to working on 
values in boxes.

The alternative way to think about map is

   map :: (x -> y) -> [x] -> [y]

In other words, given a function from x to y, and an x in a box, I will 
give you a y in a box.

Either way, there's a way to apply an ordinary function to values in 
boxes. Given that, there are two equivalent ways to define a monad. They 
both involve a function called "return":

   return :: x -> [x]

Return just takes a value and puts it in a box. "Inject" or "insert" 
might be a better name, but for some reason we're stuck with "return". 
Ho hum.

The other function is either "join" or "bind". One can be defined from 
the other - although this is highly non-obvious.

Join is the easy one to understand:

   join :: [[x]] -> [x]

It takes a box within a box, and gives you just a box. It removes one 
level of boxiness. That's pretty easy to comprehend.

Bind, on the other hand, has the hoopy type signature

   bind :: [x] -> (x -> [y]) -> [y]

In other words, given...
- An x in a box.
- A function that wants an x and gives you a y in a box
...I can give you a y in a box.

Notice how the x arrives IN A BOX, but the function expects a value NOT 
IN A BOX. So bind has to take a value /out/ of a box. Right? Right??

Actually... no. You can implement it just using join:

   bind box_x function = join (map function box_x)

Applying the function to the x inside the [x] yields a result of type 
[[y]]. Applying join to that turns it from [[y]] into [y] - the required 
result type.

Less obvious still is that join can be defined using bind:

   join bbx = bind bbx id

Here "id" is the identity function - i.e., a function that takes one 
argument, and just returns it unchanged. Recall that bind takes a value 
out of a box and passes it to a function. Well in this case, the value 
in the box is another box, so if we just /return/ that, we'll have only 
one level of boxing.

Usually it's bind that you actually want to /use/, and hence it's more 
efficient to define join in terms of bind, rather than the other way 
around. (Haskell actually lets you define return and bind without 
bothering with map at all. Map can be defined in terms of bind and 
return, after all: map f = bind (return . f).)



The really hoopy thing, of course, is that this "box" I keep talking 
about usually isn't just a simple box. (If it were, that would give you 
the identity monad, which is the most boring monad there is.) Usually 
it's something more interesting.

For example, if [x] represents a /list/ of x-values (as it does in 
Haskell, by the way), then [[x]] is a list of lists, and join is just 
flattening a list of lists into a single list. Alternatively, bind is 
mapping your function over every element of the list, and then 
flattening the resulting list of lists into a single list. (You will 
sometimes hear Haskell's bind operator is being "concatMap". "concat" is 
a standard library function that does what join does above; "concatMap" 
does the same as calling map and then concat.)

Sometimes, however, Haskellers do crazy things, like where your "box 
with an x in it" is actually a /function/ which takes half a dozen 
arguments and then /returns/ an x. For example, if [x] means "a function 
that takes a dictionary and then returns an x", then... Well, we end up 
with /a lot/ of different functions flying around, which can sound a bit 
confusing. But here it is:

- return(x) just generates a new function that accepts a dictionary, 
ignores it, and always returns x anyway.

- map(f,g) is easy enough. Return a function that takes a dictionary, 
calls g with that dictionary, and then applies f to the result.

- join(f) is taking a function that returns a function that returns an 
x. At this point we don't /have/ a dictionary, so we have nothing to 
actually /call/ f with as an argument. But we want to make a function 
that takes a dictionary and returns an x. So we write a function that 
takes a dictionary argument, calls f with it, and then calls the result 
of f again with the same argument.

- Given that we have join() and map(), it's clear that bind() should be 
implementable. But can we do it more directly? In fact, all bind(f,g) 
does is return a function that takes a dictionary, calls f with that 
argument, and then passes the result to g. Quite easy, really.

As a result of all this jiggery-pokery, you can write simple-looking 
code, but it invisibly has access to this dictionary that we keep 
passing around the place. For that to actually be useful, you need a way 
to /fetch/ the dictionary. You go that by writing a function like

   get_dictionary :: [dictionary]

Notice that this doesn't appear to be a /function/ at all; it takes no 
arguments, after all. But it appears to be a "dictionary in a box" - and 
as we just discussed, in this instance our "box" is really "a function 
that takes a dictionary and returns something". It should be obvious how 
you would write "a function that takes a dictionary and returns a 
dictionary".

So this complex arrangement of stuff allows every piece of code that 
runs inside this specific monad to have [read-only] access to a 
dictionary object. (Obviously it's not hard to change it to be some 
other sort of object instead.) This is the so-called "reader monad".

It's all fascinating stuff... but rather mind-bending in places. ;-)

Post a reply to this message