Manfred Von Thun | 21 Nov 06:37 2005
Picon
Picon

[stack] Monads in Joy


PREAMBLE

For some years now I have been trying to understand monads in category
theory and computing, with an embarrassing lack of any success. But recently
things finally fell into place, and I want to share this with the group -
and when I get around to it I want to write it up fully.

"Monads arose in category theory, and have been used extensively in the
Haskell programming community." True. But it led me and possibly others to
several misconceptions:

"Monads are for lazy languages like Haskell." False. You can have them in
the eager language ML.

"Monads are for strongly but polymorphically typed languagges." False. You
can have monads in Lisp or Scheme (see Oleg's work).

"Monads need lambda abstractions and hence only work for lambda calculus
based languages." False. Any lambda calculus language can be translated into
SK calculus which has no lambda abstractions.

"Monads need a (binary infix) operator 'bindM' which semantically is a
cousin of the apply operator (and syntactically written in reverse, but that
is trivial). So monads can be used in applicative languages such as Haskell,
ML, Lisp/Scheme, SK-calculus." True. "But monads cannot be used in
concatenative languages such as Joy." False. That is what I want to show.

THE LIST MONAD IN JOY

Understanding monads in Joy came as an enlightenment to me when I reread
Wadler's paper "The essence of functional programming" and noticed a very
small section about the list monad in Haskell. Here at last was something I
knew how to translate into Joy, and I think it is probably a good way to
introduce monads to other Joy programmers.

Define two functions:
    unitM   #  unitlist
           ==  [] cons
    joinM   #  form a a single list from a list of lists
           ==  concatenate
           ==  [null] [] [uncons] [concat] linrec
Define two combinators, which both expect a single quotation:
    mapM    #  the ordinary mapping for lists
           ==  map
    bindM   #  a strange beast
           ==  map concatenate

In the following [F] and [G] will be something like [dup *]. Now all the
following laws are satisfied (all expect a list on top of the stack, except
that (4) expects a list of lists, and (7) expects a list of lists of lists):

( 1)   [] mapM  ==  id
( 2)   [F G] mapM  ==  [F] mapM  [G] mapM
( 3)   unitM [F] mapM  ==  [F] i unitM
( 4)   joinM [F] mapM  ==  [[F] map] map joinM
( 5)   unitM joinM  ==  id
( 6)   [unitM] mapM joinM  ==  id
( 7)   [joinM] mapM joinM  ==  joinM joinM

The above do not use bindM yet, but the following do. The parameter [K] or
[H] for bindM has to be a  function K or H which produces a list, something
like [dup * unitM] or [dup dup * [] cons cons]. These laws are also
satisfied:

( 9)  unitM [F] bindM  ==  [F] i
(10)  [unitM] bindM  ==  id
(11)  [F] bindM [G] bindM  ==  [[F] i [G] bindM] bindM
(12)  [F] mapM  ==  [F unitM] bindM
(13)  joinM  ==  [] bindM

A SMALL TASTE OF OTHER MONADS IN JOY

For the definitions of unitM, bindM, mapM and bindM this is the list monad.
For different definitions we get a different monad - provided all laws are
satisfied. But we do not need all four primitives: we can have unitM and
bindM as primitives, and then use (12) and (13) as definitions for mapM and
joinM. Alternatively, we can have unitM, joinM and mapM as primitives and
use (8) as a definition for bindM. The latter alternative is probably most
natural for Joy programmers. Readers familiar with monads in Haskell will
recognise the laws from Wadlers paper(s).

Searching for different definitions yielding a different monad, the best is
probably to start with a different definition for the combinator mapM. It
has to take just one quotation parameter, and there are plenty like that in
Joy. But one also needs appropriate unitM and joinM. Here are several:

The (boring?) identity monad:
   unitM = id, joinM = id, mapM =  I, bindM = I (* both I lower case! *)
                                   ^          ^ (* arrogant mailer!*)
An "additive dip monad":
   unitM = 0, joinM = +, mapM = dip, bindM = dip +
(here the [K] parameter to bindM must leave an extra integer on top of the
stack) 

A "concatenative dip monad":
   unitM = [], joinM = concat, mapM = dip, bindM = dip concat
(Here the [K] parameter to bindM must leave an extra list on top of the
stack.)

The two dip monads propagate a state on top of the stack, and different
choices for unitM and joinM give different dippy monads. Combinators other
than map, I, or dip as interpretations for mapM need investigating, such as
nullary and infra. And even combinations [I]map, [map]map, [dip]map and I
don't know what else.

More in the future. I have a few examples of state monads.

Does anybody know how to switch off the spelling "corrector" (for lower case
I) inside this Entourage abomination?

  - Manfred 

------------------------ Yahoo! Groups Sponsor --------------------~--> 
1.2 million kids a year are victims of human trafficking. Stop slavery.
http://us.click.yahoo.com/WpTY2A/izNLAA/yQLSAA/saFolB/TM
--------------------------------------------------------------------~-> 

 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/concatenative/

<*> To unsubscribe from this group, send an email to:
    concatenative-unsubscribe <at> yahoogroups.com

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/


Gmane