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

Re: vector compare

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:

 > The default compare for vectors is unusual, and more critically it is
 > incompatible with the default compare for lists and strings.
 > The latter are both lexicographic compare.

Correct. In this SRFI, vectors are compared first by length and then
lexicographically by default.

 > I couldn't find a rationale for this difference.

The paragraph "What is the 'natural order' of lists and vectors?'


"The constant time access operations for Scheme vectors are length and ref. This suggests defining the natural order of vectors by first comparing the length and only if the lengths are equal by comparing the elements."

I don't get it.  How is that a rationale?

Do you have any examples or use cases or algorithms that are simpler
when using this "natural order"?  What prior art is there for
using this order?

If I understand correctly, your argument is that LIST and VECTOR should
both be interpreted as mere implementations of some abstract SEQUENCE
data type,

I'm saying that some Scheme implementations (at least Kawa) and at
least one SRFI (44) does this.  I'm also pointing out that Common Lisp
does this.  I.e. this is not a far-fetched concept.

and that the ordering should be defined for SEQUENCE, only.

Not quite.  It is true that if an ordering is defined for sequence,
then it would be bad to define inconsistent orderings for different
sub-types of sequence.  I'm making a weaker claim: if you define an
operation F on type A and on type B that are both sub-types of a common
super-type S then good object-oriented design suggests you should
define the operation F to have common properties (axioms) for both
A and B.

Even if you view vectors and lists as both sequences, it doesn't
follow that on operation F must be defined in terms of sequences.
However, it's usually a good idea.

Moreover, some schemes provide "uniform vectors", and there are SRFIs
that define them.  What is the natural order for a uniform vector?
By your argument, and I think "common sense" (admittedly unreliable)
it should be the same order as for normal vectors.  Certainly if you
believe uniform vectors "inherit" from an "abstract vector" type.

Now consider strings.  Is a string a vector?  If you have uniform
vectors, then it seems very strange to not view a string as a uniform
vector.  It follows that the ordering for strings should be the same
as for uniform vectors.

Strings use lexicographic order.
Hence uniform vectors should use lexicographic order.
Hence vectors should use lexicographic order.
	--Per Bothner
per@xxxxxxxxxxx   http://per.bothner.com/