Boost logo

Boost :

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])

Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk