Lab 22: More Random-Access List Operations

Intro

You’ll work in this lab with ad-hoc partners.

The two of you will work as a team to solve problems. At any time, one of you will be the Head and the other will be the Hands. The Head does the thinking and the Hands does the typing. Hands type only what the Head tells them to, but you’re free to discuss any issues that pop up. You should switch off during the lab to make sure each of you get practice problem solving, dealing with syntax, and getting finger exercises on the keyboard.

You should start this lab with this project skeleton.

Recall

We’ve now seen how to build a list that combines the best of (sequential) lists and random-access arrays: random access lists.

In this lab, you’ll implement more list operations for random-access lists.

Implement rest for random-access lists

We ran out of time to implement rest, which optionally produces the rest of the list. Remember that the rest of the list must maintain the random-access list invariants.

Here is the high-level idea of how rest works: If the list of nodes is empty, there is no rest. If the list of nodes is non-empty, you want to drop the value of that node, but keep the left and right subtrees (unless they are leaves!). If the subtrees are nodes, cons both the left and right subtrees on to the list of nodes.

Convince yourself this maintains the invariants and test your rest method.

Implement foldr for random-access lists

Add the foldr signature to your random-access list interface and implement it.

Implement map for random-access lists

Add the map signature to your random-access list interface and implement it.

You could implement map in terms of foldr. Is there any benefit to not doing it this way?

Implement more operations for random-access lists

Try to add the following, do as many as you can:

• zip

• iterator

• rev

• app

Submission

Submit a zip file of your work at the end of lab.