Original-Via: uk.ac.ed.dcs; Tue, 5 Nov 91 18:30:59 GMT
There were two small bugs in the solution of Mark Jones:
1) To avoid multiple traversal of data, comp needs to stop
to traverse data, if a non-EQ value has been found.
Hence the intuition behind comp should be rather
comp x y EQ | "x is less than y" = LT
| "x is equal to y" = EQ
| "x is greater than y" = GT
| "x and y are incomparable" = NR
comp x y z | z /= EQ = z
2) In the example for the derived instances the composition
worked the wrong way:
comp (Leaf n) (Leaf m) = comp n m
comp (u :^: v) (x :^: y) = comp u x . comp v y
comp (C x1 ... xn) (C y1 ... yn) = comp x1 y1 . ... . comp xn yn
etc...
means first to compare v/y and then u/x, first the xn/yn, etc.
-----
To overcome this, it seems to be appropriate to have instead
a binary comp function,
comp :: a -> a -> Order
is the type in the class Ord a and the derived instances
look as follows:
comp (Leaf n) (Leaf m) = comp n m
comp (u :^: v) (x :^: y) = comp u x @ comp v y
comp (C x1 ... xn) (C y1 ... yn) =
comp x1 y1 @ ... @ comp xn yn
where @ is
`@` x y = if x==EQ then y else x
This keeps the traversal order and stops evaluation when the first
non-EQ has been found.
Even select is now a bit more natural:
select lt eq gt nr x y
= case comp x y of LT -> lt; EQ -> eq; GT -> gt; NR -> nr
Stefan Kahrs
