Tree insert, lookup with keys

[Alastair Reid]

> 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/