• Choose a category
• All
• Classic-Fiction

treeElem x EmptyTree = False

treeElem x (Node a left right)

| x == a = True

| x < a = treeElem x left

| x > a = treeElem x right

First, we define the base case. If we’re looking for an element in an empty tree, then it’s certainly not there. Notice how this is the same as the base case when searching for elements in lists. If we’re not looking for an element in an empty tree, then we check some things. If the element in the root node is what we’re looking for, great! If it’s not, what then? Well, we can take advantage of knowing that all the left elements are smaller than the root node. If the element we’re looking for is smaller than the root node, we check to see if it’s in the left subtree. If it’s bigger, we check to see if it’s in the right subtree.

Now let’s have some fun with our trees! Instead of manually creating one (although we could), we’ll use a fold to build a tree from a list. Remember that pretty much everything that traverses a list one item at a time and returns a value can be implemented with a fold! We’re going to start with the empty tree and then approach a list from the right and insert element after element into our accumulator tree.

ghci> let nums = [8,6,4,1,7,3,5]

ghci> let numsTree = foldr treeInsert EmptyTree nums

ghci> numsTree

Node 5

(Node 3

(Node 1 EmptyTree EmptyTree)

(Node 4 EmptyTree EmptyTree)

)

(Node 7

(Node 6 EmptyTree EmptyTree)

(Node 8 EmptyTree EmptyTree)

)

Note

If you run this in GHCi, the result from numsTree will be printed in one long line. Here, it’s broken up into many lines; otherwise, it would run off the page!

In this foldr, treeInsert is the folding binary function (it takes a tree and a list element and produces a new tree), and EmptyTree is the starting accumulator. nums, of course, is the list we’re folding over.

When we print our tree to the console, it’s not very readable, but we can still make out its structure. We see that the root node is 5 and that it has two subtrees: one with a root node of 3 and the other with a root node of 7.

We can also check if certain values are contained in the tree, like this:

ghci> 8 `treeElem` numsTree

True

ghci> 100 `treeElem` numsTree

False

ghci> 1 `treeElem` numsTree

True

ghci> 10 `treeElem` numsTree

False

As you can see, algebraic data structures are a really cool and powerful concept in Haskell. We can use them to make anything from Boolean values and weekday enumerations to binary search trees, and more!

Type Classes 102

So far, you’ve learned about some of the standard Haskell type classes and seen which types they contain. You’ve also learned how to automatically make your own type instances of the standard type classes by asking Haskell to derive the instances. This section explains how to make your own type classes and how to make type instances of them by hand.

A quick type class recap: Type classes are sort of like interfaces. A type class defines some behavior (such as comparing for equality, comparing for ordering, and enumeration). Types that can behave in that way are made instances of that type class. The behavior of type classes is achieved by defining functions or just type declarations that we then implement. So when we say that a type is an instance of a type class, we mean that we can use the functions that the type class defines with that type.

Note

Remember that type classes have nothing to do with classes in languages like Java or Python. This confuses many people, so I want you to forget everything you know about classes in imperative languages right now!

Inside the Eq Type Class

As an example, let’s look at the Eq type class. Remember that Eq is for values that can be equated. It defines the functions == and /=. If we have the type Car and comparing two cars with the equality function == makes sense, then it makes sense for Car to be an instance of Eq.

This is how the Eq class is defined in the standard library:

class Eq a where

(==) :: a -> a -> Bool

(/=) :: a -> a -> Bool

x == y = not (x /= y)

x /= y = not (x == y)

Whoa! Some strange syntax