Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!aplcen!boingo.med.jhu.edu!haven.umd.edu!ni.umd.edu!uc780.umd.edu!cs450a03 From: cs450a03@uc780.umd.edu Newsgroups: comp.lang.misc Subject: RE: Optional static typing limits Message-ID: <23APR91.08595134@uc780.umd.edu> Date: 23 Apr 91 08:59:51 GMT References: <8493:Apr1719:30:0791@kramden.acf.nyu.edu> <1991Apr22.153149.8082@newcastle.ac.uk> Sender: usenet@ni.umd.edu (USENET News System) Organization: The University of Maryland University College Lines: 35 Nntp-Posting-Host: uc780.umd.edu Chris Holt > Dan Bernstein >> >>And, as a first sample problem to be solved by a typing system: How do >>we write a generic, type-safe sorting routine? >What would be nice would be something of the form >Sort S <= > where S : sequence of D > D : domain > <= : partial_order (D x D -> boolean) > where partial_order : transitive & reflexive & antisymmetric >Of course, partial_order would be part of the standard toolbox of the >programmer; it maps the domain of dyadic D-to-boolean operations to >that subset satisfying the given properties. If you're going to sort, why not just go with sorting by a key? If you have some domain which is ordered, but which the builtin <= doesn't understand, why not just map it into some type which the builtin recognizes? (For example build a table of integers, where each integer corresponds to an element in the unsorted sequence.) You would then need to get at the permutation information which "sort" generates, but that need not be difficult. Also, sort had better deal with sorting strings of some sort, but that need not be difficult either. If the mapping from sequence of type X to sequence of builtin type is simple enough, there is no reason that a compiler couldn't optimize it out as a distinct step. I don't see any reason, by the way, to apply sort to a partial order which is not a complete order. Raul Rockwell