🚀 go-pugleaf

Chris.Holt@newcastle.ac.uk (Chris Holt) writes:

>boehm@parc.xerox.com (Hans Boehm) writes:

>>gudeman@cs.arizona.edu (David Gudeman) writes:

>>>In article  <1991Apr22.153149.8082@newcastle.ac.uk> Chris Holt writes:
>[about sorting using a partial order relation as a parameter]

>>>I know that is the standard solution, but I wonder if a better
>>>solution wouldn't be a function $ord : D -> Int$ that maps domain
>>>objects into arbitrary integers with the property that if $d1 < d2$
>>>by the partial order, then $ord(d1) < ord(d2)$.  ($d1 < d2$ means that
>>>$d1 <= d2$ and $d1 =/= d2$.)

>>There is no such function mapping character strings to integers.  Note
>>that "a" < "aa" < "aaa" < ...infinitely many strings... < "b".  No subset
>>of the integers has this property.  See any set theory book for a
>>discussion of transfinite ordinals.

>There can be a such a function for the finite strings; you use
>the lengths of the strings, so
>  a < b < ... < z < aa < ab < ... az < ba < bb < (rest of 2-sequences)
>    < (3-sequences) < (4-sequences) etc.
>Agreed the ordering given by Hans Boehm requires a dense codomain,
>but again the rationals are dense, and so can handle finite and
>repeating strings, and they can be mapped to the integers (though
>without the obvious ordering being preserved).

I thought the original point of this was to specify an order for sorting.
Certainly the set of character strings, rationals, and integers all have
the same cardinality.  Thus I can find 1-1 mappings between them.  But to
be useful, they have to preserve the desired ordering.  For character
strings, this usually means lexicographic ordering, and there's no way
to preserve that by mapping to the integers.

I agree that taking ord: D -> Rationals would work in all common cases, but it
seems a bit expensive in practice.

Hans
boehm@xerox.com