Join  Lists
1 Rules and Support Code
2 Instructions
3 Analysis
4 Template Files
5 Handing In


Lists, as you’ve seen them until now, permit only sequential access. You can’t get to the third element until you’ve been through the first two. This means that when you recur, you do so on a list that is only one element smaller.

For some computations, this is particularly problematic if you’re working on a multi-processor, such as a machine with many cores. Even with just two processors, the amount of work the two would do will be very imbalanced because one is processing a single element while the other is processing the entire rest of the list. It would be much better if we could split the list roughly in half, and thus (in some cases) reduce the overall processing time by half. That requires a different kind of list data structure, which is what we’re going to explore.

  • Every individual student must turn in their own separate sweep.

  • Each pair turns in a single final submission.

When working with partners, you should follow the collaboration policy.

1 Rules and Support Code

Our new data structure, the join list, is defined as follows:

data JoinList:

  | empty-join-list

  | one(elt)

  | join-list(list1 :: JoinList, list2 :: JoinList, length :: Number)


A join list is thus really a tree. Often, the two sub-lists (which are really sub-trees) will be of the same size; however, the definition does not require that they be. Indeed, because it is not, constructing a join list is easy; all balancing can be done internally by the system, based on various characteristics (such as the load on the system, number of available processors, etc.).

That said, though a join list is represented as a tree, it’s still a list in nature. That means it’s an ordered data structure, and the order and must be preserved by operations. Similarly, it can contain duplicates, and these must not be discarded.

Note that you can assume that all join-lists of size 0 will be represented by empty-join-list, and all join-lists of size 1 will be represented by one(elt). We will not test your code on any join-lists like:

join-list(empty-join-list, empty-join-list, 0)

join-list(empty-join-list, join-list(empty-join-list, empty-join-list, 0), 0)

join-list(empty-join-list, one(5), 1)

join-list(one(5), empty-join-list, 1)

Due to the nature of the assignment, you are limited to using only the following functions from the support code:

Here are two things you should not do:
  • Use the fields of the join-list variant of JoinList. You should only access the list contents via split. This is meant to emulate what would happen in a truly parallel implementation: the list may be “rebalanced” by split, which would be lost if you access the fields directly. For example, any uses of cases should look something like:

    cases(JoinList) jl:

        | empty-join-list => …

        | one(elt) => …

        | join-list(_, _, _) => split(...)


  • It may be tempting to write j-first and j-rest, then implement the other functions with j-first and j-rest as you would for normal Pyret lists. Don’t do this. The functions you write for should take advantage of the unique structure of join lists. It may be necessary to use j-first and j-rest in some situations, but you should use split instead wherever possible.

If you are unsure what you may or may not do or use, please ask.

While we are not grading on the efficiency of your code per-se, if your implementation is extremely inefficient, that is probably a sign that you are not using the structure of join lists properly, and you might want to rethink your implementation.

2 Instructions

Implement the following functions. Some of them require non-empty join lists. This is specified in the type signature as JoinList%(is-non-empty-jl)).

3 Analysis

What should the value of

j-reduce(lam(x,y): x - y end, list-to-join-list([list: 1, 2, 3]))

be? Hint: There is more than one possible answer. List all.

Unfortunately, having more than one answer violates the expectation that j-reduce is a function. The problem is not with j-reduce but with the use of - (minus) as an argument. What property should the first argument to j-reduce demonstrate? Can you argue this from the description of j-reduce above?

4 Template Files

This assignment requires you to implement many different functions. In your sweep we suggest you test some of the higher-level functionality such as j-map, j-filter, j-sort, and j-reduce.

Initial Tests (JoinLists)

Implementation (JoinLists)

Final Tests (JoinLists)

5 Handing In

Remember that this assignment requires you to hand in sweeps.

To submit, return to the Captain Teach assignments page:

and click “Next Step” again. Upload a zip file containing both your implementation, named join-lists.arr, and your tests. At the next step, please upload your analysis.

Note that you will submit twice from Captain Teach—once for JoinLists and once for MapReduce.