Re: vector compare Per Bothner 09 Jun 2005 07:59 UTC

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?'
>

> http://srfi.schemers.org/srfi-67/srfi-67.html#node_toc_node_sec_Temp_20

"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
xxxxxx@bothner.com   http://per.bothner.com/