Last time around, I walked through the implementation of
\na very simple binary search tree. The implementation that I showed
\nwas reasonable, if not great, but it had two major limitations. First,
\nit 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
\na trivial tree implementation, it’s very easy for the tree to become
\nhighly unbalanced, resulting in poor performance.<\/p>\n
Today, we’ll look at how to extend the implementation so that our BST
\nbecomes useful as a key\/value dictionary type. We’ll take two different
\napproaches to that, each of which demonstrates some common Haskell
\ntechniques: one based on on using higher order functions, and one based on
\nusing tuples. Balancing the tree will be a task for another day.<\/p>\n
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
\nis really only for tutorial purposes.<\/p>\n
<\/p>\n
Here’s what we’d like to do. Instead of just being able to answer the
\nquestion “Is the value X in this tree?”, we want to be able to ask “Is
\nthere a value in this tree is associated with X, and if so, what is it?”.\n<\/p>\n
The way that we’ll do that is to use second-order functions<\/em>. First, we need to define a type for the comparison function. Given two Now, we can build a new version of the search tree. We’ll start There are two main differences between this and our original version. <\/p>\n For searching the tree, we want a different kind of operator than As it happens, Haskell has a helpful solution for that. There’s a type We’re going to put the two function parameters first<\/em> in the implementation; you’ll see why in a moment.<\/p>\n Before moving on, there’s one new thing in that implementation: the To be able to use this new tree, we need to provide a type for its 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. <\/p>\n 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 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 Just for the sake of being twisted, here’s a little bugger to populate And here’s a quick demonstration of using it in GHCI:<\/p>\n 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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[89],"tags":[],"class_list":["post-234","post","type-post","status-publish","format-standard","hentry","category-haskell"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-3M","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/234","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=234"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/234\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=234"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=234"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=234"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\nInstead of using the built in equality operator for comparing search keys
\nand nodes, we’ll use a function, which we’ll pass as a parameter to the
\nsearch operations.<\/p>\n
\nvalues – a key, and a value – we need to be able to determine whether the
\nkey is greater than<\/em>, equal to<\/em>, or less than<\/em> the
\nvalue. Second, given a value stored in the tree, we need to be able to
\nextract a key from it.<\/p>\n\n>data Comparison = Greater | Equal | Less\n>\n>type CompareFunc a = a -> a -> Comparison\n>\n>type KeyExtractor a b = a -> b\n<\/pre>\n
\nwith a type declaration, and the implementation of the insert operation.<\/p>\n\n>data KeyedSearchTree a = KSTNode a (KeyedSearchTree a) (KeyedSearchTree a)\n> | KSTEmpty deriving (Show)\n>\n>kstInsert :: Ord b => (KeyExtractor a b) -> CompareFunc b -> (KeyedSearchTree a) -> a -> (KeyedSearchTree a)\n>kstInsert kextract comp (KSTNode k left right) v =\n> case (comp (kextract k) (kextract v)) of\n> Greater -> KSTNode k (kstInsert kextract comp left v) right\n> Equal -> KSTNode v left right\n> Less -> KSTNode k left (kstInsert kextract comp right v)\n>kstInsert kextract comp KSTEmpty v = KSTNode v KSTEmpty KSTEmpty\n>\n<\/pre>\n
\n
\ninsert.<\/li>\n
\nvalues, we perform comparison on keys<\/em> using an extraction function passed as a parameter to the insert.<\/li>\n<\/ol>\n
\nwe used in the generic BST. We don’t just want to know if there’s
\na value with a particular key in the tree; we want to get<\/em>
\nthat value. And that leads us to a problem: What if there is no value
\nwith the specified key in the tree? What do we return?<\/p>\n
\ncalled Maybe<\/code> designed for exactly this purpose: it’s used for
\nboth parameters and return values where a value is optional. You can think
\nof it as being something like a metatype that allows you to distinguish
\nbetween a type that *must* have a value, and a type that allows null
\nvalues. A value of type Maybe a<\/code> can be either Just
\nx<\/code>, where x is of type a<\/code>, or Nothing<\/code>. Maybe<\/code> also happens to be a monad, which gives it some really neat properties that we’ll see later.<\/p>\n\n>kstSearch :: (KeyExtractor a b) -> (CompareFunc b) -> (KeyedSearchTree a) -> b -> Maybe a\n>kstSearch keyextract compare (KSTNode v left right) key =\n> case (compare (keyextract v) key) of\n> Greater -> kstSearch keyextract compare left key\n> Equal -> Just v\n> Less -> kstSearch keyextract compare right key\n>kstSearch _ _ KSTEmpty _ = Nothing\n>\n<\/pre>\n
_<\/code> 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<\/em> what value
\nis used there. Since searching an empty tree will always fail, we don’t
\ncare 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
\never looking at them: nothing can be fund in an empty tree.<\/p>\n
\nelements, and the comparison and key-extraction functions for that type.
\nWe’ll start with a tuple implementation. In Haskell, tuples are a kind of
\nfixed-length sequence where the tuple type specifies a distinct type for each of values in the sequence. For example, (1, 3.14, \"foo\")<\/code> is a tuple with three elements (a 3-tuple<\/em>), and the first element has type Integer<\/code>, the second has type Float<\/code>, and the third element has type String<\/code>. 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)<\/code>.<\/p>\n\n>trivialCompare a b | a > b = Greater\n> | a | otherwise = Equal\n>\n>tupleGetkey :: Ord k => (k,v) -> k\n>tupleGetkey (k,v) = k\n<\/pre>\n
\nonly 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<\/em> how to work with tuples. <\/p>\n\n>\n>tupleKSTInsert :: Ord k => KeyedSearchTree (k,v) -> (k,v) -> KeyedSearchTree (k,v)\n>tupleKSTInsert = kstInsert tupleGetkey trivialCompare\n>\n>tupleKSTSearch :: Ord k => KeyedSearchTree (k,v) -> k -> Maybe (k,v)\n>tupleKSTSearch = kstSearch tupleGetkey trivialCompare\n<\/pre>\n
\nimplementation is even based on our KeyedSearchTree<\/code>. In fact, we can even mask out the fact that it’s tuples!<\/p>\n\n>type DictionaryTree k v = KeyedSearchTree (k,v)\n>\n>dtInsert :: (Ord k) => DictionaryTree k v -> k -> v -> DictionaryTree k v\n>dtInsert tree k v = tupleKSTInsert tree (k,v)\n>\n>dtSearch :: (Ord k) => DictionaryTree k v -> k -> Maybe v\n>dtSearch tree key =\n> case (tupleKSTSearch tree key) of\n> Just (k,v) -> Just v\n> Nothing -> Nothing\n>\n>dtEmpty = KSTEmpty\n<\/pre>\n
\na DictionaryTree<\/code> using a list of key\/value tuples. Since a user of a DictionaryTree<\/code> doesn’t actually know that it’s got tuples inside, this actually decomposes the tuples from the list in order to call dtInsert<\/code>. (Hey, I said<\/em> it was twisted!)<\/p>\n\n>populateDict :: Ord k => [(k,v)] -> DictionaryTree k v\n>populateDict pairs = foldr ( (k,v) t -> dtInsert t k v) dtEmpty pairs\n>\n>exampleDict = populateDict [(\"a\",4),(\"b\",17),(\"c\",21), (\"abc\",13), (\"bd\", 18)]\n<\/pre>\n
\nkokopelli:~\/Documents\/Blog markcc$ ghci tree2.lhs\n___ ___ _\n\/ _ \/ \/\/ __(_)\n\/ \/_\/\/ \/_\/ \/ \/ | | GHC Interactive, version 6.6, for Haskell 98.\n\/ \/_\\\/ __ \/ \/___| | http:\/\/www.haskell.org\/ghc\/\n____\/\/ \/_\/____\/|_| Type :? for help.\nLoading package base ... linking ... done.\n[1 of 1] Compiling Main ( tree2.lhs, interpreted )\nOk, modules loaded: Main.\n*Main>\n*Main> exampleDict\nKSTNode (\"bd\",18) (KSTNode (\"abc\",13) (KSTNode (\"a\",4) KSTEmpty KSTEmpty) (KSTNode (\"b\",17) KSTEmpty KSTEmpty)) (KSTNode (\"c\",21) KSTEmpty KSTEmpty)\n*Main> dtSearch exampleDict \"c\"\nJust 21\n*Main> dtSearch exampleDict \"q\"\nNothing\n*Main>\n<\/pre>\n","protected":false},"excerpt":{"rendered":"