# 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.

## Exercise 2.1

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], [4], []]`

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

## Solution 2.1

Since there are as many recursive calls to `suffixes`

as there are elements of `xs`

, and both `:`

and `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.

## Exercise 2.2

Rewrite `member`

to take no more than \(d+1\) comparisons.

## Solution 2.2

See source.

## Exercise 2.3

Rewrite `insert`

using exceptions to avoid copying the entire search path (in the case of inserting an existing element).

## Solution 2.3

See source.

We use the `Maybe`

data structure for our errors, i.e. `Nothing`

indicates an error.

## Exercise 2.4

Combine the ideas of Exercise 2.2 and Exercise 2.3 to create an insert function that performs no unnecessary copying and uses no more than \(d+1\) comparisons.

## Solution 2.4

See source.

## Exercise 2.5

Write a function

`complete`

of type`complete :: a -> Int -> UnbalancedSet a`

such that

`complete a d`

is a complete binary tree of depth d with the key`a`

at every node. This function should run in \(\mathcal O (d)\) time.Extend

`complete`

to 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.

## Solution 2.5

See source.

**Item 1.**

The recursion is given by \(T(d) = T(d-1) + \mathcal O (1)\), which is solved by \(T (d) = \mathcal O (d)\).

**Item 2.**

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)\).

## Exercise 2.6

Adapt the `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
```

## Solution 2.6

See source.

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.