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.
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
- Write a function to create a leaf (tree of
- Write a function to construct a new tree
from a label and two other trees.
- Write a conversion function from the type
'a bin_tree to an array.
- Define an infix traversal function for these
- Use it to display the tree.
- 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
- 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
- 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.
- 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.
- 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.
- 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 NumbersWe would like now to construct the infinite set of prime numbers
(without calculating it completely) using lazy data structures.
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
- Given an initial list of prime numbers, write the function
next that returns the smallest number not
on the list.
- 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.