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? Ingo