Re: vector compare

[Jens Axel Søgaard <jensaxel@xxxxxxxxxxxx>]

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

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

As Sebastian argues, there not 1 natural order of vectors, but the
ordering in the srfi is /a/ natural order. A concrete
example is the sorting of polynomials:

     x^3 > x^2 + 1 > x^2 > 42

A concrete representation in terms of vectors yields:

  #(3 0 0 0) > #(2 0 1) > #(2 0 0) > #(42)



The choice of default order should also be seen in the light of:

  "The purpose of default-compare is providing some well-defined way
  of comparing two arbitrary Scheme values. This can be used in all
  situations in which the user is unwilling to define a compare
  procedure explicitly, for example because the actual details of
  the total order do not really matter."

Consider now the case where you have a list of vectors of numbers,
and wants to convert it to a set of of vectors of numbers. An
obvious plan is to sort the list, and then make a single traversal
of the sorted list skipping duplicates. In this scenario the
actual order is unimportant.

Suppose now that we have the following list:

  (list #10000(0 ... 0 1)
        #10001(0 ... 0 2)
        #10002(0 ... 0 3)
        #10003(0 ... 0 4))

In this scenerio the order used in the srfi is better
efficiencywise than the lexicographical order -- and not
only by a constant factor.

It is also possible to find a list where the srfi-ordering
is slower than the lexicograpic, but the slow down
will be bounded by a small constant factor. E.g.

  (list #10000(0 ... 0 1)
        #10000(0 ... 0 2)
        #10000(0 ... 0 3)
        #10000(0 ... 0 4))

--
Jens Axel Søgaard