Re: [boost] Re: Review Request: FC++

From: Brian McNamara (lorgon_at_[hidden])
Date: 2003-10-21 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 fully-curried) 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 entity--only 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 2-arg 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 partially-applied
(curried) the State type constructor, resulting in a new entity which
has the right-shaped 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
right-associativity 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])