Paste number 44120: monads in Lisp

Paste number 44120: monads in Lisp
Pasted by: Shine
When:3 years, 1 month ago
Share:Tweet this! | http://paste.lisp.org/+Y1K
Channel:#lisp
Paste contents:
Raw Source | XML | Display As
According to http://en.wikipedia.org/wiki/Monads_in_functional_programming a monad has the following components:

1. A type construction
2. A unit function that maps a value in an underlying type to a value in the corresponding monadic type
3. A binding operation, which applies the mapped type to a function and which returns a new monad of the same type

Lets see how the "maybe" monad could look like in Common Lisp:

1. A type construction:

  (defclass maybe () ())

  (defclass just (maybe)
    ((wrapped-object :accessor wrapped-object :initarg :wrapped-object)))

  (defclass nothing (maybe) ())

2. A unit function:

  (defgeneric unit (object)
    (:method ((maybe maybe)) maybe)
    (:method ((simple-object t))
     (make-instance 'just :wrapped-object simple-object)))

3. A binding operation:

  (defgeneric bind (object fun)
    (:method ((object just) fun) (funcall fun (wrapped-object object)))
    (:method ((object nothing) fun) object))

Every monad must obey the following 3 axioms:

axiom 1. "bind" left-identity:

  (bind (unit wrapped-type) fun) == (funcall fun wrapped-type)

axiom 2. "bind" right-identity:

  (bind monad unit) == monad

axiom 3. "bind" associativity:

  (bind (bind monad fun1) fun2) == 
  (bind monad (lambda (x) (bind (funcall fun1 x) fun2)))

A formal proof would be nice for my monad definition, but I'm just an application programmer, so lets try it with an example. First some methods for nicer displaying the results:

  (defmethod print-object ((object just) stream)
    (format stream "just: ~a" (wrapped-object object)))

  (defmethod print-object ((object nothing) stream)
    (declare (ignore object))
    (format stream "nothing"))

For testing the axioms, we need some useful functions, which takes a simple type and returns a monad:

  (defun maybe-identity (wrapped-object)
    (make-instance 'just :wrapped-object wrapped-object))

  (defun maybe-1/ (wrapped-object)
    (make-instance 'just :wrapped-object (/ wrapped-object)))

Now testing the axioms:

axiom 1:

  CL-USER > (defparameter *foo* 42)
  *FOO*

  CL-USER > (bind (unit *foo*) #'maybe-identity)
  just: 42

  CL-USER > (maybe-identity *foo*)
  just: 42

axiom 2:

  CL-USER > (defparameter *monad* (make-instance 'just :wrapped-object 3))
  *MONAD*

  CL-USER > (bind *monad* #'unit)
  just: 3

  CL-USER > *monad*
  just: 3

axiom 3:

  CL-USER > (bind (bind *monad* #'maybe-identity) #'maybe-1/)
  just: 1/3

  CL-USER > (bind *monad* (lambda (x)
                           (bind (funcall #'maybe-identity x) #'maybe-1/)))
  just: 1/3

Ok, now that we have proved that the maybe-monad is a monad, we can do something useful with it:

  (defmethod safe-/ ((x maybe) (y maybe))
    (bind x (lambda (a)
              (bind y (lambda (b)
                        (if (zerop b)
                            (make-instance 'nothing)
                          (make-instance 'just
                                         :wrapped-object (/ a b))))))))

  CL-USER > (defparameter *a* (make-instance 'just :wrapped-object 3))
  *A*

  CL-USER > (defparameter *b* (make-instance 'just :wrapped-object 2))
  *B*

  CL-USER > (defparameter *c* (make-instance 'just :wrapped-object 0))
  *C*

  CL-USER > (safe-/ *a* *b*)
  just: 3/2

  CL-USER > (safe-/ *a* *c*)
  nothing

You can nest this, too. If one object is "nothing", the whole result is nothing. The order doesn't matter:

  CL-USER > (safe-/ (safe-/ *a* *c*) *b*)
  nothing

This paste has no annotations.

Colorize as:
Show Line Numbers

Lisppaste pastes can be made by anyone at any time. Imagine a fearsomely comprehensive disclaimer of liability. Now fear, comprehensively.