They are certainly similar at each node, they descend into one of the subtrees which is chosen depending on the annotations. Our efforts culminate in the unification of the two search algorithms (!!) and winner. Thus, every tree is annotated with its measure. It makes sense to refer to this combination of measures of all elements as the measure of the tree instance Measured a v => Measured (Tree a v) v where While independent of the shape of the branching, i.e. on the placement of parenthesis, this may of course depend on the order of elements. In general, the tag at the root of a tree with n elements is measure a1 measure a2 Have the same annotations (v1 v2) (v3 v4)Īs long as the sequences of leaves are the same. For instance, the two trees (v1v2) (v3v4) v1 (v2(v3v4)) Thanks to the associativity of, this is true for any monoid. These values are independent of the actual shape of the tree. How does the annotation at the top of a tree relate to the elements at the leaves? In our two examples, it was the total number of leaves and the least priority respectively. Measure a = priority a - urgency of the element So that the smart constructor reads leaf :: Measured a v => a -> Tree v aįor our examples, the instances would be instance Measured a Size where We can capture this in a type class class Monoid v => Measured a v where Hence, a unified smart constructor reads branch :: Monoid v => Tree v a -> Tree v a -> Tree v aįor leaves, the tag is obtained from the element. Of the following monoid instances instance Monoid Size where The observation is that we obtain the tag of a branch by combining its children with the monoid operation tag (Branch. Moreover, the retrieval operations (!!) and winner are actually special cases of one and the same function!įor brevity, we will denote the associative operation of a monoid with () = mappend And by recognizing that the tags form a monoid, we can completely unify both implementations. Monoids – the grand unifierĪs we can see, one and the same tree structure can be used for two quite different purposes, just by using different annotations. | tag y = tag t = go y - winner on rightĪgain, we forgo balancing and thus insertion or deletion. Given size annotations, we can now find the n-th leaf: (!!) :: Tree Size a -> Int -> a Which automatically annotate the right sizes. We can make sure that they are always correct by using smart constructors: instead of using Leaf and Branch to create a tree, we use custom functions leaf :: a -> Tree Size aīranch :: Tree Size a -> Tree Size a -> Tree Size a Thus, we set v = Size and we want the annotations to fulfill tag (Leaf. Our example tree has 5 leaves in total and the subtree on the right contains 3 leaves. The solution is to annotate each subtree with its size. Ok, so accessing the 1st leaf was easy, how about the 2nd, 3rd, the n-th leaf? We can also implement the head operation which retrieves the leftmost element head :: Tree v a -> a ToList (Branch _ x y) = toList x ++ toList yĪnnotations are fetched by tag :: Tree v a -> v The leaves store the elements of our list from left to right. In other words, our trees look like this v Furthermore, every node is annotated with a value of type v data Tree v a = Leaf v a We would like to create a faster list-like data structure that reduces this to O(log n) i.e. logarithmic time.įor that, we use a binary tree that stores the elements a at the leaves. Needs O(n) i.e. linear time to retrieve the n-th element of the list. As you well know, retrieving the head is fast but random access is much slower: xs !! n We begin with the simplest of all data structures, the linked list. Let me explain how this monoid magic works. How can one tree be useful for so many different data structures? The answer: monoids! Namely, the finger tree works with elements that are related to a monoid, and all the different data structures mentioned above arise by different choices for this monoid. Moreover, any fancy and custom data structures like interval trees or something for stock trading are likely to be implementable in this framework as well. For example, you can do sequences, priority queues, search trees and priority search queues. This tutorial was originally posted on his blog.Ī very powerful application of monoids are 2-3 finger trees, first described by Ralf Hinze and Ross Patterson.īasically, they allow you to write fast implementations for pretty much every abstract data type mentioned in Okasaki’s book on purely functional data structures. He maintains and develops several open source libraries, including reactive-banana (a library for functional reactive programming) and threepenny-gui (a browser-based GUI framework). Codementor Haskell Expert Heinrich Apfelmus has been using Haskell as his programming language of choice for over a decade now.
0 Comments
Leave a Reply. |