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

From: Brian McNamara (lorgon_at_[hidden])
Date: 2003-10-17 22:06:08

On Fri, Oct 17, 2003 at 04:55:12PM -0400, David Abrahams wrote:
> Brian McNamara <lorgon_at_[hidden]> writes:
> > The documentation is available at
> >    http://www.cc.gatech.edu/~yannis/fc++/boostpaper/
> > in a few different formats.
> 
> Brian, I'm following the documentation links for Monads to
> http://www.cc.gatech.edu/~yannis/fc++/fcpp-lambda.pdf, and reading
> along... I arrive at:
> 
> class Monad m where
>     bind :: m a -> ( a -> m b ) -> m b
>     unit :: a -> m a
> 
> And note that you haven't introduced the syntax 'm a' anywhere.  I
> understand that to be function invocation in other contexts (without
> help from the paper which it should probably give), but I don't
> understand how to read it here.
> 
> Can you help?

Yes.

As you mentioned, you've already figured out that in the "value" domain,
this syntax is used for function application.  That is

   Haskell         C++
   -------  ===  -------         // all of these expressions
     f x          f(x)           // reduce to values
    g x y        g(x,y)

In the "type" domain, this same syntax is used for type-function
application, that is, templates:

   Haskell         C++
   -------  ===  -------         // all of these "expressions"
     f x          f<x>           // reduce to types
    g x y        g<x,y>

For example, in C++, if we have the template "list" (as in "list<int>"),
then "list" is a type function of one argument--you pass it a type (like
"int"), and it returns you a type ("list<int>").  std::map is a
two-argument type function; you pass it a key type and a value type, and
it returns you a class which is specialized for those types (e.g. a
map<string,int>).

So, returning to the concrete example at hand:

   bind :: m a -> ( a -> m b ) -> m b
   unit :: a -> m a

Here 'm' is a "type constructor" (a one-argument function from types to
types), and thus "m a" is a normal datatype.

It might be helpful to think of this

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

as being analogous to

   template <template <class> class M, class A, class B>
   M<B> bind( M<A>, fcpp::fun1< A, M<B> > );

where M is realized as a template-template parameter.   (The actual
FC++ implementation is done in a completely different way; this example
is just for purpose of exposition.)

To make things even more concrete, knowing that the general monad 
signature for unit is

   unit :: a -> m a

consider these actual examples of FC++ code:

   list_m::unit( 3 )       // a value whose type is list<int>
   maybe_m::unit( 3 )      // a value whose type is maybe<int>

Thus, in the list monad (represented by class fcpp::list_m in FC++),
"m==fcpp::list" whereas in the maybe monad (class fcpp::maybe_m),
"m==fcpp::maybe".  

Hope that helps some; I feel like that was awfully long-winded.

-- 
-Brian McNamara (lorgon_at_[hidden])