3-way compares and short-circuit sorting

*Alex Shinn* 05 Aug 2002 09:09 UTC

Perhaps it doesn't belong in this srfi, and it doesn't seem very
Scheme-ish, but I was wondering if anyone had given thought to C-style
comparisons that yield positive, negative or zero on comparison (as in
strcmp)? This lets you write efficient short-circuit tests such as:
int pred (obj a, obj b) {
return ((cheap_func(a) - cheap_func(b))
|| (expensive_func(a) - expensive_func(b)))
< 0;
}
where it is rare for the initial comparison to be zero. As it is now,
you have to either sort twice or build a custom sort pred. Building new
procedures is what Scheme is all about, so for the latter method I use
the following utility:
(define (chain-sort-predicate key1 pred<1 pred=1 key2 pred<2 . rest)
(define (make-sort-predicate key pred)
(if (eq? key identity)
pred
(lambda (a b) (pred (key a) (key b)))))
(let ((secondary
(if (null? rest)
(make-sort-predicate key2 pred<2)
(apply chain-sort-predicate (append (list key2 pred<2) rest)))))
(lambda (a b)
(let ((a1 (key1 a)) (b1 (key1 b)))
(or (pred<1 a1 b1)
(and (pred=1 a1 b1)
(secondary a b)))))))
which, without the sort-keys and variable-arity could just be
(define (chain-sort-predicate pred<1 pred=1 pred<2)
(lambda (a b)
(or (pred<1 a b)
(and (pred=1 a b)
(pred<2 a b)))))
which lets you do
(sort data (chain-sort-predicate pred<1 pred=1 pred<2))
but the problem arises when pred<1 and pred=1 are not so cheap. Usually
the steps needed to determine their value are the same, so it is a waste
to make the computation twice.
The solution in other languages is to define a general purpose
comparator, cmp in Python, <=> in Perl, which returns this trinary
value. [This is also useful in general for OO-programming because you
can define just this method and you get <, >, =, et al for free on a
given class.] Then you can sort with something-like
(sort data (lambda (a b) (nzero-or (cmp1 a b) (cmp2 a b))))
and maybe define utilities to make that cleaner.
Anyway, just some rambling, thought I'd mention it...
--
Alex