# Homework 5

Download the skeleton files `Deque.elm`, `LazyListPlus.elm`, and `EnumerateRB.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 `LazyList` analogues of a couple more standard `List` functions. You will need to download `LazyList.elm` and `elm-package.json` and place them in the directory where you are working.

#### 6.2.1 (50 points)

First, implement the following functions.

``````map    : (a -> b) -> LazyList a -> LazyList b
concat : LazyList (LazyList a) -> LazyList a``````

Your implementations should be as lazy as possible. In particular, for any `f` and `xs`, the expression `map f xs` should evaluate very quickly even if, for example, `head (map f xs)` does not.

Next, use `map` and `concat` to define the following.

``concatMap : (a -> LazyList b) -> LazyList a -> LazyList b``

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

``cartProdWith : (a -> b -> c) -> LazyList a -> LazyList b -> LazyList c``

## Problem 3 (OPTIONAL): Enumerating Red-Black Trees

In Homework 2, you defined functions that compute all trees of a certain height. In this problem, you will compute all valid red-black trees of a given black-height.

We will use the same representation for `RedBlackTrees` that store `Int`s from class:

``````type Color = R | B
type Tree  = E | T Color Tree Int Tree``````

#### 6.3.1 (0 points)

Write a function

``rbTrees : Int -> List Tree``

such that `rbTrees bh` returns all of the `Tree`s `t` (with the dummy data value `0` stored in each node) such that `check bh == True`, where `check` is defined as follows.

``````check bh t =
color t == B && noRedRed t && blackHeight t == Just bh``````

Notice that compared to the `rb` predicate from class, here we drop the `bso` requirement because we are only concerned with generating trees that satisfy the color and black-height invariants.

You may want to define the following helper function.

``cartProdWith : (a -> b -> c) -> List a -> List b -> List c``

As a sanity check:

``````> import EnumerateRB exposing (..)

> rbTrees 0
[E] : List EnumerateRB.Tree

> rbTrees 1
[T B E 0 E] : List EnumerateRB.Tree

> List.map (List.length << rbTrees) [0..3]
[1,1,4,400] : List Int

> List.map (\i -> List.all (check i) (rbTrees i)) [0..3]
[True,True,True,True] : List Bool``````

Bummer:

``````> rbTrees 4
FATAL ERROR: JS Allocation failed - process out of memory``````

#### 6.3.2 (0 points)

Since these `List`s get very large very quickly, define the following version that generates valid red-black trees lazily; you will want to use your `LazyListPlus` functions from the previous problem.

``rbTrees' : Int -> LazyList Tree``

Things should be a bit better when you're done:

``````> import LazyList exposing (..)

> rbTrees' 4
Lazy <function> : Lazy.Lazy (LazyList.LazyListCell EnumerateRB.Tree)

> rbTrees' 4 |> take 10 |> toList |> List.all (check 4)
True : Bool

> rbTrees' 4 |> take 1000 |> toList |> List.all (check 4)
True : Bool

> rbTrees' 5 |> take 1000 |> toList |> List.all (check 5)
True : Bool``````

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 hw5
% cd hw5
% wget http://www.classes.cs.uchicago.edu/current/22300-1/assignments/hw5/Deque.elm
% wget http://www.classes.cs.uchicago.edu/current/22300-1/assignments/hw5/LazyListPlus.elm
% wget http://www.classes.cs.uchicago.edu/current/22300-1/assignments/hw5/EnumerateRB.elm
% wget http://www.classes.cs.uchicago.edu/current/22300-1/assignments/hw5/elm-package.json
% wget http://www.classes.cs.uchicago.edu/current/22300-1/lectures/Laziness/LazyList.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 Deque.elm
``% svn commit -m "hw5 submission"``
``https://phoenixforge.cs.uchicago.edu/projects/USER-cs223-win-16/repository``