reference: http://www.cs.nott.ac.uk/~gmh/pearl.pdf

parser.coffee

_ = require 'lodash'

item = (cs) ->
    if cs == ""
        return []
    else
        return [[cs[0], cs.slice(1)]]


# Monad Methods
pure = (a) ->
    return (cs) -> [[a, cs]]

bind = (p, f) ->
    return (cs) ->
        accum = for x in (p cs)
                    a  = x[0]
                    ds = x[1]
                    (f a) ds
        return _.flatten accum

p1 = bind(item, (a) -> (bind(item, (b) -> pure [a, b])))

# MonadPlus Methods
mzero = (cs) -> []

combine = (p, q) ->
    return (cs) ->
        _.flatten [(p cs), (q cs)]

satisfy = (f) ->
   bind item, (c)->
       if (f c)
           return pure c
       else
           return mzero

char = (c) -> satisfy (d) -> c == d

string = (cs) ->
    if cs is "" then return pure ""
    else bind (char cs[0]), -> bind (string cs.slice(1)), -> pure cs

oneOf = (cs) -> satisfy (c) -> c in cs

# <|>
choice = (p, q) -> (cs) ->
    tmp = (combine p, q) cs
    if tmp is []
        return []
    else
        return [tmp[0]]

many = (p) -> choice (many1 p), (pure [])
many1 = (p) -> bind p, (a) -> bind (many p), (as) -> pure (_.flatten [a,as])

# 足し算計算機
spaces = many (char " ")

natural = bind (many1 (oneOf "1234567890")), (n) -> bind spaces, -> pure (Number n.join(""))

plus = bind (char "+"), -> bind spaces, -> pure ((x,y) -> x + y)

chainl = (p, op) ->
    rest = (x) -> choice((bind op, (f) -> bind p, (y) -> rest (f x, y)), pure x)
    return bind p, rest

expr = chainl natural, plus

console.log expr "1 + 2 + 3"