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

append = (t,e) ->
    res = [x for x in *t]
    tinsert res, 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 = append 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, {}
-- "4 : 5"

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.

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.

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.