Learn You a Haskell for Great Good! - Miran Lipovaca [60]
Let's Plant a Tree
To get a better feel for recursive data structures in Haskell, we’re going to implement a binary search tree.
In a binary search tree, an element points to two elements—one on its left and one on its right. The element to the left is smaller; the element to the right is bigger. Each of those elements can also point to two elements (or one or none). In effect, each element has up to two subtrees.
A cool thing about binary search trees is that we know that all the elements at the left subtree of, say, 5, will be smaller than 5. Elements in the right subtree will be bigger. So if we need to find if 8 is in our tree, we start at 5, and then because 8 is greater than 5, we go right. We’re now at 7, and because 8 is greater than 7, we go right again. And we’ve found our element in three hops! If this were a normal list (or a tree, but really unbalanced), it would take us seven hops to see if 8 is in there.
Note
Sets and maps from Data.Set and Data.Map are implemented using trees, but instead of normal binary search trees, they use balanced binary search trees. A tree is balanced if its left and right subtrees are of approximately the same height. This makes searching through the tree faster. But for our examples, we’ll just be implementing normal binary search trees.
Here’s what we’re going to say: A tree is either an empty tree or it’s an element that contains some value and two trees. Sounds like a perfect fit for an algebraic data type!
data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show)
Instead of manually building a tree, we’ll make a function that takes a tree and an element and inserts an element. We do this by comparing the new value to the tree’s root node. If it’s smaller than the root, we go left; if it’s larger, we go right. We then do the same for every subsequent node until we reach an empty tree. Once we’ve reached an empty tree, we insert a node with our new value.
In languages like C, we would do this by modifying the pointers and values inside the tree. In Haskell, we can’t modify our tree directly, so we need to make a new subtree each time we decide to go left or right. In the end, the insertion function returns a completely new tree, because Haskell doesn’t have a concept of pointers, just values. Hence, the type for our insertion function will be something like a -> Tree a - > Tree a. It takes an element and a tree and returns a new tree that has that element inside. This might seem like it’s inefficient, but Haskell makes it possible to share most of the subtrees between the old tree and the new tree.
Here are two functions for building the tree:
singleton :: a -> Tree a
singleton x = Node x EmptyTree EmptyTree
treeInsert :: (Ord a) => a -> Tree a -> Tree a
treeInsert x EmptyTree = singleton x
treeInsert x (Node a left right)
| x == a = Node x left right
| x < a = Node a (treeInsert x left) right
| x > a = Node a left (treeInsert x right)
singleton is a utility function for making a singleton tree (a tree with just one node). It’s just a shortcut for creating a node that has something set as its root, and two empty subtrees.
The treeInsert function is to insert an element into a tree. Here, we first have the base case as a pattern. If we’ve reached an empty subtree, that means we’re where we want to go, and we insert a singleton tree with our element. If we’re not inserting into an empty tree, then we need to do some checking. First, if the element we’re inserting is equal to the root element, we just return a tree that’s the same. If it’s smaller, we return a tree that has the same root value and the same right subtree, but instead of its left subtree, we put a tree that has our value inserted into it. We do the same if our value is bigger than the root element, but the other way around.
Next up, we’re going to make a function that checks if some element is in the tree:
treeElem :: (Ord a) => a -> Tree