In the previous lecture, we saw the basic form of data parallelism, namely the parallel for-loop. In this lecture, we'll study some other data-parallel operations. Scala collections can be converted to parallel collections by invoking the par method. Subsequent data parallel operations are then executed in parallel. In this example, we converted the range collection into a parallel range. We then filter the integers that they're divisible by 3 and count the number of palindromes among those integers. However, some collection operations are not parallelizable. Let's study this in more detail. Here is a task for you. Implement the parallel sum method, which returns the sum of the integers in the given array. In your implementation, you should use the method foldLeft. Let's see how to do this. The implementation is simple. It calls .par to create a parallel version of the array, and then invokes the foldLeft method with the initial value of the sum equal to zero. The operator used by foldLeft is set to addition. So, here's a question for you. Does this implementation run in parallel? The answer is no. Let's see why not. We examine the foldLeft signature more closely. The foldLeft method takes the type parameter B which is the type of the accumulation, a neutral element z of type B, and the function f that combines the accumulation and the elements of the collection into another accumulation. Method foldLeft says, give me a collection with n elements of that A, any number of neutral elements, and any number of instances of the function f. I will connect the elements of the collection together using the function f. In how many ways can fold left to do that? I argue that foldLeft can do this in only one way. To understand why, note that foldLeft's job is very similar to putting together Lego bricks. Let's establish an isomorphism between a functional programming and playing with Legos. LEGO®is a trademark of the LEGO Group of companies which does not sponsor, authorize or endorse this site. The signature of the function f is a lot like the following Lego brick.
It has two inputs and one output. LEGO®is a trademark of the LEGO Group of companies which does not sponsor, authorize or endorse this site. We will consider this 2 times 1 slot to correspond to the input type A. And this 1 times 1 slot to correspond to the input type B. Similarly, we will consider this 1 times 1 slot to correspond to the output type B. Next, what does the collection element type A correspond to? We decided that A corresponds to this 2 times 1 slope. So we can represent it with the following roof brick. Finally, the neutral element has type B, which has to be a 1 times 1 slot. In general, the collection can have any number of elements of type A. The goal of the foldLeft method is to connect all the elements of the collection using any number of instances of function f, so that at the end, there is only one output slot B of size 1 times 1. So let's start with the collection element of type A. The only brick we can connect with is the f brick, and at this position. That leaves the 1 times 1 input slot empty. The only element we can use here is the neutral element 1 times 1 brick, which has the type B. So we put it in. We similarly connect the remaining A bricks with their function f bricks. Now, it becomes obvious that the only way to connect these three parts together
is like this. There is no other way to connect these pieces. We now see that in order for the accumulation value B to become available at any position, it first must be computed for the previous elements. In other words, these functions must be invoked sequentially, one after another. Methods such as foldRight, reduceLeft, reduceRight, scanLeft, and scanRight also execute sequentially for the same reason. To enable folding the elements in parallel, we will have to introduce a new method called fold. This method will have a slightly different signature. Instead of having another type parameter for the accumulation type, like foldLeft did, the accumulation will have the same type as the elements in the collection. The folding function will have two input parameters of type A and return a result of type A. It can be represented with the following Lego brick. This brick will turn out to be so good that it is literally on fire. This time, we slightly inverted the input and output directions on the brick. These will be the inputs, and this will be the output. Collection elements will be represented with the following brick, which is this time, 1 times 1. This time there are many ways to connect the function invocations and collection elements together. We decide to connect two elements with one function, and the other two elements to another. Since the output of the function has exactly the same shape as its input, we can use the function again to connect these two parts together. This construct should be familiar to you. It resembles the reduction tree that we learned about in the previous weeks. The two invocations of the function f on the left and on the right can now be executed by separate processors. For this reason, the fold method can be implemented to execute in parallel. The fold operation is one of the basic abstractions. Many other data-parallel operations can be implemented in terms of fold. The next lecture, we will take a look at some of the use cases for fold, as well as some alternative operations.