Persistence

Prev: Introduction Next: Some Familiar Data Structures in a Functional Setting

Prev: Introduction Next: Some Familiar Data Structures in a Functional Setting

2.1 Lists

Exercises

Exercise 2.1

Write a function suffixes of type a list -> a list list that takes a list xs and returns a list of all the suffixes of xs in decreasing order of length.

suffixes [1,2,3,4] = [[1,2,3,4], [2,3,4], [3,4], [4], []]

Show that the resulting list of suffixes can be generated in $O(n)$ time and represented in $O(n)$ space.

2.2 Binary Search Trees

Exercises

Exercise 2.2

In the worst case, member performs approximately $2d$ comparisons, where $d$ is the depth of the tree. Rewrite member to take no more than $d+1$ comparisons by keeping track of a candidate element that might be equal to the query element, for example the last element for which < returned false or > returned true, and checking for equality only when you hit the bottom of the tree.

Exercise 2.3

Inserting an existing element into a binary search tree copies the entire search path even though the copied nodes are indistinguishable from the originals. Rewrite insert using exceptions to avoid this copying. Establish only one handler per insertion rather than one handler per iteration.

Exercise 2.4

Combine the ideas of the previous two exercises to obtain a version of insert that performs no unnecessary copying and uses no more than $d+1$ comparisons.

Exercise 2.5

Sharing can also be useful within a single object, not just between objects. For example, if the two subtrees of a given node are identical, then they can be represented by the same tree.

1. Using this idea, write a function complete of type Elem x int -> Tree where complete (x, d) creates a complete binary tree of depth d with x stored in every node. This function should run in $O(d)$ time.
2. Extend this function to create balanced trees of arbitrary size. These trees will not always be complete binary trees, but should be as balanced as possible: for any given node, the two subtrees should differ in size by at most one. This function should run in $O(\log n)$ time.

Hint: use a helper function create2 that, given a size m, creates a pair of trees, one of size m and one of size m + 1.

Exercise 2.6

Adapt the UnbalancedSet functor to support finite maps rather than sets. Figure 2.10 gives a minimal signature for finite maps.

Note that the NOTFOUND exception is not predefined in Standard ML, so you will have to define it yourself. Although this exception could be made part of the FINITEMAP signature, with every implementation defining its own NOTFOUND exception, it is convenient for all finite maps to use the same exception.

2.3 Chapter Notes