Re; ordNub

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

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
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe