Data-Structural Bootstrapping

Prev: Numerical Representations Next: Implicit Recursive Slowdown

Prev: Numerical Representations Next: Implicit Recursive Slowdown

10.1 Structural Decomposition

10.1.2 Binary Random-Access Lists Revisited

Exercise 10.1

Prove that this version of update runs in $O({\log }^{2}n)$ time.

Exercise 10.2

Reimplement AltBinaryRandomAccessList so that cons, head, and tail all run in $O(1)$ amortized time, using the type:

datatype a RList =
    NIL
  | ONE of a * (a * a) RList susp
  | TWO of a * a * (a * a) RList susp
  | THREE of a * a * a * (a * a) RList susp

10.1.3 Bootstrapped Queues

Exercise 10.3

Consider the expression tail (snoc (q, x)). Show that the calls to tail and snoc will never both recursively call snoc.

Exercise 10.4

Implement these queues without polymorphic recursion using the types:

datatype a EL = ELEM of a | LIST of a EL list susp
datatype a Queue = E | Q of int * a EL list * a Queue * int * a EL list

Exercise 10.5

Another way to eliminate the need for polymorphic recursion is to represent the middle using some other implementation of queues. Then the type of bootstrapped queues is:

datatype a Queue =
    E | Q of int * a list * a list susp PrimQ.Queue * int * a list

1. Implement this variation of bootstrapped queues as a functor:

functor BootstrapQueue (PrimQ : QUEUE) : QUEUE

2. Prove that if PrimQ is instantiated to some implementation of real-time queues, then all operations on the resulting bootstrapped queues take $O(1)$ amortized time.

10.2 Structural Abstraction

10.2.1 Lists With Efficient Catenation

Exercise 10.6

Write a function flatten of type a Cat list -> a Cat that catenates all the elements in a list of catenable lists. Show that your function runs in $O(1+e)$ amortized time, where e is the number of empty catenable lists in the list.

10.2.2 Heaps With Efficient Merging

Exercise 10.7

Inlining the LazyBinomialHeap functor of Section 6.4.1 as described above yields the types:

datatype Tree = Node of int * Heap * Tree list
datatype Heap = E | NE of Elem.T * Tree list susp

Complete this implementation of bootstrapped heaps.

Exercise 10.8

Elements in a heap frequently contain other information besides the priority. For these kinds of elements, it is often more convenient to use heaps that separate the priority from the rest of the element.

1. Adapt either LazyBinomialHeap or SkewBinomialHeap to the alternate HEAPWITHINFO signature.
2. Rewrite the Bootstrap functor as functor Bootstrap (PrimH : HEAPWITHINFO) : HEAPWITHINFO = .... You will need neither higher-order functors nor recursive structures.

10.3 Bootstrapping To Aggregate Types

10.3.1 Tries

Exercise 10.9

Very often, the set of keys to be stored in a trie has the property that no key is a proper prefix of another. Reimplement tries under this assumption, using the type:

datatype a Map = Entry of a | TRIE of a Map M.Map

Exercise 10.10

Tries frequently contain long paths of nodes that each have only a single child. A common optimization is to collapse such paths into a single node. Reimplement tries using the type:

datatype a Map = TRIE of M.Key list * a option * a Map M.Map

Maintain the invariant that no node is both invalid and an only child. You may assume that the structure M provides an isEmpty function.

Exercise 10.11

Complete the following implementation of abstract hash tables:

functor HashTable (structure Approx : FINITEMAP
                   structure Exact : FINITEMAP
                   val hash : Exact.Key -> Approx.Key) : FINITEMAP =
struct
  type Key = Exact.Key
  type a Map = a Exact.Map Approx.Map
 
  fun lookup (k, m) = Exact.lookup (k, Approx.lookup (hash k, m))
end

The advantage of this representation is that Approx can use an efficient key type, such as integers, and Exact can use a trivial implementation, such as association lists.

10.3.2 Generalized Tries

Exercise 10.12

Reimplement the TrieOfTrees functor without polymorphic recursion using the types:

datatype a Map = TRIE of a EM option * a Map M.Map
and a EM = ELEM of a | MAP of a Map

Exercise 10.13

Implement tries whose keys are multiway trees of type:

datatype a Tree = T of a * a Tree list

Exercise 10.14

Complete the following functors that implement the product-map and sum-map rules.

functor ProductMap (M1 : FINITEMAP) (M2 : FINITEMAP) : FINITEMAP =
struct
  type Key = M1.Key * M2.Key
end
 
datatype (a, b) Sum = LEFT of a | RIGHT of b
 
functor SumMap (M1 : FINITEMAP) (M2 : FINITEMAP) : FINITEMAP =
struct
  type Key = (M1.Key, M2.Key) Sum
end

Exercise 10.15

Given a structure M that implements finite maps over the type Id of identifiers, implement tries over the type Exp of lambda expressions, where:

datatype Exp = VAR of Id | LAM of Id * Exp | APP of Exp * Exp

You may find it helpful to extend the type of tries with a separate constructor for the empty map.

10.4 Chapter Notes