JoinLists
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 would 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.
1 Rules and Support Code
data JoinList<T>:
| empty-join-list
| one(elt :: T)
| join-list(list1 :: JoinList<T>,
list2 :: JoinList<T>,
length :: Number)
end
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 must be preserved by operations. Similarly, it can contain duplicates, and these must not be discarded.
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:
JoinList.join(other :: JoinList) -> JoinList
(What this notation means: The name JoinList is bound for you in the stencil, and join is a field of JoinList.)
Given another join list, it joins them to produce a new join list. If one or both of the join lists are empty-join-list, join will simply return the other list. Otherwise it will return a join list containing the second list appended to the first.
split(jlist :: JoinList(is-join-list), proc :: (JoinList, JoinList -> Any)) -> Any
This consumes a join list with two or more elements as the first argument. As the second argument, it takes a handler which consumes two JoinLists. First, split divides its first argument into a prefix and suffix which are non-empty JoinLists that will result in the original list if joined together. Then split invokes its second argument on this prefix and suffix and returns what that invocation returns. There is no guarantee that split will divide the list at the most recent join.
==
JoinList supports ==, which checks whether the two JoinLists have the same elements in the same order.
For purposes of testing you may use the functions
join-list-to-list(jlist :: JoinList) -> List and
list-to-join-list(lst :: List) -> JoinList
because otherwise your tests will be inconvenient to write. However, you may not use these—
or any functions other than those listed above— to implement the required functionality.
- 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(...)
end
Give in to the temptation 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.
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)).
j-first<A>(jl :: JoinList<A>%(is-non-empty-jl)) -> A
Returns the first element of a non-empty list.
j-rest<A>(jl :: JoinList<A>%(is-non-empty-jl)) -> JoinList<A>
Returns a join list containing all elements but the first of a non-empty list.
j-length<A>(jl :: JoinList<A>) -> Number
Returns the length of a join list.
j-nth<A>(jl :: JoinList<A>%(is-non-empty-jl), n :: Number) -> A
Returns the nth element (using a 0-based index) of a list containing at least n + 1 elements. For example, a second argument of 0 returns the first element of the join list.
j-max<A>(jl :: JoinList<A>%(is-non-empty-jl), cmp :: (A, A -> Boolean)) -> A
Returns the “maximum” value in a non-empty list. The second argument is a comparator that defines “maximum” for the type in the list: if the comparator returns true, the first argument to the comparator is “greater” than its second argument.
j-map<A,B>(map-fun :: (A -> B), jl :: JoinList<A>) -> JoinList<B>
Implements map for join lists.
j-filter<A>(filter-fun :: (A -> Boolean), jl :: JoinList<A>) -> JoinList<A>
Implements filter for join lists.
j-reduce<A>(reduce-func :: (A, A -> A), jl :: JoinList<A>%(is-non-empty-jl)) -> A
Distributes an operator across a non-empty list. That is, given the elements e1, e2, ..., en in order, and operator op, computes the equivalent of e1 op e2 op ... op en.
j-sort<A>(cmp-fun :: (A, A -> Boolean), jl :: JoinList<A>) -> JoinList<A>
Sorts a list in the order given by the second argument, the comparator. If the comparator returns true, then the first argument to the comparator should come before the second argument in the list produced.
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 - (subtraction) 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.
5 Handing In
Remember that this assignment requires you to hand in sweeps.
To submit, return to the Captain Teach assignments page:
https://www.captain-teach.org/brown-cs019/assignments/
and click “Next Step” again. First, save and upload a file containing your implementation, named join-lists.arr. In the next step, do the same for your tests. At the last step, please upload your analysis.
Note that you will submit twice from Captain Teach—