Monads in Moonscript

This is a translation of a great article on "Understanding Monads with JavaScript". Although the result is still somewhat verbose compared to Haskell, Moonscript makes the result much easier to read than Lua (or Javascript)

The author starts out with a simple stack example, although naturally this approach applies to any set of operations on data.

First we need some immutable list operations, a la Lisp:

tinsert = table.insert

insert = (t,e) ->
    res = [x for x in *t]
    tinsert res,1,e
    res

tail = (t) ->
    [x for x in *t[2,]]

Obviously not a very efficient thing to do with Lua tables, but this is an exercise in immutability.

The push and pop operations can be written. We want these to be curried, so that push(4) creates a function that actually does do the pushing. These functions must return the state, which here is the value of the operation, and the data being operated on.

push = (element) -> (stack) ->
    value = nil
    newStack = insert stack, element
    {value: value, stack: newStack}

pop = -> (stack) ->
    value = stack[1]
    newStack = tail stack
    {value: value, stack: newStack}

And now for a monad-style operation!

bind = (operation,continuation) -> (stack) ->
    result = operation stack
    continuation(result.value) result.stack

-- this allows the computation to pass back the value as a state
result = (value) -> (stack) ->
    {value:value, stack:stack}

-- finally, do the stack operations with an initial stack
-- and return the actual return value
evalStack = (operation,initial) ->
    operation(initial).value

-- naturally, this is rather more nasty in Lua ;)
computation = bind push(4),->
    bind push(5), ->
        bind pop(), (r1) ->
            bind pop(), (r2) ->
                result r1..' : '..r2

print evalStack computation, {}
-- "5 : 4"

bind is the key function here. You give it an operation on a stack (like push(4)) and a continuation. bind performs the operation, and calls the continuation on the value, giving yet another stack operation.

In this case, we apply the operation push(4) to the stack, and call the continuation (there's no value returned in this operation). That calls bind with push(5), which is applied, and continues, implicitly passing the object along the chain.

This is a little clumsy, but Moonscript offers a solution which is arguably more straightforward than the author's proposed sequence helplper.

sequence = (actions) -> -- actions...,continuation
    continuation = table.remove(actions)
    (stack) ->
        values = {}
        for operation in *actions
            res = operation stack
            tinsert values, res.value if res.value ~= nil
            stack = res.stack
        continuation(unpack(values)) stack


c2 = sequence {
    push(4)
    push(5)
    pop!
    pop!
    (r1,r2) -> result r1..' : '..r2
}

print evalStack c2, {}

I've let continuation take a table, not varargs, because passing a table in Moonscript is less fussy than passing multiline arguments to a function. Also I'm no longer bothering to continue pretending that tables are immutable, since these values don't leak out of sequence anyway.

You can think of sequence as a multi-operation bind, where the continuation now gets passed multiple values. But there is a rather serious weakness: if the operations are genuinely asynchronous, then both this sequence and the original blocks while all the operations are in progress. (Imagine that push was a socket send operation and pop was a socket receive operation.)

A gneralization is possible that factors out the state representation details from our push and pop, using the simplification possible with multiple return values:

wrap = (operation) -> (argument) -> (stack) ->
    value, new_obj = operation stack, argument
    {value:value,stack:new_obj}

push = wrap (value) =>
    return nil, insert @, value

pop = wrap =>
    return @[1], tail @

Use of the fat arrow is convenient and suggestive of wrapping method calls to be continuation-friendly.

Of course, Moonscript has coroutines, which are a much more efficient built-in way to do this continuation style, but it does illustrate an important functional technique.