NetNews Usenet Archive 1992 #30/NN_1992_30.iso/spool/comp/lang/function/1469

Text File | 1992-12-16 | 4.6 KB | 131 lines

Newsgroups: comp.lang.functional
Path: sparky!uunet!gumby!yale!cs.yale.edu!news
From: [e-mail] (Mark P. Jones)
Subject: Re: for monad lovers only
Message-ID: <[e-mail]>
Keywords: monads Gofer overloading
Sender: [e-mail] (Usenet News)
Nntp-Posting-Host: chickadee.systemsz.cs.yale.edu
Organization: Yale University, Department of Computer Science, New Haven, CT
References: <[e-mail]>
Date: Wed, 16 Dec 1992 15:33:18 GMT
Lines: 117

In article <[e-mail]> [e-mail] (Luc Duponcheel) writes:
|  In his article [e-mail] (Mark Jones) writes something like :
|
|  >Now we're ready for the generalization.  The type constructor
|  >State b is a monad M so that we could actually define a more general
|  >version of row that works for any monad M using:
|  >
|  >    mapl  :: (a -> M b) -> ([a] -> M [b])
|  >    mapl f []     = unitM []
|  >    mapl f (x:xs) = f x         `bindM` \y ->
|  >                    mapl f xs   `bindM` \ys ->
|  >                    unitM (y:ys)
|  >
|
|  Now that the function row has been generalised
|  we might as well go one step further by generalising mapl.

Thanks Luc!  I've worked through your message and I thought you (and
others) might be interested to see how it looks in the notation I'm
using.

First of all, Luc gives three equivalent conditions for being able
to compose two monads to form another.  More precisely, Luc gives three
operators and states that, if you can find a definition for one of these
satisfying certain laws, then you can compose the monads (and give
definitions for the other two operators).

With this in mind, we introduce a two parameter class of composable
monads:

    class (Monad m, Monad l) => Composable m l where
        prod  :: l (m (l a)) -> m (l a)
        swap  :: l (m a) -> m (l a)
        app   :: (l a -> m b) -> l (m a) -> m b

        prod   = app (return . join)
        swap   = prod . map (map return)
        app f  = join . map f . swap

In order to specify an instance of this class, we only need to specify
a value for one of the three functions prod, swap and app.  The default
definitions at the end of the class declaration can be used to generate
the other two.  (Of course, it would be a mistake to omit definitions
for all three since the definitions are obviously circular).  For
example, we can express the fact that any monad is composable with the
list monad by writing:

    instance Composable m [ ] where
        swap []     = [ [] ]
        swap (x:xs) = [ y:ys | y<-x, ys<-swap xs ]

(In the context of a type expression, the notation [ ] represents the
list constructor.  I didn't want to make another reserved word, although
things might be prettier to if we wrote it as List.)

Now Luc's generalization of my generalization can be defined by:

    mmap f = swap . map f

This is equivalent to Luc's original definition (from subsequent mail,
I think both Luc and I discovered this simpler form after he had sent
his message).  You'll notice that I've left of the type of mmap; this
is so that I can show you that type inference really does give the
type we want:

    ? :t mmap
    mmap :: Composable b d => (a -> b c) -> d a -> b (d c)
    ?

Ok, so we might have used names like l and m instead of b and d,
but other than that, this is the type that you would expect.

|  it would be nice to be able to write something like
|
|      ( Monad M, Monad L) => Monad (M . L) where
|          prod :: (L . M . L) a -> (M . L) a
|
|          map = map . map
|          unit = unit . unit
|          join = join . map prod

Here's the closest that I can get to this at the moment.  I'm not
sure how useful this would be for practical programming though.
Perhaps somebody else can comment on that.

First, the definition of the composition of two type constructors:

    type Comp f g a = f (g a) in mapComp, returnComp, joinComp

This uses a restricted type synonym; the expansion of Comp f g a
is only permitted in the binding groups of the functions mapComp,
returnComp and joinComp to be defined below.

Let's start with the fact that Comp f g is a functor:

    mapComp :: (Functor f,Functor g) => (a->b) -> (Comp f g a->Comp f g b)
    mapComp  = map . map

    instance (Functor f, Functor g) => Functor (Comp f g) where
        map = mapComp

Now we can move on to describe the monad structure of the composition:

    returnComp :: (Monad f, Monad g) => a -> Comp f g a
    returnComp  = return . return

    joinComp   :: (Composable f g) => Comp f g (Comp f g a) -> Comp f g a
    joinComp    = join . map prod

    instance Composable f g => Monad (Comp f g) where
        return = returnComp
        join   = joinComp

How does that look?

All the best,
Mark