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

search operations.

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

insert. - 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

called `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

x`a`

, or `Nothing`

. `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 `(Integer,Float,String)`

.

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

a `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>