4 Programming in Curry

4.3 Trees

We discuss two common variants of trees and show some typical functions of each variant.

4.3.1 Binary Search Trees

A binary tree is either of the following: a singleton value called empty (also null or leaf) or a pair, called a branch, consisting of two binary trees called the left and the right child. Most often, a branch is a triple rather than a pair which in addition to the children also stores a value of some generic set. This value is called the root or decoration of the tree.

A (decorated) binary tree is declared in Curry as:

⬇
data BinTree a = Leaf | Branch a (BinTree a) (BinTree a)

where BinTree is a type constructor and a is its parameter and stands for the type of the decorations. A popular variant of binary trees is called a binary search tree. The set of decorations is totally ordered and the decoration of a non-empty binary search tree is greater than all the decorations in the left child and smaller than all the decorations in the right child. This condition prevents repeated decorations in a binary search tree. The following function inserts a value in a binary search tree in such a way that the result is again a binary search tree [Browse Program][Download Program]:

⬇
insert x Leaf = Branch x Leaf Leaf
insert x (Branch d l r)
  | x < d = Branch d (insert x l) r
  | x > d = Branch d l (insert x  r)
  | otherwise = Branch d l r

An in-order traversal of any binary search tree produces the sorted list of the decorations of the tree.

⬇
inorder Leaf = []
inorder (Branch d l r) = inorder l ++ [d] ++ inorder r
Exercise 11

Sort a list without repeated values by constructing a binary search tree from the list and then traversing the tree [Browse Answer][Download Answer].

4.3.2 Trie Trees

An ordered tree is a pair in which the first component is an element of a set, called the set of decorations, and the second component is a sequence of ordered trees.

An ordered tree is declared in Curry as:

⬇
data Tree a = Tree a [Tree a]

where a is a parameter that stands for the type of the decorations and the identifier “Tree” is overloaded to denote both a type constructor (1st and 3rd occurrences) and a data constructor (2nd occurrence).

A trie is a tree that stores a mapping from keys, typically strings, to values and is characterized by sharing key prefixes. We present a simple variant where only keys are stored. This variant is useful to efficiently represent a dictionary and tell whether a string is in the dictionary.

We declare the type of a trie as follows:

⬇
type Trie = [Tree Char]

The following function inserts a string in a trie sharing whatever prefix of the string might already be present in the trie. The distinguished symbol that terminates a string is a period. [Browse Program][Download Program]

⬇
insert :: String -> Trie -> Trie
insert []     t  = (Tree ’.’ [] : t)
insert (w:ws) [] = [Tree w (insert ws [])]
insert (w:ws) (Tree c cs : ts)
  | ord w < ord c = insert (w:ws) [] ++ (Tree c cs : ts)
  | ord w > ord c = Tree c cs : insert (w:ws) ts
  | otherwise     = Tree c (insert ws cs) : ts
Exercise 12

Code functions to build a trie from a list of words and to print all the words in the trie [Browse Answer][Download Answer].

Exercise 13

Code a function that takes a word and a trie and tells whether or not the word is in the trie [Browse Answer][Download Answer].