I want a tree that carrys some information of type s;
data Tree s = TNil | Branch s Tree Tree; ins :: Tree s -> s -> Tree s ...
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.
Type classes, multiparameter type classes, and the other approaches you and others suggest are one way of tackling the problem. In examples like this, I usually find that typeclass-based approaches are not the way to go. As datatypes get richer, I often find that I want to use different fields as keys in different situations. e.g., for a 'Person' type I might want to use name (surname and forename), address, age, social security number, etc. depending on the situation. Since I want to use different fields _of the same type_ as keys, a typeclass-based solution won't work. Instead, I use higher order functions. First, let's define some suitable comparision functions: type Ord a = a -> a -> Ordering -- some example field comparisions byName :: Ord Person byName x y = compare (nameOf x) (nameOf y) byAge :: Ord Person byAge x y = compare (ageOf x) (ageOf y) now we generalise your insert function: insBy :: Ord s -> Tree s -> s -> Tree s insBy cmp (Branch x l r) y = case cmp x y of ... ^^^ ^^^^^^^ A minor variation of this is to pass in selector functions: type Selector a b = a -> b -- example types involving 'Selector' nameOf :: Selector Person Name ageOf :: Selector Person Int insBy :: Ord key => Selector s key -> Tree s -> s -> Tree s insBy sel (Branch x l r) y = case compare (sel x) (sel y) of ... ^^^ ^^^^^^^ this is a bit easier to use but slightly less flexible (but probably not in any important way). -- Alastair Reid alastair@reid-consulting-uk.ltd.uk Reid Consulting (UK) Limited http://www.reid-consulting-uk.ltd.uk/alastair/