
Boost : 
From: Brian McNamara (lorgon_at_[hidden])
Date: 20031021 00:15:35
On Mon, Oct 20, 2003 at 10:34:27PM 0400, David Abrahams wrote:
> Let's see if I get this. In Haskell, a unary function invocation is
> spelled
>
> f x
>
> So it stands to reason that a nullary (or fullycurried) function
> invocation is spelled
>
> f
>
> And since Haskell is completely lazy, this makes perfect sense: a
> nullary function is a value and (in most [all?] cases) a value is a
> nullary function.
>
> Therefore,
>
> [1 2 3]
>
> or
>
> List 1 2 3
>
> can be thought of as a computation.
This is a fine way to think about it, if you like. (In fact, none of
the theory of monads relies on laziness in the way you're describing
here, but as far as I can see, it doesn't "hurt" to think about it this
way, either.)
> Brian McNamara <lorgon_at_[hidden]> writes:
> > With the State monad, for example:
> >
> >  (State s) is a monad
> > type State s a = s > (a,s)
> >
> > it makes more intuitive sense. You can think of the state monad as a
> > "computation" which, when passed an initial state (of type "s"),
> > returns a pair of some value (of type "a") along with the (possibly
> > updated) state.
>
> I'm still a little vague on some things. If (State s) is a monad,
> what's (State) ?
Recall that a monad is a "type constructor": a function from a type to
a type. State is the same general kind of entityonly it has _two_
arguments. That is, if we use the C++ template analogy:
template <class A> struct M; // M<A> yields a type
template <class S, class A> struct State; // State<S,A> yields a type
In Haskell, the "type system for types" is called the "kind" system.
Monads (type constructors) have this kind:
m :: * > *
 "*" represents a type; m takes a type and returns a type
As you can see
State :: * > * > *  State's kind is a 2arg type constructor
Thus,
State Int :: * > *  instead of Int, any type "s" could be used
which is why "(State s)" could be a monad; we have partiallyapplied
(curried) the State type constructor, resulting in a new entity which
has the rightshaped kind to be a monad.
Don't sweat this next stuff, which will either be enlightening, or just
a distraction that will make your head hurt.
begin
When you get into "monad transformers", which allows monads to be
composed, you'll create types like
type StateT s m a = s > m (a,s)
where the kind of StateT is
StateT :: * > (* > *) > * > *
or, in C++speak
template <class S, template <class> class M, class A> struct StateT;
As you can imagine,
StateT Int Maybe :: * > *  one particular example
is a monad, and more generally we'd define the right methods so that
for all types "s"
for all type constructors "m" where m is an instance of class Monad
"StateT s m" is also an instance of class Monad
Note that "StateT s" is a monad transformer. Monad transformers are
entities with this kind:
SomeMonadTransformer :: (* > *) > (* > *)
That is, you can pass a monad to a monad transformer, and it returns you
a new monad.
end
> >> > the results. This is why bind() has the signature it does. A typical
> >> > string of operations in a monad looks like this:
> >> > comp1 `bind` \a >  run comp1, store result in 'a'
> >> > comp2 `bind` \b >  run comp2, store result in 'b'
> >> > comp3 `bind` \c >  run comp3, store result in 'c'
> >> > unit (f a b c)  compute some function of a, b, and c
> >> > That whole expression has type "m r".
> >>
> >> I think that little word "in" is crucial here.
>
> Looking again at what you wrote above, I see that it's a function
> signature... or maybe I need another lesson in Haskell syntax. Isn't
> that what ">" is all about?
Yes; the code
\x > yadda yadda x yadda
means
lambda(X)[ yadda yadda X yadda ]
Note that lambdas "extend to the right as far as possible" in Haskell,
so that code parses as
comp1 `bind` (\a >
comp2 `bind` (\b >
comp3 `bind` (\c >
unit (f a b c) ) ) )
Now you can see that the first call to bind() takes comp1 as its left
argument, and _the entire rest of the computation_ as its right
argument. (In fact, bind() is associative; the explicit
rightassociativity in the example just stems from the use of lambda as
a convenient way to scope the intermediate names {a, b, c} so that
these names stay "visible" throughout the rest of the computation.)
 Brian McNamara (lorgon_at_[hidden])
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk