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],[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.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.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.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