[Haskell-cafe] Re; ordNub

[Doug McIlroy]

> I think the following computable function shows that it is always
> possible (it chooses an order during queries):

> Maintain a table, initially emtpy

> As soon as (a <= b) is requested, see if a and b are already in
> the table (using the computatble equality function) , if so, use
> their ordering in the table. If an element is not in the table, add it.

> Hence the table gives a consistent total order (it depends on which
> ordering queries are requested, but that is not relevant?)

This method has more than Gedanken value. Amusingly, I used it in "A 
killer adversary to quicksort" [Software - Practice and Experience 29
(1999) 341-344, http://www.cs.dartmouth.edu/~doug/mdmspe.pdf] to
drive essentially any quicksort (illustrated with the C standard
sort interface) into quadratic behavior. 

Doug McIlroy