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