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

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

states our motivation (extra dry) for this design.

> 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 of
> *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 actually provide.

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 sequences) and
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 specialized sequence
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
structures.

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

Sebastian.