Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!elroy.jpl.nasa.gov!decwrl!parc!boehm From: boehm@parc.xerox.com (Hans Boehm) Newsgroups: comp.lang.misc Subject: Re: Optional static typing limits Message-ID: Date: 26 Apr 91 00:18:09 GMT References: <2325@optima.cs.arizona.edu> <1991Apr25.160451.18739@newcastle.ac.uk> Sender: news@parc.xerox.com Organization: Xerox PARC Lines: 41 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