# Homework 2

Download the skeleton files `ListsAndTrees.elm` and `DrawTrees.elm` and use them 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

#### 2.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 [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 = Empty | Node Int Tree Tree``

#### 2.2.1 --- Okasaki, Exercise 2.2 (20 points)

Write a function

``mem : Int -> Tree -> 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: `(==)`, `(/=)`, `(<=)`, `(<)`, `(>=)`, `(>)`.

#### 2.2.2 --- Okasaki, Exercise 2.5a (10 points)

Write a function

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

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

#### 2.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 : Int -> Int -> Tree``

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

#### 2.2.4 (20 points)

Write a function

``balancedTrees : Int -> Int -> List Tree``

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) [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``````

#### 2.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 : Int -> Int -> List Tree``

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

#### 2.2.6 (10 points)

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

Write a function

``almostCompleteTrees : Int -> Int -> List Tree``

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) [0..5]
[1,1,3,15,255,65535] : List Int``````

## Problem 3: Drawing Trees

The goal of this problem is to continue learning how to render images using Elm. In particular, you will write an application that (a) generates an (infinite) signal of `Tree`s, and (b) renders each to the screen when the user clicks a mouse button. These two subproblems are described one after another, though you can tackle them in either order.

#### 2.3.1 (20 points)

Calling `Signal.sampleOn` `ticker sig` produces a signal whose values are just like `sig` except that it updates only when `ticker` does. In other words, `sig` is "sampled" whenever `ticker` changes.

First, define an analogous "sampling" function for lists. Implement

``sampleListOn : Signal b -> List a -> Signal a``

such that `sampleListOn ticker xs` creates a signal out of the values in `xs` that is updated whenever `ticker` changes.

Your solution should crash (with some of nasty JavaScript exception) if `xs` is empty. The resulting signal (assuming that `xs` is non-empty), should never run out of values. To achieve this, when reaching the end of `xs`, the signal should continue producing values starting all over again from the beginning of `xs`.

Next, define

``signalTree : Signal Tree``

in terms of `sampleListOn` such that it produces an infinite stream of `Tree`s to render, with updates every time the user clicks a mouse button (see the `Mouse` library).

You are free to produce `Tree`s however you wish. For example, you may choose to use `completeTrees` to cycle through all complete trees of a given height or `balancedTrees` for all balanced trees of a given size.

#### 2.3.1 (60 points)

Rendering a tree as an image is the crux of the matter at hand. Implement the function

``view : (Int,Int) -> Tree -> Element``

which takes a pair of integers `(w,h)` that describes the current width and height of the HTML window and a binary tree `t` to render.

You are free to draw the nodes and edges of the tree however you see fit. One option is to impose the shape of a complete binary tree on the given tree, leaving gaps for `Empty` nodes. With this approach, the breadth-first indexing scheme discussed earlier will come in rather handy.

Make sure to cozy up to the `Graphics.Element` and `Graphics.Collage` libraries as you devise your approach; they are your friends (and the only ones who can help)!

Once everything in place, you will be able to render your stream of `Tree`s:

``````main : Signal Element
main =
Signal.map2 view Window.dimensions signalTree``````

In the meantime, while developing your solution, you may find it helpful to define `main` in terms of `view` and a particular (constant) example tree, so that you can compile and view the HTML output of your program:

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

For reference, click here to see the output from a sample implementation.

#### 2.3.4 (20 points)

You will receive full points for the parts above as long as everything is working, no matter how pretty (or ugly) the results are. These last few remaining points are reserved for solutions that are particularly pleasing.

To help get the creative juices flowing, here are some possible ideas for making the animation prettier:

• Adjust the size of the drawing based on `Window.dimensons`.
• Add text buttons, dropdown menus, etc. to allow the user to tweak parameters of `signalTree` (e.g. the list-producing function to use, the height/size parameters).
• Drawing sparse trees more nicely, so that they don't take up as much room as complete trees. This article on Drawing Trees provides one approach.

In the coming weeks, we will generate a poll based on everyone's solutions to this problem. You may receive points for this problem based on the results of the voting. More details to follow.

Submit the following three files:

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

• A 200-by-200 pixel thumbnail image of your animation called `ThumbTree.EXT`, where `EXT` is a standard image format such as `png`, `jpg`, or `gif`. This thumbnail will be used to help generate a gallery on the forthcoming voting page, where each thumbnail will link to the corresponding animation. So you will want to choose an accurate and compelling preview of your animation to entice people to view it.

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

Start by navigating to the folder where you checked out your repo. Next, create a subfolder for this assignment and populate it with the skeleton code:

``````% svn mkdir hw2
% cd hw2
% wget http://www.classes.cs.uchicago.edu/current/assignments/hw2/ListsAndTrees.elm
% wget http://www.classes.cs.uchicago.edu/current/assignments/hw2/DrawTrees.elm``````

If `wget` or a similar tool (such as `curl`) is not available on your machine, download and save the skeleton files provided above in some other way. Then add only these files to your repo:

``````% svn add ListsAndTrees.elm
``% svn commit -m "hw2 submission"``
``https://phoenixforge.cs.uchicago.edu/projects/USER-cs223-win-16/repository``