Sorting by enumeration
Erik R.
I'm at an AA meeting) Here's the current problem I'm having trouble
with.
I've got two different "enumeration" types that have natural
ordering. They are not just numbers and letters, but for the sake of
this question, they will be. So I have:
(defvar *numbers* '(1 2 3 4 5 6 7))
(defvar *letters* '(a b c d e f))
I also have lists of doubletons (currently represented as cons cells)
with one number and one letter each. Like so:
(setf values '((3 . F) (4 . C) (2 . A) (6 . C) (7 . E)))
I want to be able to 1) sort by number, 2) sort by letter, 3) sort by
both number and letter.
I've got this before function from Paul Graham's "On Lisp" book:
(defun before (a b order &key (test #'eql) (key #'(lambda (a) a)))
"Determines if element A appears before element B in list order"
(and order
(let ((first (first order)))
(cond ((funcall test (funcall key b) first) nil)
((funcall test (funcall key a) first) order)
(t (before a b (rest order) :test test :key key))))))
So it's pretty simple to write the first two:
(defun sort-by-number (values)
(sort values #'(lambda (value1 value2) (before value1 value2
*numbers* :key #'car))))
(defun sort-by-letter (values)
(sort values #'(lambda (value1 value2) (before value1 value2
*letters* :key #'cdr))))
My first question is, does this make sense and is this the right way
to do it?
As for sorting on both number and letter, my mind is drawing a blank.
In java, comparators return -1, 0, or 1 when the first value is less
than, equal, or greater than the second value. Therefore, I would
sort on the first field, number, and only if they were equal would I
sort on the second field, letter. But since Lisp only has "less than"
or "not less than" comparator return values, it seems like I'm going
to have to do some equals testing as well.
Also, it seems entirely likely that a macro could be written to take
any number of comparators and try them in order, only falling through
to the next one if the values were equal, but my entirely novice lisp
skills aren't anywhere near that level yet.
Any help from your black belt lispers?
Cheers,
Erik
Slobodan Blazeski
looks like that it works, sorry no time to clear it & test it more
thoroughly.
(defun be4 (a b)
(cond ((< (position (car a) *numbers*)
(position (car b) *numbers*))
t)
((> (position (car a) *numbers*)
(position (car b) *numbers*))
nil)
(t
(if (< (position (cdr a) *letters*)
(position (cdr b) *letters*))
t))))
(defun number-and-letter (values)
(sort values #'be4))
(number-and-letter '((3 . F) (3 . A) (4 . C) (4 . B) (2 . A) (6 . C)
(7 . E)))
=>((2 . A) (3 . A) (3 . F) (4 . B) (4 . C) (6 . C) (7 . E))
cheers
bobi
Erik R.
wrote:
Yes, I know how to do it with position. That's easy. The recursive
way the my (PG's) before function does it is more efficient because it
only has to find the one of the elements in the list to know which
comes first. I was hoping that there was an elegant way to do it
without also having to iterate through the list more than the
once....and then to further extend it for n comparators.
Tamas Papp
I am not a black belt lisper, but here is how I would do it. Looking
positions up in a list is a bit slow, so I would put things in a hash
table. You said your objects were more general, make sure that you
specify the appropriate test to the hash table, the default eql works
here.
The following code generates ordering functions with closures:
(defvar *numbers* '(1 2 3 4 5 6 7))
(defvar *letters* '(a b c d e f))
(defparameter *values* '((3 . F) (4 . C) (2 . A) (6 . C) (7 . E)))
(defun make-position-function (list)
;; build a hash table from item-position pairs
(let ((hash-table (make-hash-table)))
(do ((list list (cdr list))
(position 0 (1+ position)))
((not list))
(setf (gethash (car list) hash-table) position))
;; return the function
(lambda (item)
(multiple-value-bind (position foundp) (gethash item hash-table)
(unless foundp
(error "Item ~a is not in the hash table." item))
position))))
(defun make-comparison-function (position-function)
(lambda (a b)
(< (funcall position-function a) (funcall position-function b))))
(defparameter *number<* (make-comparison-function
(make-position-function *numbers*)))
(defparameter *letter<* (make-comparison-function
(make-position-function *letters*)))
;; since sort is desctructive, redefine *values* before each run below
;; sort by numbers
(sort *values* #'(lambda (a b)
(funcall *number<* (car a) (car b))))
;; sort by letters
(sort *values* #'(lambda (a b)
(funcall *letter<* (cdr a) (cdr b))))
;; lexicographic ordering
(sort *values* #'(lambda (a b)
(or (funcall *number<* (car a) (car b))
(and (eql (car a) (car b))
(funcall *letter<* (cdr a) (cdr b))))))
Yes, you need to test for equality somehow to get a lexicographic
ordering. You can prettify the code above, eg is two numbers/letters
are equal, you don't need to look them up in the hash table to get
their ordering.
HTH,
Tamas
Erik R.
Are two hash-table lookups really faster than iterating through a list
of a dozen values once? What about for an enum of only four
elements? I'm curious at what size of enumeration do the two table
lookups become faster.
I like your solution a lot, btw. Thanks for taking the time.
-Erik
Tamas Papp
> Are two hash-table lookups really faster than iterating through a list
> of a dozen values once? What about for an enum of only four
> elements? I'm curious at what size of enumeration do the two table
> lookups become faster.
I don't know. I would suggest that you time them, the way to do that
in Lisp is
(time ...)
Make sure that you turn of CPU frequency scaling. I would be
interested in the result. BTW, I thought you had more values, not
just a dozen, that's why I suggested hash tables.
> I like your solution a lot, btw. Thanks for taking the time.
Glad that I could help,
Tamas
Zach Beane
[snip]
> I also have lists of doubletons (currently represented as cons cells)
> with one number and one letter each. Like so:
>
> (setf values '((3 . F) (4 . C) (2 . A) (6 . C) (7 . E)))
>
> I want to be able to 1) sort by number, 2) sort by letter, 3) sort by
> both number and letter.
[snip]
> As for sorting on both number and letter, my mind is drawing a
> blank.
I was drawing a blank, too, until I read this section of the SORT
page:
The predicate is assumed to consider two elements x and y to be
equal if (funcall predicate x y) and (funcall predicate y x) are
both false.
(BTW, this is one of the reasons I think it's valuable to learn how to
parse the hyperspec, instead of using a "lite" reference like the one
in ANSI Common Lisp.)
With that hint, I came up with this:
(defparameter *conses*
'((8 . 5) (9 . 5) (1 . 9) (1 . 3) (2 . 51) (8 . 11) (5 . 3)))
(defun sort-fun (test key)
(lambda (a b)
(funcall test (funcall key a) (funcall key b))))
(defun cascaded-predicate (&rest funs)
(lambda (a b)
(dolist (fun funs nil)
(cond ((funcall fun a b)
;; A is certainly less than B; return true
(return t))
((not (funcall fun b a))
;; A is not less than B, and vice-versa: keep going
)
(t
;; A is certainly not less than B: return nil
(return nil))))))
(defun cascade-sort (sequence &rest tests-and-keys)
(let ((funs (loop for (test key) on tests-and-keys by #'cddr
collect (sort-fun test key))))
(let ((predicate (apply #'cascaded-predicate funs)))
(sort sequence predicate))))
#|
(cascade-sort (copy-tree *conses*) #'< #'car)
((1 . 9) (1 . 3) (2 . 51) (5 . 3) (8 . 5) (8 . 11) (9 . 5))
(cascade-sort (copy-tree *conses*) #'< #'car #'< #'cdr) =>
((1 . 3) (1 . 9) (2 . 51) (5 . 3) (8 . 5) (8 . 11) (9 . 5))
(cascade-sort (copy-tree *conses*) #'< #'car #'> #'cdr) =>
((1 . 9) (1 . 3) (2 . 51) (5 . 3) (8 . 11) (8 . 5) (9 . 5))
(cascade-sort (copy-tree *conses*) #'> #'car #'> #'cdr) =>
((9 . 5) (8 . 11) (8 . 5) (5 . 3) (2 . 51) (1 . 9) (1 . 3))
(cascade-sort (copy-tree *conses*) #'> #'car #'< #'cdr) =>
((9 . 5) (8 . 5) (8 . 11) (5 . 3) (2 . 51) (1 . 3) (1 . 9))
(cascade-sort (copy-tree *conses*) #'< #'cdr #'< #'car) =>
((1 . 3) (5 . 3) (8 . 5) (9 . 5) (1 . 9) (8 . 11) (2 . 51))
(cascade-sort (copy-tree *conses*) #'< #'cdr #'> #'car) =>
((5 . 3) (1 . 3) (9 . 5) (8 . 5) (1 . 9) (8 . 11) (2 . 51))
|#
Tweaking this to work with your original example should, I hope, be
pretty trivial.
Zach
Frode Vatvedt Fjeld
> I've got two different "enumeration" types that have natural
> ordering. They are not just numbers and letters, but for the sake
> of this question, they will be. So I have:
>
> (defvar *numbers* '(1 2 3 4 5 6 7))
> (defvar *letters* '(a b c d e f))
It seems to me that you contradict yourself here, somehow: if your
types have natural ordering, why do you have these lists whose only
purpose seems to be to provide ordering? (Although these particular
lists in effect duplicate "<" and "string<".)
> I also have lists of doubletons (currently represented as cons
> cells) with one number and one letter each. Like so:
>
> (setf values '((3 . F) (4 . C) (2 . A) (6 . C) (7 . E)))
>
> I want to be able to 1) sort by number, 2) sort by letter, 3) sort by
> both number and letter.
>
> I've got this before function from Paul Graham's "On Lisp" book:
>
> (defun before (a b order &key (test #'eql) (key #'(lambda (a) a)))
> "Determines if element A appears before element B in list order"
> (and order
> (let ((first (first order)))
> (cond ((funcall test (funcall key b) first) nil)
> ((funcall test (funcall key a) first) order)
> (t (before a b (rest order) :test test :key key))))))
A few things about this "before":
- The function (lambda (a) a) is better referred to by its name,
which is "identity".
- For sequence operators that take key arguments, the key is usually
only applied to the elements of the sequence(s) (i.e. not to a and
b here).
- Also, that key is even applied to a and b once for each element in
the list, which is wasteful.
- Personally, I find such use of recursion distasteful. I'd do this:
(defun before (a b order &key (test #'eql) (key #'identity))
(loop for x in order as keyed-x = (funcall key x)
when (funcall test a keyed-x)
return t
when (funcall test b keyed-x)
return nil))
> As for sorting on both number and letter, my mind is drawing a
> blank. In java, comparators return -1, 0, or 1 when the first value
> is less than, equal, or greater than the second value. Therefore, I
> would sort on the first field, number, and only if they were equal
> would I sort on the second field, letter. But since Lisp only has
> "less than" or "not less than" comparator return values, it seems
> like I'm going to have to do some equals testing as well.
It's not entirely unreasonable sometimes to define "equal" in terms of
an ordering predicate like this:
(defun equal-by-ordering (orderer x y)
(and (not (funcall orderer x y))
(not (funcall orderer y x))))
I'm not saying you'd necessarily use this exact function, more likely
you'd write your overall ordering predicate something like this:
(lambda (x y)
(cond
((< (car x) (car y))
t)
((< (car y) (car x))
nil)
((string< (cdr x) (cdr y))
t)
((string< (cdr y) (cdr x))
nil)
..etc.))
--
Frode Vatvedt Fjeld
Erik R.
> "Erik R." <rasmussene...@gmail.com> writes:
> > I've got two different "enumeration" types that have natural
> > ordering. They are not just numbers and letters, but for the sake
> > of this question, they will be. So I have:
>
> > (defvar *numbers* '(1 2 3 4 5 6 7))
> > (defvar *letters* '(a b c d e f))
>
> It seems to me that you contradict yourself here, somehow: if your
> types have natural ordering, why do you have these lists whose only
> purpose seems to be to provide ordering? (Although these particular
> lists in effect duplicate "<" and "string<".)
Because they aren't really letters and numbers in my program. They
are other ordered atoms that have an order because of their English
definitions, like '(HOT WARM COOL COLD), or debug levels '(ERROR
WARNING INFO DEBUG).
> > I also have lists of doubletons (currently represented as cons
> > cells) with one number and one letter each. Like so:
>
> > (setf values '((3 . F) (4 . C) (2 . A) (6 . C) (7 . E)))
>
> > I want to be able to 1) sort by number, 2) sort by letter, 3) sort by
> > both number and letter.
>
> > I've got this before function from Paul Graham's "On Lisp" book:
>
> > (defun before (a b order &key (test #'eql) (key #'(lambda (a) a)))
> > "Determines if element A appears before element B in list order"
> > (and order
> > (let ((first (first order)))
> > (cond ((funcall test (funcall key b) first) nil)
> > ((funcall test (funcall key a) first) order)
> > (t (before a b (rest order) :test test :key key))))))
>
> A few things about this "before":
>
> - The function (lambda (a) a) is better referred to by its name,
> which is "identity".
I figured that must exist. I just didn't know the name. Thanks.
-Erik
Alan Crowe
My instinct with this kind of code is to try and write banal
code. I know that if I do I will thank myself in six months
time when I come to read it.
I think the banal version looks like this:
CL-USER> (defun letter< (x y)
(check-type x character)
(check-type y character)
(char< x y))
LETTER<
CL-USER> (defun number< (x y)
(check-type x number)
(check-type y number)
(< x y))
NUMBER<
CL-USER> (defun numeric-part< (x y)
(check-type x cons)
(check-type y cons)
(number< (car x) (car y)))
NUMERIC-PART<
CL-USER> (defun alphabetic-part< (x y)
(declare (cons x y))
(letter< (cdr x) (cdr y)))
ALPHABETIC-PART<
CL-USER> (defun 2part< (x y)
(cond ((numeric-part< x y) t) ;numeric part is decisive
((numeric-part< y x) nil) ;decisive both ways
(t (alphabetic-part< x y))))
2PART<
CL-USER> (dolist (order (list #'numeric-part<
#'alphabetic-part<
#'2part<))
(print (sort (copy-list '((3 . #\F)
(4 . #\C)
(2 . #\A)
(6 . #\C)
(4 . #\D)
(4 . #\B)
(7 . #\E)))
order)))
((2 . #\A) (3 . #\F) (4 . #\C) (4 . #\D) (4 . #\B) (6 . #\C) (7 . #\E))
((2 . #\A) (4 . #\B) (4 . #\C) (6 . #\C) (4 . #\D) (7 . #\E) (3 . #\F))
((2 . #\A) (3 . #\F) (4 . #\B) (4 . #\C) (4 . #\D) (6 . #\C) (7 . #\E))
Then your code has lines such as
(sort (build a list sorry about the jumble) #'2part<)
(sort (make way wrong round) #'numeric-part<)
(sort (dluib a tsli) #'alphabetic-part<)
The CHECK-TYPE is handy as a kind of documentation that is
always right. DECLARE is more usual, because most
implementations let you turn checking on and off as a matter
of compilation policy. Use your judgement to get these bells
and whistles working for you, not against you.
Alan Crowe
Edinburgh
Scotland
Erik R.
Yes, I realized after the fact that I didn't mention the size of the
enums.
Okay, I think I have my solution. Here it is...
Using Tamas' make-comparison-function, renamed slightly, and renaming
my enum values to avoid confusion with the natural order of numbers
and letters, I have this:
(defparameter *temps* '(hot warm normal cool cold))
(defparameter *sizes* '(tiny small medium large huge))
(defparameter *temp<* (make-enum-comparison-function (make-enum-
position-function *temps*)))
(defparameter *size<* (make-enum-comparison-function (make-enum-
position-function *sizes*)))
(defparameter *values* '((hot . medium) (cool . small) (cold . tiny)
(normal . huge) (cold . large)))
And these sort fine with:
CL-USER> (sort (copy-tree *values*) *temp<* :key #'car)
((HOT . MEDIUM) (NORMAL . HUGE) (COOL . SMALL) (COLD . TINY) (COLD .
LARGE))
CL-USER> (sort (copy-tree *values*) *size<* :key #'cdr)
((COLD . TINY) (COOL . SMALL) (HOT . MEDIUM) (COLD . LARGE) (NORMAL .
HUGE))
But then I've also written the nice abstraction that my senses told me
could be written that will take any number of comparison-function and
key-function pairs and make a function that will cascade through them,
similar to what Zach was saying. Behold:
(defmacro make-multiple-key-comparison-function (&rest comparator-key-
pairs)
(labels ((rec (a b pairs)
(if (null pairs)
nil
(let* ((pair (first pairs))
(comparator (first pair))
(key (second pair)))
`(let ((key-a (funcall ,key ,a))
(key-b (funcall ,key ,b)))
(cond ((funcall ,comparator key-a key-b) t)
((funcall ,comparator key-b key-a)
nil)
(t ,(rec a b (rest pairs)))))))))
(let ((a (gensym))
(b (gensym)))
`(lambda (,a ,b)
,(rec a b comparator-key-pairs)))))
And this macroexpands rather beautifully like so:
CL-USER> (macroexpand '(make-multiple-key-comparison-function
(#'*size<* #'cdr) (#'*temp<* #'car)))
#'(LAMBDA (#:G1995 #:G1996)
(LET ((KEY-A (FUNCALL #'CDR #:G1995)) (KEY-B (FUNCALL #'CDR
#:G1996)))
(COND ((FUNCALL #'*SIZE<* KEY-A KEY-B) T)
((FUNCALL #'*SIZE<* KEY-B KEY-A) NIL)
(T
(LET ((KEY-A (FUNCALL #'CAR #:G1995))
(KEY-B (FUNCALL #'CAR #:G1996)))
(COND ((FUNCALL #'*TEMP<* KEY-A KEY-B) T)
((FUNCALL #'*TEMP<* KEY-B KEY-A) NIL) (T
NIL)))))))
So now I just define my composite comparison functions like so:
(defparameter *temp-and-size<*
(make-multiple-key-comparison-function (*temp<* #'car) (*size<*
#'cdr)))
(defparameter *size-and-temp<*
(make-multiple-key-comparison-function (*size<* #'cdr) (*temp<*
#'car)))
And voila, it sorts by one and then the other, and supports an
infinite number of comparator/key pairs.
CL-USER> (sort (copy-tree *values*) *size-and-temp<*)
((NORMAL . SMALL) (COLD . SMALL) (HOT . MEDIUM) (COLD . LARGE) (COOL .
HUGE))
CL-USER> (sort (copy-tree *values*) *temp-and-size<*)
((HOT . MEDIUM) (NORMAL . SMALL) (COOL . HUGE) (COLD . SMALL) (COLD .
LARGE))
Thanks for all your help, guys. I finally got to where I wanted.
Cheers,
Erik
P.S. If I ever get motivated enough, I might do that performance
testing that Tamas suggested, but I'm happy with the hash tables for
now.
Zach Beane
> But then I've also written the nice abstraction that my senses told me
> could be written that will take any number of comparison-function and
> key-function pairs and make a function that will cascade through them,
> similar to what Zach was saying. Behold:
>
> (defmacro make-multiple-key-comparison-function (&rest comparator-key-
> pairs)
No reason to make it a macro, though.
Zach
Erik R.
I couldn't figure out how as a function, since my recursive call would
have to create a new function, which seemed wasteful. But then I'm
coming from a Java background where construction of objects is
wasteful. Maybe making new functions at runtime is not?
Erik
Geoff Wozniak
> Are two hash-table lookups really faster than iterating through a list
> of a dozen values once? What about for an enum of only four
> elements? I'm curious at what size of enumeration do the two table
> lookups become faster.
>
I've run tests on this and found it varies wildly. My notes tell me
the following.
These values were obtained on a 2.16GHz Intel Core Duo (17" MacBook
Pro). In each case, a table (alist or hash) was made and the values
were looked up N times each, accumulating the results. Each lookup
operation was done M times in order to prevent potential zero values,
where M is some sufficently large number. In the following cases, N
is 100 and M is 10000. The times given are the mean value over all
the lookup operations.
This was done with compiled functions using the default compiler
settings. Hash table lookup times were essentially constant across
all runs (which is to be expected, for the most part).
Allegro CL 8.1 (Express): The cut-off seems to be an alist of 5
elements. Hash tables take about 8.0e-6 seconds to do a lookup.
Alists of size 5 take about the same (7.99999e-6 seconds). Alists of
size 10 take about 1.42e-5 seconds to find an element.
SBCL 1.0.8.27: Cut-off is around 29 elements. A hash table lookup
takes about 1.79e-5 seconds. An alist with 10 elements averages
around 8.39e-6 seconds for any lookup.
CLisp 2.40: Hash tables seem to beat lists of just one element (!). A
hash lookup takes around 2.09e-5 seconds. An alist of one element
comes out with a time of 2.19e-5 seconds.
LispWorks 5.0.1 Personal: Hash tables seem to tie alists with one
element. Hash lookups are around 4.0e-7 seconds, which about the same
for a one element alist.
Roughly speaking, hash tables seem to be faster, even for small sets
of associations.
Madhu
| I've got two different "enumeration" types that have natural
| ordering. They are not just numbers and letters, but for the sake of
| this question, they will be. So I have:
[...]
| As for sorting on both number and letter, my mind is drawing a blank.
| In java, comparators return -1, 0, or 1 when the first value is less
| than, equal, or greater than the second value. Therefore, I would
| sort on the first field, number, and only if they were equal would I
| sort on the second field, letter. But since Lisp only has "less than"
| or "not less than" comparator return values, it seems like I'm going
| to have to do some equals testing as well.
|
| Also, it seems entirely likely that a macro could be written to take
| any number of comparators and try them in order, only falling through
| to the next one if the values were equal, but my entirely novice lisp
| skills aren't anywhere near that level yet.
|
| Any help from your black belt lispers?
Also check out S.E.Harris': make lexicographic comparator
posted in this newsgroup
Message-ID: <q94vevs...@chlorine.gnostech.com>
[Note it cannot be directly applied to your problem without adding some
more functions]
--
Madhu
Zach Beane
Not wasteful at all. The stuff I posted is likely to be extremely
fast, and you also don't have to create functions all the time; you
can save the function away somewhere and re-use it, as long as the
general structure of the sorted stuff remains the same.
Zach
Pascal Bourguignon
It makes sense. I would do it differently.
The first thing is that SORT takes already a KEY argument so you
shouldn't have to have it in BEFORE.
I would write at the very least:
(sort values (make-order *letters*) :key (function doubleton-letter))
with:
(defun make-order (order-list) (lambda (a b) (before a b order-list)))
(defun doubleton-letter (x) (cdr x))
(defun doubleton-number (x) (car x))
>> > As for sorting on both number and letter, my mind is drawing a blank.
>> > In java, comparators return -1, 0, or 1 when the first value is less
>> > than, equal, or greater than the second value. Therefore, I would
>> > sort on the first field, number, and only if they were equal would I
>> > sort on the second field, letter. But since Lisp only has "less than"
>> > or "not less than" comparator return values, it seems like I'm going
>> > to have to do some equals testing as well.
And you cannot write a function that takes two booleans and return -1,
0 or +1?
I guess you'd have to put your mind's gear on the "on" position...
Hint: LET
Let's take it from the start:
>> > I've got two different "enumeration" types that have natural
>> > ordering. They are not just numbers and letters, but for the sake of
>> > this question, they will be. So I have:
Here we have a problem. If they're not just number and letters
(there's no "letter" in Common Lisp, what do you mean by "letter"?),
they could be objects built at run-time. Therefore a solution based
on a macro wouldn't work, since macros work at macroexpansion time,
not at run-time. On the other hand, for run-time stuff, there's
nothing magical, you just write functions, I'll assume you can do it.
So assuming that your ordered objects are known at macroexpansion time
(eg. at compilation time), we'll translate
>> > I've got two different "enumeration" types that have natural
>> > ordering.
as:
(define-enumeration numbers (1 2 3 4 5 6 7))
(define-enumeration letters (a b c d e f))
So you have objects
>> > I want to be able to 1) sort by number, 2) sort by letter, 3) sort by
>> > both number and letter.
for (1) and (2), it's direct:
(sort objects (function numbers-lessp) :key (function doubleton-number))
(sort objects (function letters-lessp) :key (function doubleton-letter))
assuming calls to DEFINE-ENUMERATION define NUMBERS-LESSP and LETTERS-LESSP.
For (3), this is a general question that is worth solving generally.
(sort objects (combine-orders/lessp (letters :key doubleton-letter)
(numbers :key doubleton-number)))
Problem solved.
Ok, now we need to implement the macros. To avoid the cost of
calling POSITION twice in a row with the same arguments, we could
cache the results, which could be interesting an optimization for the
whole program, or we can write ad-hoc code like name-ORDER:
(defmacro define-enumeration (name object-list)
"
DO: Defines an enumeration, that is two functions name-LESSP
and name-ORDER that compare the objects in OBJECT-LIST.
"
`(eval-when (:compile-toplevel :load-toplevel :execute)
(defun ,(intern (format nil "~A-LESSP" name)) (a b)
(let ((i (position a ',object-list))
(j (position b ',object-list)))
(if (and i j)
(< i j)
(error "~A and ~A are not comparable with ~A-LESSP"
a b ',name))))
(defun ,(intern (format nil "~A-ORDER" name)) (a b)
(let ((i (position a ',object-list))
(j (position b ',object-list)))
(if (and i j)
(cond ((< i j) -1)
((> i j) +1)
(t 0))
(error "~A and ~A are not comparable with ~A-ORDER"
a b ',name))))
',name))
(defmacro combine-order/lessp (criterion &rest others)
"
CRITERION: An order-designator,
or a list (order-designator &key key).
An order-designator is a symbol naming a function that takes
two arguments and returns -1, 0 or 1 depending on the relative order
of these arguments, or a symbol naming an enumeration as defined
by DEFINE-ENUMERATION, (and the order designated is therefore
criterion-ORDER).
KEY is a symbol naming a function extracting the key to compare.
OTHERS: Other sub-criteria.
RETURN: A LESSP function comparing two objects according to the criteria.
"
(flet ((order-funame (name)
(multiple-value-bind (symbol status)
(find-symbol (format nil "~A-ORDER" name) (symbol-package name))
(if (and status (fboundp symbol))
symbol
name))))
(let ((normalized-criteria
(mapcar (lambda (criterion)
(if (atom criterion)
(list (order-funame criterion) 'identity)
(list (order-funame (first criterion))
(or (getf (rest criterion) :key)
'identity))))
(cons criterion others))))
(labels ((gen-steps (criteria)
(if criteria
(destructuring-bind (order key) (first criteria)
`(ecase (,order ,(if (eq 'identity key)
'a
`(,key a))
,(if (eq 'identity key)
'b
`(,key b)))
((-1) t)
((+1) nil)
((0) ,(gen-steps (rest criteria)))))
'nil)))
`(lambda (a b)
(minusp ,(gen-steps normalized-criteria)))))))
Exercise 1: write a macro define-combined-lessp that would define a
named lessp function instead of an anonymous function like
combine-order/lessp, so we could write:
(define-enumeration numbers (1 2 3 4 5 6 7))
(define-enumeration letters (a b c d e f))
(define-combined-lessp doubleton-lessp
(letters :key doubleton-letter)
(numbers :key doubleton-number))
(sort objects (function numbers-lessp) :key (function doubleton-number))
(sort objects (function letters-lessp) :key (function doubleton-letter))
(sort objects (function doubleton-lessp))
--
__Pascal Bourguignon__ http://www.informatimago.com/
NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.
Erik R.
Okay, here's another question. Is there any compelling reason to
change from my working version using a macro, that expands out the
cond/let tree, to use functions? I might do it just for practice, but
I'm curious to know where the consensus on Good Efficient Coding lies
on matters like this.
Erik
Erik R.
>
> read more »
Good lord! While I'm delighted to find a community so willing to help
out, I'm eerily amazed at the level of detail some of you are willing
to go to. Pascal, please tell me you pasted in part of your
application source into that message and didn't write all that nicely
commented code just for me. I'm very impressed by the simplicity and
readability of the final code you've arrived to after abstracting away
the macro stuff.
Thank you for providing another solution. It's very educational to
read through alternate solutions (and coding styles), particularly to
a problem that I've spent so much time thinking about already.
Cheers,
Erik
P.S. I haven't decided whether I prefer the < or lessp suffix yet.
They both make a lot of sense.
Slobodan Blazeski
>
> - Show quoted text -
The other posters already gave you a lot of good suggestions,
especially the Pascal advice for solving the general problem instead
is excellent, it could improve your toolbox and elad to clean design.
The answer lies in the hyperspec if you want to use sort with your own
predicate functions make sure that it return generalized boolean. How
would you write the function that return that predicate that's up to
you.
One more thing, why do you care so much about efficiency? You're
creating some number crunching code or 3d simulation or something like
that ? If you don't most of the time will be spend on gui,waiting for
user input, networking , database etc that your optimizations will
make no difference even if lisp code runs at no time. Even if you do
something that needs heavily optimized code do you already created
your app ? Is your code clean and doing what it sopose to do ? Have
you profiled your code and find out that the enum sorting function is
the real bottleneck ? Or you fell victim of premature optimization
and wasting time improving something that doesn't matter very much.
After I sow how many overhead comes from code that is outside of my
control I don't optimize anything unless the code the answer to above
is yes . Optimization is a good looking trap but I prefer to avoid it.
It's a huge waste of time.
Bobi
Pascal Bourguignon
> Good lord! While I'm delighted to find a community so willing to help
> out, I'm eerily amazed at the level of detail some of you are willing
> to go to. Pascal, please tell me you pasted in part of your
> application source into that message and didn't write all that nicely
> commented code just for me.
Sorry, this is custom code just for you! :-)
CL is so fun, we can hardly resist.
> I'm very impressed by the simplicity and
> readability of the final code you've arrived to after abstracting away
> the macro stuff.
Yes, the point is to just sexpify your problem statement, and then
implement the missing macros and functions.
Another good example is:
Alan Crowe's runable pseudo-code.
http://groups.google.com/group/comp.lang.lisp/msg/a827235ce7466a92
> Thank you for providing another solution. It's very educational to
> read through alternate solutions (and coding styles), particularly to
> a problem that I've spent so much time thinking about already.
>
> Cheers,
> Erik
>
> P.S. I haven't decided whether I prefer the < or lessp suffix yet.
> They both make a lot of sense.
--
__Pascal Bourguignon__ http://www.informatimago.com/
NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.
Erik R.
These are good points, Bobi. I'm working on an AI search problem that
I've wrestled with in a few other languages and the size of the search
space has so far proven too much for me to conquer. So in my Lisp
implementation, I'm dotting my i's and crossing my t's as I go along.
Plus, I'm just generally interested in good coding practices as I
enter this new programming realm.
Thanks for your comments.
Erik
Zach Beane
> Okay, here's another question. Is there any compelling reason to
> change from my working version using a macro, that expands out the
> cond/let tree, to use functions? I might do it just for practice, but
> I'm curious to know where the consensus on Good Efficient Coding lies
> on matters like this.
Macros can't be funcalled or applied. That means they can't easily
participate in higher-order operations that involve passing around a
function object.
When a macro is redefined, compiled callers must be recompiled.
Macros can't be traced.
There are some really stellar ways to use macros; see
http://groups.google.com/group/comp.lang.lisp/msg/2ff89986ee77f639
or
http://groups.google.com/group/comp.lang.lisp/msg/86cf454beb8a42f9
for a couple examples. But I think Norvig really nails it with his
"Lessons of PAIP" at http://norvig.com/Lisp-retro.html , particularly
with:
1. Use anonymous functions. [p. 20]
2. Create new functions (closures) at run time. [p. 22]
3. Use the most natural notation available to solve a problem. [p. 42]
6. Use macros (if really necessary). [p. 66]
52. A word to the wise: don't get carried away with macros [p. 855].
Zach
Rob St. Amant
> I'm working on an AI search problem that I've wrestled with in a few
> other languages and the size of the search space has so far proven
> too much for me to conquer. So in my Lisp implementation, I'm
> dotting my i's and crossing my t's as I go along.
Out of curiosity, what's the nature of the AI problem? There are some
knowledgeable AI people who post here and may be able to point you
toward existing systems in the same area.
Slobodan Blazeski
>
> - Show quoted text -
Wellcome to lisp, the language for doing AI :) I'm curious what kind
of problem are you working on ? There's already a tons of lisp code
maybe there's something that could make your life easier. Of course
unless you have to kill me if you tell me.
bobi
Erik R.
I'm working on a double dummy bridge solver. I'm pretty sure that the
most successful solution to the problem is by Matt Ginsberg[1]. At
it's core, it's just a min-max problem, but, like all min-max problems
bigger than tic-tac-toe, the cleverness to the solution is in trimming
the tree. My Java and D implementations haven't worked much past
hands of 8 or 9 cards in 10-15 minutes. Ginsberg claimed to do a full
hand of 13 cards in less than a second back in 1999.
I'm just starting, so I'm just doing the easy min-max algorithm stuff
so far. One thing that I'm not certain about is how to store my
current min-max state. I've got a half-dozen state variables, that,
coming from Java, I instinctively put into slots in a CLOS object, but
I'm pretty sure that's a silly approach. When you've got a few
variables that a dozen functions need access to, should that just be a
let with some defuns inside? That's gotta be better than defparameter-
ing them globally, right?
I'm sure I'll be posting other ponderings here in the coming weeks/
months.
Erik
WJ
> "Erik R." <rasmus...@gmail.com> writes:
>
> [snip]
> > I also have lists of doubletons (currently represented as cons cells)
> > with one number and one letter each. Like so:
> >
> > (setf values '((3 . F) (4 . C) (2 . A) (6 . C) (7 . E)))
> >
> > I want to be able to 1) sort by number, 2) sort by letter, 3) sort by
> > both number and letter.
> [snip]
> > As for sorting on both number and letter, my mind is drawing a
> > blank.
>
> I was drawing a blank, too, until I read this section of the SORT
> page:
>
> The predicate is assumed to consider two elements x and y to be
> equal if (funcall predicate x y) and (funcall predicate y x) are
> both false.
>
> (BTW, this is one of the reasons I think it's valuable to learn how to
> parse the hyperspec, instead of using a "lite" reference like the one
> in ANSI Common Lisp.)
>
> With that hint, I came up with this:
>
> (defparameter conses
> '((8 . 5) (9 . 5) (1 . 9) (1 . 3) (2 . 51) (8 . 11) (5 . 3)))
>
> (defun sort-fun (test key)
> (lambda (a b)
> (funcall test (funcall key a) (funcall key b))))
>
> (defun cascaded-predicate (&rest funs)
> (lambda (a b)
> (dolist (fun funs nil)
> (cond ((funcall fun a b)
> ;; A is certainly less than B; return true
> (return t))
> ((not (funcall fun b a))
> ;; A is not less than B, and vice-versa: keep going
> )
> (t
> ;; A is certainly not less than B: return nil
> (return nil))))))
>
> (defun cascade-sort (sequence &rest tests-and-keys)
> (let ((funs (loop for (test key) on tests-and-keys by #'cddr
> collect (sort-fun test key))))
> (let ((predicate (apply #'cascaded-predicate funs)))
> (sort sequence predicate))))
>
> #|
>
> (cascade-sort (copy-tree conses) #'< #'car)
> ((1 . 9) (1 . 3) (2 . 51) (5 . 3) (8 . 5) (8 . 11) (9 . 5))
>
> (cascade-sort (copy-tree conses) #'< #'car #'< #'cdr) =>
> ((1 . 3) (1 . 9) (2 . 51) (5 . 3) (8 . 5) (8 . 11) (9 . 5))
>
> (cascade-sort (copy-tree conses) #'< #'car #'> #'cdr) =>
> ((1 . 9) (1 . 3) (2 . 51) (5 . 3) (8 . 11) (8 . 5) (9 . 5))
>
> (cascade-sort (copy-tree conses) #'> #'car #'> #'cdr) =>
> ((9 . 5) (8 . 11) (8 . 5) (5 . 3) (2 . 51) (1 . 9) (1 . 3))
>
> (cascade-sort (copy-tree conses) #'> #'car #'< #'cdr) =>
> ((9 . 5) (8 . 5) (8 . 11) (5 . 3) (2 . 51) (1 . 3) (1 . 9))
>
> (cascade-sort (copy-tree conses) #'< #'cdr #'< #'car) =>
> ((1 . 3) (5 . 3) (8 . 5) (9 . 5) (1 . 9) (8 . 11) (2 . 51))
>
> (cascade-sort (copy-tree conses) #'< #'cdr #'> #'car) =>
> ((5 . 3) (1 . 3) (9 . 5) (8 . 5) (1 . 9) (8 . 11) (2 . 51))
>
> |#
>
Using Scheme:
(define conses
'((8 . 5) (9 . 5) (1 . 9) (1 . 3) (2 . 51) (8 . 11) (5 . 3)))
(define (sort-func test key) (lambda (a b) (test (key a) (key b))))
(define (cascade-tests funcs)
(lambda (a b)
(eq? 'less
(any
(lambda (func)
(cond
((func a b) 'less)
((func b a) 'greater)
(else #f)))
funcs))))
(define (cascade-sort seq . tests-and-keys)
(define (make-funcs test key . more)
(cons (sort-func test key)
(if (null? more) '() (apply make-funcs more))))
(sort seq (cascade-tests (apply make-funcs tests-and-keys))))
guile> (cascade-sort conses < car)
((1 . 9) (1 . 3) (2 . 51) (5 . 3) (8 . 5) (8 . 11) (9 . 5))
guile> (cascade-sort conses < car < cdr)
((1 . 3) (1 . 9) (2 . 51) (5 . 3) (8 . 5) (8 . 11) (9 . 5))
guile> (cascade-sort conses < car > cdr)
((1 . 9) (1 . 3) (2 . 51) (5 . 3) (8 . 11) (8 . 5) (9 . 5))
guile> (cascade-sort conses > car > cdr)
((9 . 5) (8 . 11) (8 . 5) (5 . 3) (2 . 51) (1 . 9) (1 . 3))
guile> (cascade-sort conses > car < cdr)
((9 . 5) (8 . 5) (8 . 11) (5 . 3) (2 . 51) (1 . 3) (1 . 9))
guile> (cascade-sort conses < cdr < car)
((1 . 3) (5 . 3) (8 . 5) (9 . 5) (1 . 9) (8 . 11) (2 . 51))
guile> (cascade-sort conses < cdr > car)