AW: Tree insert, lookup with keys

Ingo Wechsung
Fri, 20 Dec 2002 12:08:01 +0100

Ketil wrote:

>But it isn't obvious what b is supposed to be.

Sure, it must be an instance of Ord. In a way, I promise the compiler not to
use anything but compare on b's. Of course, when I define n instances, there
will be n different b-Types that must not be confused.

>(Requires -fglasgow-exts)

Thanks for the tip. Since I am obviously still learning, I prefer not to use
the extensions until I know exactly what they are about. (As it seems, I am
just experiencing one case where the extensions are useful. I'm sure there
are many other cases.)

Meanwhile, I see 2 possibilities to solve the problem in standard Haskell:

(a) Stick with String keys
	key :: a -> String;

or, (b) forget class Keyed and for every type s in Tree s derive an instance
from Ord that defines compare accordingly.

Solution (b) seems not so good to me since we might need the standard Ord
behaviour elsewhere.
Solution (a) is practical and should perform fairly well, except when we
must write
something like
	key (Baz x s y) = show x;

Are there any other solutions in standard Haskell?