monad.el

(WIP) Toy implementation of monads in Emacs Lisp.

Just for fun! Don’t take this seriously!

Note: The lexical binding must be enabled to make this work

Do Notation

(monad-do type
     &rest body)

Currently, the type can be one of

• Maybe
• List
• Reader
• Writer
• State

The body contains a list of sexps in the form of (var monad) except for the last expression. If you don’t want to bind anything, use (_ monad) or just (monad). Since do notation doesn’t allow you to bind any variable in the last expression, so the last expression is only monad, not (monad). Whthin the body, return is also allowed. If the monad belongs to MonadPlus, you can also use guard within the body. Currently, guard can only be used for Maybe and List monads.

Some of the following code are based on examples of http://learnyouahaskell.com/.

Maybe Monad

To create a Maybe monad, use Just or Nothing:

(Just 4) ; => (Just . 4)
Nothing ; => Nothing

To see if something is a Maybe monad:

(Maybep (Just 4)) ; => t

To get the value from Just:

(Maybe-get (Just "foo")) ; => "foo"

Use do notation:

(monad-do Maybe
  (x (Just 4))
  (y (if (= x 4)
         (return 5)
       Nothing))
  (return (+ x y)))
;; => (Just . 9)

Use guard within do notation:

(monad-do Maybe
  (x (Just 4))
  (y (Just 5))
  ((guard (> x y)))
  (return (+ x y)))
;; => Nothing

How can this be useful in real world scenarios? For example, in org2elcomment, we need to search inside an Emacs Lisp source code file to find the two lines: ;;; Commentary: and ;;; Code:, and insert the comment between these two lines. If one of the searches fails, the whole process fails. Here is how to use Maybe monad in this scenario:

(monad-do Maybe
  (beg (Maybe<-
        (save-excursion
          (goto-char (point-min))
          (re-search-forward ";;; Commentary:$" nil t))))
  (end (Maybe<-
        (save-excursion
          (goto-char (point-min))
          (re-search-forward ";;; Code:$" nil t))))
  (return (cons beg end)))

The code is much simpler and clearer than the code using nested if since we only need to consider the successful path. Maybe<- is a simple macro to convert the return value of its last argument into a Maybe value: nil to Nothing and anything else is Just something:

(Maybe<-
  (+ 1 2)
  (eq 'too 'naive)) ; => Nothing
(Maybe<-
  (eq 'too 'simple)
  (* 2 3)) ; => (Just . 6)

List Monad

To create a List monad, use List:

(List 2 3) ; => (2 3)

List is actually an alias for list.

Use do notation:

(monad-do List
  (x (List 2 3 4))
  (y (List 5 6 7))
  (return (cons x y)))
;; => ((2 . 5) (2 . 6) (2 . 7) (3 . 5) (3 . 6) (3 . 7) (4 . 5) (4 . 6) (4 . 7))

To make it more readable, let’s define a list comprehension macro called List-for:

(defmacro List-for (bindings &rest body)
  (declare (indent 1))
  `(monad-do List
     ,@bindings
     (return (progn ,@body))))

Now we can write the code in a more beautiful way:

(List-for
    ((x (List 2 3))
     (y (List 5 6)))
  (let ((z (+ x y)))
    (format "%s + %s = %s" x y z)))
;; => ("2 + 5 = 7" "2 + 6 = 8" "3 + 5 = 8" "3 + 6 = 9")

The above code looks a lot like the for expression in Scala. In fact, in Scala for expressions are translated using flatMap (not precisely, the last binding expression uses map instead of flatMap), which is the Scala’s name for bind in List monads.

You can also use guard for List monads:

(List-for
    ((x (List 2 3))
     (y (List 5 6))
     ((guard (> (* x y) 12))))
  (let ((z (+ x y)))
    (format "%s + %s = %s" x y z)))
;; => ("3 + 5 = 8" "3 + 6 = 9")

Wow! We can have List Comprehensions in Emacs Lisp now! Cool :-)

Reader Monad

To create a Reader monad:

(Reader '+ 1) ; => (closure (t) (&rest args) (apply '* '1 args))

To run a Reader monad:

(Reader-run (Reader '+ 1) 1) ; => 2

Reader is just an alias for apply-partially, and Reader-run is an alias for funcall. In Emacs Lisp, partial application of a function is not as elegant as in Haskell. :-(

Use do notation:

(Reader-run
 (monad-do Reader
   (x (Reader '* 2))
   (y (Reader '+ 10))
   (return (+ x y)))
 3)
;; => 19

Writer Monad

To create a writer monad:

(Writer 888 "Lucky") ; => (Writer 888 . "Lucky")

To run a Writer monad:

(Writer-run (Writer 888 "Lucky")) ; => (888 . "Lucky")

Use do notation:

(defun log-number (x)
  (Writer x (list (format "Got number: %s" x))))

(monad-do Writer
  (x (log-number 3))
  (y (log-number 5))
  (return (* x y)))
;; => (Writer 15 "Got number: 3" "Got number: 5")

Right now the monoid type inside the Writer can only be

• string
• list
• Integer (viewed as Sum, not Product)
• Maybe

cons will be used for everything else.

More types can be supported by simply adding more branches to Monoid-append in the source code.

Monoid examples:

(Monoid-append "too" " young") ; => "too young"
(Monoid-append '(5 2) '(0)) ; => (5 2 0)
(Monoid-append 124 126) ; => 250
(Monoid-append (Just "The quick ") (Just "brown fox")) ; => (Just . "The quick brown fox")

State Monad

To create a State monad:

(State (lambda (x) (cons 0 (1+ x)))) ; => (State lambda (x) (cons 0 (1+ x)))

To run a State monad:

(State-run (State (lambda (x) (cons 0 (1+ x)))) 5) ; => (0 . 6)

Use State-get and State-put to perform get and put:

(State-run (State-get) 1) ; => (1 . 1)
(State-run (State-put 2) 1) ; => (nil . 2)

Use do notation:

(defun stack-pop ()
  (State #'identity))

(defun stack-push (a)
  (State (lambda (s) (cons nil (cons a s)))))

(State-run
 (monad-do State
   (x (State-get))
   (y (stack-pop))
   (z (stack-pop))
   ((if (= (length x) 3)
        (State-put '(200))
      (State-put '(100))))
   ((stack-push y))
   (_ (stack-push z))
   (return x))
 '(8 9 10))
;; => ((8 9 10) 9 8 200)

But wait… We do have mutable states in Emacs Lisp, so what is the benefit of State monads? Well, I’m not sure, but at least it shows that we can pretend we don’t have mutable variables so we have to use State monads to write more Haskell-ish Emacs Lisp code. Anyway, this is just a toy and a proof of concept. Don’t take it too seriously!