Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!crdgw1!uunet!mcsun!ukc!newcastle.ac.uk!turing!ncmh From: Chris.Holt@newcastle.ac.uk (Chris Holt) Newsgroups: comp.lang.misc Subject: Re: Optional static typing limits Message-ID: <1991Apr25.160451.18739@newcastle.ac.uk> Date: 25 Apr 91 16:04:51 GMT References: <2325@optima.cs.arizona.edu> Sender: news@newcastle.ac.uk Organization: University of Newcastle upon Tyne, UK, NE1 7RU Lines: 35 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). A partial order can always be strengthened to a total order, of course; but one thing I wondered as I decided to make my example partial is, must every algorithm for partial order sorting be at least o(n**2)? ----------------------------------------------------------------------------- Chris.Holt@newcastle.ac.uk Computing Lab, U of Newcastle upon Tyne, UK ----------------------------------------------------------------------------- "And when they die by thousands why, he laughs like anything." G Chesterton