Hi, 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 Ingo
Ingo Wechsung
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 }
But it isn't obvious what b is supposed to be. Try multi-parameter type classes e.g. class (Ord b) => Keyed a b where key :: a -> b (I'm possibly messing up the placement of the 'Ord b' qualifier)
and then
data Sym = Sym String Int Ty; -- Ty is another algebraic type instance Keyed Sym String where key (Sym a _ _) = a
(Requires -fglasgow-exts) -kzm -- If I haven't seen further, it is by standing in the footprints of giants
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/
participants (3)
-
Alastair Reid -
Ingo Wechsung -
ketil＠ii.uib.no