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

1 |
data Tree a = Empty | Node a (Tree a) (Tree a) |

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.

1 2 3 4 5 |
add :: (Ord a) => Tree a -> a -> Tree a add Empty x = Node x Empty Empty add (Node n left right) x | x <= n = Node n (add left x) right | otherwise = Node n left (add right x) |

The function signature

1 |
add :: (Ord a) => Tree a -> a -> Tree a |

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 Read More