Tree insert, lookup with keys
20 Dec 2002 12:40:36 +0000
> 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 email@example.com
Reid Consulting (UK) Limited http://www.reid-consulting-uk.ltd.uk/alastair/