[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

This page is part of the web mail archives of SRFI 32 from before July 7th, 2015. The new archives for SRFI 32 contain all messages, not just those from before July 7th, 2015.

*To*: srfi-32@xxxxxxxxxxxxxxxxx*Subject*: 3-way compares and short-circuit sorting*From*: Alex Shinn <foof@xxxxxxxxxxxxx>*Date*: Mon, 05 Aug 2002 18:09:57 +0900*Delivered-to*: srfi-32@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx*User-agent*: Wanderlust/2.8.1 (Something) Emacs/21.2 Mule/5.0 (SAKAKI)

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

- Prev by Date:
**RE: Almost OT, < and <=** - Next by Date:
**a typo; min/max; partial orders** - Previous by thread:
**URL correction correction** - Next by thread:
**a typo; min/max; partial orders** - Index(es):