Homework 6 (100 points)

Download the skeleton files Deque.elm and ThunkList.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: Deques

6.1.1 --- Okasaki, Exercise 5.1a (50 points)

A double-ended queue, or deque (pronounced "deck"), allows adding and removing elements from both ends of the data structure. In this problem, you will adapt the FastQueue strategy from Chapter 5 to implement the Deque abstraction. In particular, use the representation

type Deque a = D { front : List a, back : List a }

and maintain the invariant that front and back are both non-empty whenever there are at least two elements in the Deque.

Implement the following three operations (which we referred to in the Queue context as enqueue, dequeue, and peek, respectively):

addBack     : a -> Deque a -> Deque a
removeFront : Deque a -> Maybe (Deque a)
peekFront   : Deque a -> Maybe a

In addition, implement the following three analogous operators:

addFront    : a -> Deque a -> Deque a
removeBack  : Deque a -> Maybe (Deque a)
peekBack    : Deque a -> Maybe a

Implement and use a helper function

check : List a -> List a -> Deque a

that enforces the invariant by checking whether either list is empty and, if so, splitting the other in half and reversing one of the halves.

All operations should run in O(1) amortized time assuming, as in Chapter 5, that values are not used persistently (but you are not asked to prove it).

Hint: The frontmost and backmost element of a Deque may be the same.

Problem 2: Lazy Lists

In this problem, you will implement ThunkList analogues of a couple more standard List functions. Like in class, we will simply use thunks without memoizing their results.

6.2.1 (50 points)

First, implement the following functions.

append : ThunkList a -> ThunkList a -> ThunkList a
map    : (a -> b) -> ThunkList a -> ThunkList b
concat : ThunkList (ThunkList a) -> ThunkList a

Your implementations should be incremental. They should return immediately, without forcing any elements from input lists.

Next, use map and concat to define the following.

concatMap : (a -> ThunkList b) -> ThunkList a -> ThunkList b

Finally, implement the following function that computes the Cartesian product of two ThunkLists and transforms each its pairs using the input function.

cartProdWith : (a -> b -> c) -> ThunkList a -> ThunkList b -> ThunkList c

Grading and Submission Instructions

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 hw6
% cd hw6
% wget http://www.classes.cs.uchicago.edu/archive/2020/spring/22300-1/assignments/hw6/ThunkList.elm
% wget http://www.classes.cs.uchicago.edu/archive/2020/spring/22300-1/assignments/hw6/Deque.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 ThunkList.elm
% svn add Deque.elm

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

% svn commit -m "hw6 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:

https://phoenixforge.cs.uchicago.edu/projects/USER-cs223-spr-20/repository