[Ur] ord class and performance

Gabriel Riba gabriel at xarxaire.com
Fri Feb 27 10:21:00 EST 2015


When I make a lookup in a "Binary Search Tree" to decide whether it is 
equal to the root payload or it is in the left or right branch,

given the actual ord class definition, I have to make the comparison 
twice: with "lt" and "le", or with the help of the eq class, "eq" and 
then "lt".

while a "compare" function giving a ternary result {-1,0,1} or {LT, EQ, 
GT} (haskell style) would cut the comparisons in half.

A possible solution would be to substitute in the constructor function 
mkOrd, the second function "le" with a ternary result "compare" 
function, and define "le" in terms of "compare".




More information about the Ur mailing list