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

Re: default ordering of vectors

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

Sebastian Egner wrote:
Looking at the discussion again, I see only three major arguments:

(1) Conceptually vectors and lists are just sequences, and these are
conventionally ordered LEX by default.

This issue becomes very important in current and future Scheme variants that implement a "sequence hierarchy". This includes some existing Scheme languages (including Kawa) and other languages in the Lisp/Scheme family, including Common Lisp and Dylan.

Soem of us *do* think of lists and vectors as dfferent implementation choices of the same sequence abstraction. Having different ordering semantics would be inconsistent with such a model.

(2) LENGTH-LEX is more natural (and efficient) for sequences that
support a constant-time SIZE operation.

Most of the comments on this issue have argued that LEX is more natural for vectors. Since people disagree on what is "natural" (and most prefer LEX) all you're left with is an efficiency argument for certain use cases - and a loss for other use cases. Since the SRFI does support non-default comparisons, the efficiency argument is not that strong.

(3) Conceptually strings are "vectors of chars" and strings are conventionally
ordered LEX by default, so vectors should be ordered LEX as well in order
to reduce confusion.

 From my point of view, (2) is the most fundamental, in a mathematical
sense. By providing different orders for vectors and lists it is also
possible to have the two most important liftings of total orders to
sequences readily available.

But (2) isn't a "mathematical" argument. You say LENGTH-LEX is more "natural", but most of us seem to disagree, and more "efficient" (but only in some cases).

Actually, I'm not unsympathetic. If you're going to sort vectors (in the sense of sorting==grouping), and you have no semantic information, it probably makes most sense to first sort by length. But sorting without any semantic information is inherently arbitrary, and mostly you'll need an appplication-specific sorting anyway. I.e. sorting on "raw data-types" is inherently going to be wrong as often as it is right, and so there isn't a clear right way to do it. Given that, consistency with lists and strings should be the bigger concern.
	--Per Bothner
per@xxxxxxxxxxx   http://per.bothner.com/