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

*To*: srfi-67@xxxxxxxxxxxxxxxxx*Subject*: Re: vector compare*From*: Sebastian Egner <sebastian.egner@xxxxxxxxxxx>*Date*: Thu, 9 Jun 2005 09:18:59 +0200*Delivered-to*: srfi-67@xxxxxxxxxxxxxxxxx*In-reply-to*: <dJAr2.A.s6H.Eu9pCB@rotkohl>

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

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.

> "sequence hierarchy" as in Common Lisp.

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

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.

**Follow-Ups**:**Re: vector compare***From:*Per Bothner

**Re: vector compare***From:*Michael Sperber

- Prev by Date:
**Optional arguments at the beginning** - Next by Date:
**Re: vector compare** - Previous by thread:
**Re: vector compare** - Next by thread:
**Re: vector compare** - Index(es):