Previous Contents Next


Binary Trees

We represent binary trees in the form of vectors. If a tree a has height h, then the length of the vector will be 2(h+1)-1. If a node has position i, then the left subtree of this node lies in the interval of indices [i+1 , i+1+2h], and its right subtree lies in the interval [i+1+2h+1 , 2(h+1)-1]. This representation is useful when the tree is almost completely filled. The type 'a of labels for nodes in the tree is assumed to contain a special value indicating that the node does not exist. Thus, we represent labeled trees by the by vectors of type 'a array.

  1. Write a function , taking as input a binary tree of type 'a bin_tree (defined on page ??) and an array (which one assumes to be large enough). The function stores the labels contained in the tree in the array, located according to the discipline described above.

  2. Write a function to create a leaf (tree of height 0).

  3. Write a function to construct a new tree from a label and two other trees.

  4. Write a conversion function from the type 'a bin_tree to an array.

  5. Define an infix traversal function for these trees.

  6. Use it to display the tree.

  7. What can you say about prefix traversal of these trees?

Spelling Corrector

The exercise uses the lexical tree , from the exercise of chapter 2, page ??, to build a spelling corrector.

  1. Construct a dictionary from a file in ASCII in which each line contains one word. For this, one will write a function which takes a file name as argument and returns the corresponding dictionary.

  2. Write a function words that takes a character string and constructs the list of words in this string. The word separators are space, tab, apostrophe, and quotation marks.

  3. Write a function verify that takes a dictionary and a list of words, and returns the list of words that do not occur in the dictionary.

  4. Write a function occurrences that takes a list of words and returns a list of pairs associating each word with the number of its occurrences.

  5. Write a function spellcheck that takes a dictionary and the name of a file containing the text to analyze. It should return the list of incorrect words, together with their number of occurrences.

Set of Prime Numbers

We would like now to construct the infinite set of prime numbers (without calculating it completely) using lazy data structures.

  1. Define the predicate divisible which takes an integer and an initial list of prime numbers, and determines whether the number is divisible by one of the integers on the list.

  2. Given an initial list of prime numbers, write the function next that returns the smallest number not on the list.

  3. Define the value setprime representing the set of prime numbers, in the style of the type 'a enum on page ??. It will be useful for this set to retain the integers already found to be prime.

Previous Contents Next