| 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: |
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.