Last time around, I walked through the implementation of
a very simple binary search tree. The implementation that I showed
was reasonable, if not great, but it had two major limitations. First,
it uses equality testing for the search, so that the implementation is only really suitable for use as a set; and second, because it’s such
a trivial tree implementation, it’s very easy for the tree to become
highly unbalanced, resulting in poor performance.
Today, we’ll look at how to extend the implementation so that our BST
becomes useful as a key/value dictionary type. We’ll take two different
approaches to that, each of which demonstrates some common Haskell
techniques: one based on on using higher order functions, and one based on
using tuples. Balancing the tree will be a task for another day.
As an aside: in a real Haskell program, you would probably never write a simple type like this. Haskell has a great library, and it’s got plenty of library types that do a much better job than this. This
is really only for tutorial purposes.
Here’s what we’d like to do. Instead of just being able to answer the
question “Is the value X in this tree?”, we want to be able to ask “Is
there a value in this tree is associated with X, and if so, what is it?”.
The way that we’ll do that is to use second-order functions.
Instead of using the built in equality operator for comparing search keys
and nodes, we’ll use a function, which we’ll pass as a parameter to the
First, we need to define a type for the comparison function. Given two
values – a key, and a value – we need to be able to determine whether the
key is greater than, equal to, or less than the
value. Second, given a value stored in the tree, we need to be able to
extract a key from it.
>data Comparison = Greater | Equal | Less > >type CompareFunc a = a -> a -> Comparison > >type KeyExtractor a b = a -> b
Now, we can build a new version of the search tree. We’ll start
with a type declaration, and the implementation of the insert operation.
>data KeyedSearchTree a = KSTNode a (KeyedSearchTree a) (KeyedSearchTree a) > | KSTEmpty deriving (Show) > >kstInsert :: Ord b => (KeyExtractor a b) -> CompareFunc b -> (KeyedSearchTree a) -> a -> (KeyedSearchTree a) >kstInsert kextract comp (KSTNode k left right) v = > case (comp (kextract k) (kextract v)) of > Greater -> KSTNode k (kstInsert kextract comp left v) right > Equal -> KSTNode v left right > Less -> KSTNode k left (kstInsert kextract comp right v) >kstInsert kextract comp KSTEmpty v = KSTNode v KSTEmpty KSTEmpty >
There are two main differences between this and our original version.
- In this version, instead of using the builtin “>” comparison operator, we use a comparison function passed as a parameter to the
- Instead of performing comparisons using the entire
values, we perform comparison on keys using an extraction function passed as a parameter to the insert.
For searching the tree, we want a different kind of operator than
we used in the generic BST. We don’t just want to know if there’s
a value with a particular key in the tree; we want to get
that value. And that leads us to a problem: What if there is no value
with the specified key in the tree? What do we return?
As it happens, Haskell has a helpful solution for that. There’s a type
Maybe designed for exactly this purpose: it’s used for
both parameters and return values where a value is optional. You can think
of it as being something like a metatype that allows you to distinguish
between a type that *must* have a value, and a type that allows null
values. A value of type
Maybe a can be either
Just, where x is of type
Maybe also happens to be a monad, which gives it some really neat properties that we’ll see later.
We’re going to put the two function parameters first in the implementation; you’ll see why in a moment.
>kstSearch :: (KeyExtractor a b) -> (CompareFunc b) -> (KeyedSearchTree a) -> b -> Maybe a >kstSearch keyextract compare (KSTNode v left right) key = > case (compare (keyextract v) key) of > Greater -> kstSearch keyextract compare left key > Equal -> Just v > Less -> kstSearch keyextract compare right key >kstSearch _ _ KSTEmpty _ = Nothing >
Before moving on, there’s one new thing in that implementation: the
_ pattern. In Haskell, that’s a pattern that means “I don’t care”. It matches any value, but doesn’t bind it to anything. So you can’t access the value of a parameter matched by an “_”, which makes sense, since by using the “_” you’ve said that you don’t care what value
is used there. Since searching an empty tree will always fail, we don’t
care what functions are provided for doing compares, and we don’t care what key is being searched for. We know the result of the function without
ever looking at them: nothing can be fund in an empty tree.
To be able to use this new tree, we need to provide a type for its
elements, and the comparison and key-extraction functions for that type.
We’ll start with a tuple implementation. In Haskell, tuples are a kind of
fixed-length sequence where the tuple type specifies a distinct type for each of values in the sequence. For example,
(1, 3.14, "foo") is a tuple with three elements (a 3-tuple), and the first element has type
Integer, the second has type
Float, and the third element has type
String. Tuple types are written in the same way as tuples, but with types instead of values, so our example tuple as a whole has the type
For a search tree that looks like a typical dictionary, we can use an element type that’s a simple 2-tuple; the first element of the tuple will be a key, and the second will be the value. We don’t need to completely specify the types of the two elements of the tuple; we’ll have a more flexible implementation if we use type variables. For the search tree to work, the key type will need to be an ordered type, so we’ll constrain it with a type-class clause.
>trivialCompare a b | a > b = Greater > | a < b = Less > | otherwise = Equal > >tupleGetkey :: Ord k => (k,v) -> k >tupleGetkey (k,v) = k
Now we get to the reason for putting the function parameters first. Remember how we talked about currying the other day? Here’s a great example of how you might use it. We’ll create two new custom insert and search functions for our tuple based binary search tree, by providing
only the first two parameters (the key extractor and compare functions) to the generic keyed search tree insert and search functions; the result of doing that will be to return a two-parameter function with the key extract and compare functions internally bound, so that users of our tree don’t need to worry about the details. To them, the search tree just knows how to work with tuples.
> >tupleKSTInsert :: Ord k => KeyedSearchTree (k,v) -> (k,v) -> KeyedSearchTree (k,v) >tupleKSTInsert = kstInsert tupleGetkey trivialCompare > >tupleKSTSearch :: Ord k => KeyedSearchTree (k,v) -> k -> Maybe (k,v) >tupleKSTSearch = kstSearch tupleGetkey trivialCompare
We can get even a bit fancier: we can use another form of type definition to define a tuple tree type, and hide the fact that the
implementation is even based on our
KeyedSearchTree. In fact, we can even mask out the fact that it’s tuples!
>type DictionaryTree k v = KeyedSearchTree (k,v) > >dtInsert :: (Ord k) => DictionaryTree k v -> k -> v -> DictionaryTree k v >dtInsert tree k v = tupleKSTInsert tree (k,v) > >dtSearch :: (Ord k) => DictionaryTree k v -> k -> Maybe v >dtSearch tree key = > case (tupleKSTSearch tree key) of > Just (k,v) -> Just v > Nothing -> Nothing > >dtEmpty = KSTEmpty
Just for the sake of being twisted, here’s a little bugger to populate
DictionaryTree using a list of key/value tuples. Since a user of a
DictionaryTree doesn’t actually know that it’s got tuples inside, this actually decomposes the tuples from the list in order to call
dtInsert. (Hey, I said it was twisted!)
>populateDict :: Ord k => [(k,v)] -> DictionaryTree k v >populateDict pairs = foldr (\ (k,v) t -> dtInsert t k v) dtEmpty pairs > >exampleDict = populateDict [("a",4),("b",17),("c",21), ("abc",13), ("bd", 18)]
And here’s a quick demonstration of using it in GHCI:
kokopelli:~/Documents/Blog markcc$ ghci tree2.lhs ___ ___ _ / _ \ /\ /\/ __(_) / /_\// /_/ / / | | GHC Interactive, version 6.6, for Haskell 98. / /_\\/ __ / /___| | http://www.haskell.org/ghc/ \____/\/ /_/\____/|_| Type :? for help. Loading package base ... linking ... done. [1 of 1] Compiling Main ( tree2.lhs, interpreted ) Ok, modules loaded: Main. *Main> *Main> exampleDict KSTNode ("bd",18) (KSTNode ("abc",13) (KSTNode ("a",4) KSTEmpty KSTEmpty) (KSTNode ("b",17) KSTEmpty KSTEmpty)) (KSTNode ("c",21) KSTEmpty KSTEmpty) *Main> dtSearch exampleDict "c" Just 21 *Main> dtSearch exampleDict "q" Nothing *Main>