[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.
> 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?'
states our motivation (extra dry) for
> Note that this difference makes it difficult
to have a unified
> "sequence hierarchy" as in Common Lisp.
> The problem is that ordering is defined in terms
> *implementation* types rather than semantics.
If I understand correctly, your argument
is that LIST and VECTOR should
both be interpreted as mere implementations
of some abstract SEQUENCE
data type, and that the ordering should
be defined for SEQUENCE, only. Hence,
all implementations of sequence should
have the same (default) ordering---
independently of what operations they
This is in contrast to the point of
view we have taken for this SRFI:
There are two abstract data types called
VECTOR and LIST, where
VECTOR is specified by a SIZE procedure
and a REF procedure
(e.g. constant-time random access finite-length
LIST is specified by procedures EMPTY?,
HEAD and TAIL (e.g.
unbounded finite stacks).
In our point of view, these abstract
types have a life of their own
and are not just simplified versions
of some hypothetical abstract
SEQUENCE type. (Which is entirely absent
in Scheme as it is today.)
Now for LIST the natural ordering is
lexicographic. For VECTOR the
both SIZE and REF operations are assumed
constant time and the
natural ordering is defined as first
by SIZE, then by REF (lex).
The concrete LIST and VECTOR types specified
in Scheme are
implementations of the abstract LIST
and VECTOR---and inherit
the ordering (part of the semantics)
from the abstract one. In fact,
we do not even talk about the abstract
LIST and VECTOR data
types explicitly; we only say "is
ordered like a VECTOR."
My experience is that both orders are
needed quite frequently
because sequence data types (i.e. finite
collections with elements
ordered by their relative position)
are used for so many different
purposes. The abstract SEQUENCE type
is great for simplifying
complicated data structure libraries
(like EDISON) but it also
rubs out any distinction between more
types (stack, queue, deque, steque,
string, chain, rope, vector,
tuple, array, streams, files etc.) At
least, I believe that having the
operations you need---and not more---is
the key to efficient data
To summarize, in our interpretation
a VECTOR is not just a LIST
with a "#" in front---it is
an entirely different abstract data type
(>constant-time random-access finite
sequence<), and as such
its instances should be ordered by the
most appropriate order.
If Scheme ever includes the notion of
SEQUENCE, and some
hierarchy of more restricted types,
it might be time to redesign
(e.g. defining the ordering together
with the type or something).