Often in lisp I find I have lists of some arbitrarily complex objects
and I need to sort them in some consistent fashion so that I can more
efficiently perform some set operations, such as set-difference, merge
or somesuch. I have custom-coded versions of these operations that
work specifically against sorted lists, as this can often be done in
linear time. To accomplish this, I have a (hideously ugly) any< binary
predicate that can compare any arbitrary atom/list/tree against any
other and leads to a consistent sorting order. Below is some code that
accomplishes this. Ignore any bugs/limitations. I am wondering if
anyone knows of a cleaner way of performing such arbitrary
comparisons.
Example:
[1]> (sort '((3 foo) (alpha beta gamma) (0 1 1 2) (bar baz) 3.14)
#'any<)
(3.14 (ALPHA BETA GAMMA) (BAR BAZ) (0 1 1 2) (3 FOO))
Source Code: (I swear not all my code is this retarded :)
(defun list-cmp (fn= fn< a b) ;compares two lists lexically
(cond ((and (car a) (car b) (funcall fn= (car a) (car b)))
(cond ((not (cdr a)) t)
((and (atom (cdr a)) (not (atom (cdr b)))) t)
((and (atom (cdr a)) (atom (cdr b))) (funcall fn< (cdr a)
(cdr b)))
((and (atom (cdr b)) (not (atom (car a)))) nil)
((cdr b) (list-cmp fn= fn< (cdr a) (cdr b)))))
((and (car a) (car b)) (funcall fn< (car a) (car b)))
((not (car a)))))
(defun list< (a b) ;compares two lists of any objects lexically
(list-cmp #'equal #'any< a b))
(defun any< (a b) ;compares anything at all with anything else
(labels ((type-num (x)
(cond ((null x) 0)
((symbolp x) 1)
((numberp x) 2)
((consp x) 3))))
(let ((ta (type-num a)) (tb (type-num b)))
(if (= ta tb)
(case ta
(0 nil)
(1 (string< (symbol-name a) (symbol-name b)))
(2 (< a b))
(3 (list< a b)))
(< ta tb)))))
Conrad Barski wrote:
> Often in lisp I find I have lists of some arbitrarily complex objects
> and I need to sort them in some consistent fashion so that I can more
> efficiently perform some set operations, such as set-difference, merge
> or somesuch. ...
I'm afraid there is no such sorting predicate unless you limit the range
of objects you need to sort.
Suppose the Lisp implementation supported some capability similar to
sxhash that assigned to each user-visible object immediately when it
was created a permanent unique numeric identifier. This would solve
your problem, except that the overhead would be unacceptable, because
every object (string, number, cons, symbol) would have to carry around
this identifier forever. (We could avoid the metacircularity surrounding
these numbers by making the numbers themselves inaccessible, providing
only a sort predicate that compares the numberic identifiers of two
objects without revealing the identifiers to the user code.)
Many implementations allocate permanent hashing codes to interesting
objects when they are allocated, e.g. standard-object, symbol and
pathname, so that eq/eql hashtables can perform efficiently on these
objects. But it would be unreasonable to load conses and strings with
this overload. And even if they did, the needs of hashing only requires
that the has codes be distributed, not that they be absolutely unique.
I suspect that your need to "perform ... set operations, such as
set-difference" does not really extend across _all_ lisp objects.
Real applications would likely constrain this need to some single
type, or small set of types. Could you not assign these objects
with some unique numeric identifier, or arrange to encapsulate
any set of objects of interest inside some interning object with a
sorting number?
"Conrad Barski" <·····················@yahoo.com> wrote in message
·································@posting.google.com...
> Often in lisp I find I have lists of some arbitrarily complex objects
> and I need to sort them in some consistent fashion so that I can more
> efficiently perform some set operations, such as set-difference, merge
> or somesuch. I have custom-coded versions of these operations that
> work specifically against sorted lists, as this can often be done in
> linear time. To accomplish this, I have a (hideously ugly) any< binary
> predicate that can compare any arbitrary atom/list/tree against any
> other and leads to a consistent sorting order. Below is some code that
> accomplishes this. Ignore any bugs/limitations. I am wondering if
> anyone knows of a cleaner way of performing such arbitrary
> comparisons.
Here's another approach:
(defmethod lt ((obj1 null) obj2) t)
(defmethod lt (obj1 (obj2 null)) nil)
(defmethod lt ((obj1 symbol) obj2) (lt (symbol-name obj1) obj2))
(defmethod lt (obj1 (obj2 symbol)) (lt obj1 (symbol-name obj2)))
(defmethod lt ((obj1 string) (obj2 number)) t)
(defmethod lt ((obj1 number) (obj2 string)) nil)
(defmethod lt ((obj1 string) (obj2 cons)) t)
(defmethod lt ((obj1 cons) (obj2 string)) nil)
(defmethod lt ((obj1 number) (obj2 cons)) t)
(defmethod lt ((obj1 cons) (obj2 number)) nil)
(defmethod lt ((obj1 string) (obj2 string)) (string< obj1 obj2))
(defmethod lt ((obj1 number) (obj2 number)) (< obj1 obj2))
(defmethod lt ((obj1 cons) (obj2 cons))
(if (equal (car obj1) (car obj2))
(lt (cdr obj1) (cdr obj2))
(lt (car obj1) (car obj2))))
(defmethod gt (obj1 obj2)
(not (lt obj1 obj2)))
I think it's a little more transparent and easier to extend.
--
Coby Beck
(remove #\Space "coby 101 @ big pond . com")