Lambda the Ultimate

In imperative language, people use typdef to avoid such long declaration.

No, in (certain) imperative languages people use typedef to avoid abominations like

template<class A, class B>
pair<B,StdGen> (*(*bind(pair<B,StdGen> (*(*)(A))(StdGen)))(pair<A,StdGen> (*)(StdGen)))(StdGen);

which are not hard but impossible to understand. ;-)

That's what I call "syntax that doesn't help"!

Edit: Not that

template<class T>
typedef pair<T,StdGen> Randomised(StdGen);

template<class A, class B>
Randomised<B> *(*bind(Randomised<B> *(*)(A)))(Randomised<A>*);

would be any more pleasent to read. And the typedef there isn't legal either...

Edit 2: Changed auxiliary type name to correspond to article.

The type (from the article)

type Randomised a = StdGen -> (a, StdGen)

allows one to specify the type of bind as

bind :: (a -> Randomised b) -> Randomised a -> Randomised b

In imperative language, people use typdef to avoid such long declaration.

In Haskell, people use Monads to avoid such long declarations. But some people find them hard to understand....

Keep working at it. It'll make sense in the end. :-)

... that type declaration is probably the hardest part of the article, and the paragraph just before it is garbled. It should read something like:

We now must work out how to compose two randomised functions, f and g. The first element of the pair that g returns needs to be passed in as an input to f. But the seed returned from the g also needs to be passed into f. So we can give this signature for bind:

bind :: (a → StdGen → (b,StdGen)) → (StdGen → (a,StdGen)) → (StdGen → (b,StdGen))

Still confused? Okay, let's use the following type declaration, which is mentioned later in the article:

type Randomised a = StdGen → (a, StdGen)

This says that we can only know the true value [a] of a random value [Randomised a] after we have passed in the seed [StdGen]. When we pass in the seed [StdGen →], we get out a pair consisting of the true value and the next random seed [(a, StdGen)].

Now, recall that f is a function taking a deterministic input, of type a, and returning a non-deterministic output, of type Randomised b:

f :: a → Randomised b

Similarly, g takes input of some as-yet-unspecified type (call it c) and returns a non-deterministic a:

g :: c -> Randomised a

bind allows us to compose f and g. It does this by converting f into a function that accepts a non-deterministic input:

bind f :: Randomised a -> Randomised b

or in other words:

bind :: (a -> Randomised b) -> (Randomised a -> Randomised b)

Composing bind f with g gives:

bind f . g :: c -> Randomised b

Does that help?

Yes, thanks using the type helps a lot.

Now I must try to understand the rest :-)
The first two example were very easy to understand, the third caused me trouble and I've not managed to grasp the end of the article.

As an additionnal question, why do you call the seed 'StdGen'?

Standard prefix: IANACT (I am not a category theorist)

A paper of McBride's, on what he calls "applicative functors", details a weaker set (and so superset) than monads. These applicative functors sequence things, however, they do so in a static manner. Monads allow more than just sequencing; the paper points out that they allow computed values to effect the control flow of the rest of the computation. Along with arrows, there's probably a decent slew of intermediate-powered structures between monads and pure computation.

My way to think about monads is simply to look at them as a way to force execution order in a language without a specified evaluation order of arguments.
...
Monads now simply encapsulate this behavior using HOFs and also encapsulate the chaining of values thru the calls.

Sequencing is one of the foundational features of monads, but on its own doesn't characterize monads properly. After all, CPS also enforces sequencing, and is much simpler. With sequencing alone, you would not be able to "encapsulate the chaining of values thru the calls". That feature relies on the other foundational feature of monads, which is that they wrap values. It is the combination of these two foundational features which supports the full capabilities of monads:

1. Wrapping values in an arbitrary wrapper, specific to each type of monad (performed by 'unit' a.k.a. 'return').
2. Sequencing steps of a computation using an explicit binding/application operator ('bind'), specific to each type of monad.

Most interesting uses of monads depend on both of these features. The fact that monadic values are wrapped allows (among other things) state to be squirreled away "in the monad"; and the fact that 'bind' is invoked between each step of a monadic computation provides a place to perform operations on that squirreled-away state, and to perform any other operations that need to happen at each step.

I totally agree that my description is a bit short, but I think that if you want to explain a concept like Monads to the 'imperative mind' (which most programmers still are) you first have to explain the foundation and motivation of the concept. And thats is: Sequencing (by using calls which have a definite execution order even in a pure functional language) and value-chaining thru those calls.

If you mentions things like 'category theory' and give a strict mathematical definition of the concept, most people simply will 'shut down' immediatly because they aren't used to strict mathematical thinking. Monads are still something which sounds quite 'esoterically' to most 'normal' programmers. Many of them have still difficulties to really grok closures. And don't even mention continuations. Maybe we even need a more 'down to earth' instead of 'Monads' for it.

I admit I had the same problems in the beginning and it took some time for me to get the point. If someone simply had told me the above, I'm sure it would've taken less time.

And after you explained the motivation and the basic principles and those principles are really understood (which seems trivial to many of the people here - but its far from trivial for most programmers out there) - then you can go to the details. And yes, on this level monads are really more then the basic concept - but not much more.

I can only agree: Karsten's sketch gives me a basic idea I can grasp and work on from, while other explanations where like a slippery fish that evaded me as a whole whenever I tried to grasp them.