# Monads in Joy

## Manfred Von Thun — 2005-11-21 05:37:46

    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