The expressiveness of Haskell – Trees.

A simple recursive data declaration is enough to define a tree.

This simply states that a Tree of ‘a’s is either Empty or (‘|’) it has a Node that has an ‘a’ and two other trees, a left subtree and a right subtree.
The code to add an item to a tree is equally simple and recursive.

The function signature

states that ‘add’ takes a Tree of ‘a’, a value to add and returns a Tree of ‘a’. The only restriction on ‘a’ being that it must be of type ‘Ord’ meaning two ‘a’s can be compared to determine that larger one.

Line 2 of the add function shows that adding an item to an Empty tree is just a matter of creating a Node with the item along with two Empty subtrees.

When adding an item in the more general case then if the item is less than the entry in the current Node then the item is added, recursively, to the left subtree otherwise it is recursively added to the right subtree.

Done!

Leave a Reply

Your email address will not be published. Required fields are marked *

ˆ Back To Top