Sorting by enumeration - comp.lang.lisp

Message from discussion Sorting by enumeration

Zach Beane

View profile

More options Aug 20 2007, 2:06 pm

Newsgroups: comp.lang.lisp

From: Zach Beane <x...@xach.com>

Date: Mon, 20 Aug 2007 14:06:59 -0400

Local: Mon, Aug 20 2007 2:06 pm

Subject: Re: Sorting by enumeration

  Reply to author
  |
  Forward
  | Print
  | View thread
  | Show original
  | Report this message
  | Find messages by this author
  

"Erik R." <rasmussene...@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))

Tweaking this to work with your original example should, I hope, be
pretty trivial.

Zach

Reply to author Forward