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 Trees, 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 Trees to render, with updates every time the user clicks a mouse button (see the Mouse library).

You are free to produce Trees 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 Trees:

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.

Grading and Submission Instructions

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

Submitting Your Code

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 add DrawTrees.elm
% svn add ThumbTree.EXT

Make sure you choose the same exact names for directories and files that you create. Once you are ready to submit:

% svn commit -m "hw2 submission"

You can resubmit as many times as you wish, and we will grade the most recent versions submitted. Late days, if any, will be computed based on your submission times.

As a sanity check, you can visit the Web-based frontend for your repository to make sure that you have submitted your files as intended: