Re: powerset
- From: Frank Buss <fb@xxxxxxxxxxxxx>
- Date: Sun, 8 Jul 2007 03:54:16 +0200
jim burton wrote:
That's on
the right side of power and expressivity vs. being too abstract, while
this version, being discussed on haskell-cafe I think, makes my head
hurt:
powerset = filterM (const [True, False])
I understood most of the Lisp solutions given in this thread without
problems, maybe because Lisp has the advantage that there is nearly no
syntax and things like operator overloading, you write what you mean and
you can read what you mean, without too much implicit knowledge. In
contrast to this is Haskell, which provides many syntatic sugar for things
like monads, currying etc. To understand this, it can help to translate it
to Lisp again.
I've found an explanation for Haskell programmers at this page:
http://community.livejournal.com/evan_tech/220036.html
First "const [True, False]" is a fancy syntax for "\_ -> [True, False]",
which is "(lambda () (list t nil))" in Lisp. filterM has two arguments: a
function and a monad. The function is applied to the argument to produce a
new monad. The second argument is omitted, which is called currying and
means the same like "powerset m = filterM (const [True, False]) m". To
understand how it works, first a little introduction to monads (this is
inspired by the monad scheme implementation at
http://groups.google.com/group/comp.lang.functional/msg/2fde5545c6657c81 ).
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 *m* (make-instance 'just :wrapped-object 3))
*M*
CL-USER > (bind *m* #'unit)
just: 3
CL-USER > *m*
just: 3
axiom 3:
CL-USER > (bind (bind *m* #'maybe-identity) #'maybe-1/)
just: 1/3
CL-USER > (bind *m* (lambda (x) (bind (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
Now the interesting thing. filterM is implemented in Haskell like this:
filterM :: (Monad m) => (a -> m Bool) -> [a] -> m [a]
filterM _ [] = return []
filterM p (x:xs) = do
flg <- p x
ys <- filterM p xs
return (if flg then x:ys else ys)
The trick is that there are monads defined for lists in Haskell. This can
be implemented in Lisp like this (todo: list-bind should be overloaded,
which should be possible, but the bind-operator, which is simple #'list in
this example, would be difficult) :
(defun concat (list)
(when list (append (car list) (concat (cdr list)))))
(defun list-bind (list fun)
(concat (mapcar fun list)))
(defun filter-monad (predicate list)
(if (null list)
(list ())
(let ((x (first list))
(xs (rest list)))
(list-bind (funcall predicate x)
(lambda (flag)
(list-bind (filter-monad predicate xs)
(lambda (ys)
(list (if flag
(cons x ys)
ys)))))))))
Maybe some macros could help to simplify the syntax, but this is what the
Haskell implementation does. It can be used like this:
CL-USER > (filter-monad (lambda (x) (list t nil)) '(1 2 3))
((1 2 3) (1 2) (1 3) (1) (2 3) (2) (3) NIL)
--
Frank Buss, fb@xxxxxxxxxxxxx
http://www.frank-buss.de, http://www.it4-systems.de
.
- References:
- powerset
- From: Frank Buss
- Re: powerset
- From: jim burton
- Re: powerset
- From: André Thieme
- Re: powerset
- From: jim burton
- powerset
- Prev by Date: Re: powerset
- Next by Date: Re: throwing control within a nested conditional
- Previous by thread: Re: powerset
- Next by thread: Re: powerset
- Index(es):
Relevant Pages
|
