Re: vector compare

[Sebastian Egner <sebastian.egner@xxxxxxxxxxx>]

Per Bothner wrote:
> 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?

Built-in lexicographical orders on vectors
have hurt me more than once
for ordering actual 'vectors', i.e.
elements of vector spaces (abelian group
with a field acting on it) of different
dimension. By using the lex order you
effectively fix an embedding of the
lower-dimensional vector spaces into
the higher---and that is often the wrong
thing to do.

Concerning prior art: Are you really
asking me why anybody anywhere would
like to order sequences by length and
then lexicographically, instead just
lexicographically, and where you can
find published references to programs
that do that?

Actually, I do not intend to settle
this question by digging up 'prior art' and
looking where the bigger pile is. Let
us focus on which problem we would
like to solve, and how the solutions
fit with the structures that are present in
Scheme. The advantage of ordering LIST
and VECTOR the same is that
it is easier to remember. The advantage
of ordering them differently is that
you get the choice---based on the basic
operations.

> > 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.

SRFI 44 defines a lot and implements
nothing. I think SRFI 44 represents a good deal of
good work. Yet it is still to be seen
that this is really the way data structures should be
organized in Scheme. Comparing containers,
for example, is a problem: SRFI 44 defines
nothing for that but its design excludes
several possible approaches already.

Concerning Kawa and Common Lisp, the
problem is the same: The object system brings
structure to the world of data types---but
it also imposes a certain point of view.
This point of is certainly plausible,
but it is not the only one, and its benefits are overrated.

My point of view is that the user should
be enabled to construct exactly the data structures
required for an application from prefab
building blocks---instead of finding a fully organized
world already. Initially the organized
world is nice, but sooner or later you hit brick walls,
and the more complex it gets the more
that hurts.

Now, if you have sequence data that
is naturally ordered lexicographically than you can
use LISTs or VECTORs ordered as lists
to represent the data. If you have sequences 
that are naturally ordered by length
and then lexicographically you can use VECTORs
or LISTs ordered as vectors. And in
both cases it is likely that the concrete default 
representation has something to do with
the application already. (Which is the result of
the 'natural ordering based on the available
primitive operations' thing.)

> 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.

And this what this SRFI is doing: Vector,
List, Number, String, Symbol, Char, etc. are all
subtypes of the overall Scheme object
type---and they all provide a compare procedure
that satisfies certain axioms. Furthermore
the orderings of number types are required
to be compatible with the tower of numeric
data types in R5RS, even though the tower
does not really define a subtype hierarchy
in the strong sense, because that makes
sense mathematically. Finally, default-compare
refines pair-compare. And that is as far
as the subtype thing goes in this SRFI.
In particular, LIST and VECTOR are *not* seen
as two concrete realizations of a common
container supertype.

Now your point of view is that Vector
and List should be interpreted as subtypes
of  a Sequence type---because SRFI
44, Kawa, and Common Lisp do that way
and it is "not a far-fetched concept."
(Quite natural even, I would say.)
But I do not find this concept back
in the definition of Scheme as it is now,
and there are alternative approaches
that give you more choice.

Don't get me wrong, I am in fact a fan
of the Sequence approach. I even experimented
with my own Sequence data type as an
add-on for Scheme, but not as an abstract
type (or interface) to unify LIST and
VECTOR. The sequences I experimented with
were self-optimizing (amortized) data
structures that eventually adapt to their use
case (in particular LIFO, FIFO, or random-access)
and are reasonably efficient
(i.e. O(n log n) with small constants)
over an extremely large scale of size, including
external memory algorithms. In the end,
the implementation went out of hand for
a hobby project and I had to stop. Now
these sequences do not fit SRFI 44, nor
Kawa, nor Common LISP and they coexist
with LIST and VECTOR.

> 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.

My whole point is that the order to
be defined for a data type does not follow
from the data type or its supertypes
but is part of what the data type means.
Now if the uniform vectors represent
elements of vector spaces than you might
want a different ordering than if they
represent strings.

Btw., strings are one the most exceptional
things around. The lex. ordering is
historic and not at all 'God-given'.
Japanese dictionaries contain several
alternative orderings: By stroke number,
by radical (prototypes of parts of the
actual characters, most are also characters
in themselves), or by pronounciation.
"The natural order" of strings
is a matter of taste. In Germany the treatment of
Umlauts has changed during the past
30 years: Today ä is inserted where
'ae' would be. But I have lots of dictionaries
at home that insert ä where
'a' would be. Using Unicode scalar values
ä has a high scalar value
so it would be inserted after 'z'. Ordering
strings by length>lex can also make
sense in some applications.
 
So I have difficulties following you
argumentation above.
My point of view is:

Yes, strings use lex. order because
that makes sense as a general default.
No, that does not imply that uniform
vectors should also use lex. order.
They can better provide one or more
orders that make sense for
their intended applications. And no,
that still does not imply that the built-in
VECTOR type should be ordered in any
particular way for the sake of
uniformity.

Historically, "uniform vectors"
do not allow you to specify the ordering you
want to use---but they should. Lukily,
in the majority of the cases it is sufficient
to define any ordering at all. If u8vector
or anything provides a default order,
I would make it length>lex because
that is the most natural and efficient for
this type, unless you tell me that you
always use them in hashing in which
case I would make the default order
by hashcode, then length>lex. ;-)

Sebastian.