In this lecture, we study the basic obstructions required to implement data parallel operations in a generic fashion. Some of these obstructions such as iterators, you may have already heard about. Others such as splitters, builders and combiners we will study in this lecture. Each iterable collection can create its own iterator object. In Scala every iterator comes with two methods, next and hasNext. The iterator maintains some internal state that describes what the current element is. Calling next moves the iterator to the next element and returns it, while calling has next Returns true only if there are more elements to traverse. The iterator contract states that next can only be called if hasNext returns true. That means that users of the iterator should almost always call hasNext before pulling out the element with next. Here's an exercise. Try to extend the iterator trait with the foldLeft method. This foldLeft method should be an operation on the iterator trait, not the collection. Take some time to implement this method. Let's see the solution. Here is one possible implementation. In the first line, we declare a local variable and initialize it with a neutral element for foldLeft. Then, as long as hasNext returns to, we call next to pull out an element, apply the function f to the accumulation, and assign the result back to s. When the while loop ends, the method returns the accumulation s. Although this example is simple, you can surmise that iterators can be used to implement many other methods in a straightforward way. Splitter is a counterpart of iterator used for parallel programming. The splitter trait is an extension of the iterator trait. The snippet shows its simplified form. It has the method split, which returns a sequence of splitters that reverse the subsets of the current splitter. It also comes with a remaining method, which returns an estimate on the number of remaining elements. Every parallel collection has it's own splitter implementation and must define a method splitter which returns it's own splitter object. The splitter contract states several things. First, after calling split, the splitter is left in a undefined state methods like next, hasNext, or split cannot be called again on the splitter. Then the resulting splitters traverse disjoint sets of the original splitter. For example, if the splitter contains elements a, b, c, d, and e, then the resulting splitters could, for example, traverse elements a, b, and c. And elements d and e. Normally the split method should return at least two splitters. Importantly, the split method must execute in logarithmic time or better. The idea is the split must be invoked multiple times during the execution of the parallel operation, so it must be efficient. Now, take some time and think about how you could use splitters to implement the method fold that we talked about in the previous lecture. Let's see one possible implementation. The idea will be to create a reduction tree. And then the number of elements drops below a certain threshold, revert to the sequential case. In the first line, we use the splitters method remaining to get an estimate on the number of elements. If this number is below some threshold, we call the alternative sequential old left method. Otherwise, we branch the parallel reduction tree by calling split and spawning the task for each of the child splitters. Each of these tasks recursively calls fold and parallel. The tasks are then joined and then we have a collection with their values we call foldLeft to merge those values. From the previous weeks we know that we can optimize this method further by for example invoking fold on one of the children sequentially. However, this solution returns correct values. Builders are abstractions used for creating new collections, roughly speaking the builder trait is as follows. It has two tight parameters a in repr, where a is the type of the elements that we can add the builder and repr denotes the type of the collection that the builder creates. It has a plus equals method used to add an element to the builder. And a result method that returns a collection. Each collection must implement the new builder method, which is used to build a new collection of the same type. For example, a list of integers would return a builder of type of builder of int and a list of int. The builder contract specifies that the result method must return a collection with all the elements that were previously added, using the += method. However, calling result leaves the Builder in an undefined state. After this, we cannot use it anymore. Here's another small task. Try to implement the filter operation on collections. You may use the foreach loop this time, and the newBuilder method. Here's one way to do this. We start by creating a newBuilder b. Then we traverse the elements of the current collection with a for each loop. For each element we check in the filtering element two and if it does we add the element to the builder using the += method. Finally we call the result method to get a new collection. Now that we saw what builders are. Let's take a look at their parallel counterparts. A combiner is a parallel version of a builder. We again show a simplified version of this trait. In addition to the builder method, combiners have a method combine. Which mergers two combiner objects together. Every parallel collection must implement the new combiner method which creates a new combiner object specific to that collection. The combine method must return a new combiner such that it contains the elements of both input combiners. For example, if we have two combiners with elements x, y, z and elements u, v, w. After we call combine, we get a new combiner with elements x, y, z, u, v, and w. After combine is called, both input combiners are left in an undefined state and can no longer be used. Finally, combine must be an efficient method. Its running time must be logarithmic time or better. Here's some homework for you. Try to implement the filter method again but this time, make in run in parallel. You may use the splitter and new combiner methods
