# Lab 3 (110 points)

Download the skeleton file `ListsAndTrees.elm` and use it as a starting point for the following problems. Look for all occurrences of `TODO` in comments, which point out where you should implement your solutions. Once you are done, follow the submission instructions below.

## Problem 1: Lists

#### 3.1.1 — Okasaki, Exercise 2.1 (10 points)

Implement the function

``suffixes : List a -> List (List a)``

so that it returns a list of all suffixes of the input in decreasing order of length. Then, in comments, argue why your implementation runs in O(n) time and can be represented in O(n) space.

Once you have implemented the function, you should get the following behavior at the Elm REPL:

``````> import ListsAndTrees exposing (..)

> suffixes (List.range 1 4)
[[1,2,3,4],[2,3,4],[3,4],,[]] : List (List number)``````

## Problem 2: Binary Trees

In this problem, you will define several functions that operate on binary trees of integers represented by the type:

``type Tree a = Empty | Node a (Tree a) (Tree a)``

#### 3.2.1 — Okasaki, Exercise 2.2 (20 points)

Write a function

``mem : comparable -> Tree comparable -> Bool``

such that `mem x t` determines whether `x` is contained in the binary search tree `t`, using at most h+1 comparisons where h is the height of `t`. Each of the following functions constitutes one comparison: `(==)`, `(/=)`, `(<=)`, `(<)`, `(>=)`, `(>)`.

#### 3.2.2 — Okasaki, Exercise 2.5a (10 points)

Write a function

``fullTree : a -> Int -> Tree a``

such that `fullTree x h` produces a completely full tree of height `h` where every node stores the element `x`. Your function should return the empty tree whenever `h` is less than or equal to zero. This function should run in O(`h`) time.

For example:

``````> fullTree 0 0
Empty : ListsAndTrees.Tree

> fullTree 0 1
Node 0 Empty Empty : ListsAndTrees.Tree

> fullTree 0 2
Node 0 (Node 0 Empty Empty) (Node 0 Empty Empty) : ListsAndTrees.Tree``````

#### 3.2.3 — Okasaki, Exercise 2.5b (20 points)

The size of a tree is the number of (non-empty) nodes it contains. We will say a tree t is size-balanced if for any given node n in t, the two subtrees of n differ in size by at most one.

Write a function

``balancedTree : a -> Int -> Tree a``

such that `balancedTree x n` returns some balanced tree of size `n`, where the element `x` is stored at all nodes. 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`.

#### 3.2.4 (20 points)

Write a function

``balancedTrees : a -> Int -> List (Tree a)``

such that `balancedTrees x n` returns all balanced trees of size `n`, where the element `x` is stored at all nodes.

The following is a sanity check:

``````> List.map (List.length << balancedTrees 0) (List.range 0 20)
[1,1,2,1,4,4,4,1,8,16,32,16,32,16,8,1,16,64,256,256,1024] : List Int``````

#### 3.2.5 (20 points)

A complete tree is typically defined to be a tree where every level except possibly the last is completely full and the nodes in the last level are as far left as possible.

Write a function

``completeTrees : a -> Int -> List (Tree a)``

such that `completeTrees x h` returns all complete trees of height `h` where `x` is stored at every node.

The following is a sanity check:

``````> List.map (List.length << completeTrees 0) (List.range 0 5)
[1,1,2,4,8,16] : List Int``````

One strategy for this problem is based on how breadth-first order can be used to index the nodes of a complete binary tree. For example:

``````    Level 1              1

Level 2        2           3

Level 3     4     5     6     7

. .   . .   . .   . .``````

Using this observation, you can implement `completeTrees` by computing a full tree of height `h-1` (think `fullTree`) and then adding “all valid rows for level `h`” to it (think `suffixes`). The key is to define a function that “adds” a row to the bottom level of an existing tree.

#### 3.2.6 (10 points)

We will say that a tree is almost complete if all levels except possibly the last are completely full; we impose no constraints on the last level of an almost complete tree.

Write a function

``almostCompleteTrees : a -> Int -> List (Tree a)``

such that `almostCompleteTrees x h` returns all almost complete trees of height `h` where `x` is stored at every node.

Think about how to refactor your solution to the previous problem so that much of it can be reused for this one. Hint: You can use `subsequences` in a similar way to how `suffixes` was used.

The following is a sanity check:

``````> List.map (List.length << almostCompleteTrees 0) (List.range 0 5)
[1,1,3,15,255,65535] : List Int``````

# Grading and Submission Instructions

Submit the following file:

• The file `ListsAndTrees.elm` updated with your changes. You are free to modify this file as you wish, as long as you do not change any type signatures that are provided.

Your solution will be graded using a combination of automated grading scripts and manual review. It is a good idea for you to design some test cases of your own to exercise more sample behaviors than just the ones provided in the writeup. We also reserve the right to take into account the organization and style of your code when assigning grades.

If you are not able to finish all parts of the assignment, make sure that all of your submitted files compile successfully. If not, you risk getting zero points for the assignment. In particular, for each file `Foo.elm`, make sure that it can be loaded into the Elm REPL

``````% elm-repl
> import Foo
>``````

and that it can be compiled to a standalone HTML file:

``````% elm-make Foo.elm --output=Foo.html
Successfully generated Foo.html``````