Okasaki's PFDS, Chapter 2
This post contains my solutions to the exercises in chapter 2 of Okasaki’s ‘Purely Functional Data Structures’. The latest source code can be found in my GitHub repo.
Write a function
suffixes of type
suffixes :: [a] -> [[a]]
that takes a list
xs and returns a list of all the suffixes of
xs in decreasing order of length. For example,
suffixes [1, 2, 3, 4] == [[1, 2, 3, 4], [2, 3, 4], [3, 4], , ]
Show that the resulting list of suffixes can be generated in \(\mathcal O (n)\) time and represented in \(\mathcal O (n)\) space.
Since there are as many recursive calls to
suffixes as there are elements of
xs, and both
tail run in constant time,
suffixes must be linear in the length of the list
xs. That is, the solution to the recursion \(T (n) = T(n-1) + \mathcal O (1)\) is \(T (n) = \mathcal O (n)\).
Moreover, we use the \(n\) lists that already exist and also \(\mathcal O (n)\) new pointers to each of those lists. Therefore,
suffixes xs is represented in \(\mathcal O (n)\) space.
Binary Search Trees (BSTs)
We start with binary trees (not search trees yet!). A binary tree is either empty or has two children, which we call ‘left’ and ‘right’.
data Tree a = E | T (Tree a) a (Tree a) deriving (Show, Eq)
In the binary trees below, empty nodes are depicted as squares.
A BST is a binary tree with some extra structure. In particular, we require that the key of a node be greater than that of any of its left descendants and smaller than that of any of its right descendants.
In the following exercises, we implement BSTs in the context of sets.
member to take no more than \(d+1\) comparisons.
insert using exceptions to avoid copying the entire search path (in the case of inserting an existing element).
We use the
Maybe data structure for our errors, i.e.
Nothing indicates an error.
Write a function
complete :: a -> Int -> UnbalancedSet a
complete a dis a complete binary tree of depth d with the key
aat every node. This function should run in \(\mathcal O (d)\) time.
completeto create balanced trees of arbitrary size that runs in \(\mathcal O (n)\) time, where \(n\) is the number of nodes. A tree is said to be balanced if the size of any node’s left child differs by at most one from the size of that node’s right child.
The recursion is given by \(T(d) = T(d-1) + \mathcal O (1)\), which is solved by \(T (d) = \mathcal O (d)\).
The complexity of
balance is equal to that of
create2. The recursion for
create2 is given by \(T (n) = T (n/2) + \mathcal O (1)\), which is solved by \(T (n) = \mathcal O (\log n)\).
UnbalancedSet functor to support finite maps rather than sets. The signature for finite maps is as follows.
class FiniteMap m k a where empty :: m k a bind :: k -> a -> m k a -> m k a lookup :: k -> m k a -> Maybe a
We reuse the set implementation for
UnbalancedSet by creating the
Binding data type with the appropriate ordering. Note that this doesn’t allow updating key-value pairs.