Tree insert, lookup with keys

Ingo Wechsung
Fri, 20 Dec 2002 11:19:44 +0100


perhaps I don't understand the type system fully yet:

I want a tree that carrys some information of type s;

data Tree s = TNil | Branch s Tree Tree;

This is fine for String, Integer and other atomic types.

ins :: Tree s -> s -> Tree s;
ins Tnil s = Branch s Tnil Tnil;
ins (Branch s l r) x = case compare x s of {
	LT -> Branch s (ins l x) r;
	EQ -> Branch s l r;
	GT -> Branch s l (ins r x);

So far so good, however, I do not always want to compare everything.
What I really want is to have (compare (key x) (key s)) instead in the
definition of ins.

My attempt:

class Keyed a where {		-- Type a is keyed if it has a key function.
	key :: Ord b => a -> b;	-- key is a function, that, when applied to
a yields some b that is comparable

and then

data Sym  = Sym String Int Ty;		-- Ty  is another algebraic type
instance Keyed Sym where {
	key (Sym a _ _) = a;	-- use string as key

But I always get the following message:
 Cannot unify the type-signature variable `b` with the type `String`
	 Expected type: b
	 Inferred Type: String
 In the definition of `key': a

Why is this? Has "key" to return the very same type for every instance?
After all, I need type `b' in compare only so it should not matter what it
really is. The compiler could check if for every instance key is defined so
that the return type is some instance of Ord, couldn't he.

Merry Christmas