Now we look at Operations that are often called Fold or Reduce. We have previously seen the map operation. Map applies a given function to every element of a collection. Say we have a List(1,3,8) recorded in map would produce List(1, 9, 64) when then mapping function is the squaring function. Now, what is an example of fold? If we take the same List(1,3,8) and if we fold it with the sum operation, which is just a binary operation that takes two values and produces their sum. With the starting element 100, then it will simply compute the result of doing a sum, starting from 100 of all the elements of the list, so the result will 100 plus, 1, plus 3, plus 8 or 112. The general property of fold really takes a binary operation as input, and possibly some additional parameters. Variants of fold differ in whether they take another initial element as a parameter, or instead assume a non-empty collection. Different variants of fold also differ in the order in which they combine the elements of a collection. If we again look at the list, foldLeft will combine these elements starting from the left. It also takes an initial element. If the list is 1, 3, 8, and the initial element is 100, then let's consider what happens when we applied the operation minus to this collection and this initial element. We'll compute the value of 100, the initial element, minus the first element. And the entire result minus this second element and so on until the end of the list. In this case the result is 88. In contrast, foldRight, takes also an initial element but combines the values starting from the end of the list. So you can think of 100 as replacing the empty list, at the very end of the list. And then we combine the last element of the list with 100. So the first thing we would compute would be 8-100 in this example. Then we take that result and we compute 3 minus that result, and so on. You can think of the original list as being 1, 3, 8, and then Nil, and what this has done is replaced the constructor for the least with minus and the Nil with a given element. So the result, in this case, is minus 94. You can see that the order of operations obviously differs between these two folds. We will here be mostly concerned with operation variant called reduce. Reduce does not take an additional element like foldLeft and foldRight did, instead it uses the element of a list itself as the starting point. So let's see what happens when we take list 1, 3, 8 and then do reduce left with minus. We take the elements of the list in the same order that they appeared in the input and then we put minus between them, grouping the operation from left to right. So in this case, the result is 1 minus 3 which is minus 2 and then minus 8, giving minus 10. In contrast, reduceRight while also preserving the order of elements of the list. It combines them by inserting parentheses towards the right. So the elements on the right side of the list will be combined first. And in this example, 3 minus 8 is minus 5, and then 1 minus minus 5 is plus 6. So again we see, that for reduce as well, the order matters when we have an operation such as minus. When we wish to process elements of a collection in parallel, we would like to have the freedom of choosing the order in which we process elements. Not only would we like to be able to process it from left to right, but also by choosing the order in some more complex ways. For this to be correct, we will ask for our operation to be associative. Examples of associative operations include addition or concatenation of strings, but not the minus that we have given here as an example. In general, an associative operation takes two elements of some type. Let's say A, and returns an element of the same type. And it needs to satisfy the following property. For every x, y, and z. Combining first y and z. And then combining x with that result, is the same as combining x and y first. And then, combining that with z. It is sometimes easier and more conventional to write the associativity law if we write f of ab as a with some operator b. Then the law becomes the following. This law tells us that when we look at three elements that appear in sequence just two different orders of combining these elements result in the same value. But if we know that, then we have the following consequence. If we have arbitrary expressions that have the same list of operands that are connected with our associated operation, but may have arbitrarily different parenthesis indicated in the order in which the operation should be done. Then these expressions evaluate to the same result. So we need to preserve the ordering of elements, not only just their number and we can change where the parenthesis are. So use an example that shows three different expressions containing x, y, zed w in that order. If the operation is associative then all these three expressions evaluate to the same value. Each expression built from some values that are combined using our associative operator, can be represented as a tree. In this tree, leaves represent our values, like x, y, and z. An the nodes of the tree represent the application of the operation. The shape of the tree then encodes where the parenthesis were. In our original expression, for example, the parenthesis that y and z should be combined first, and that's why we have a sub-tree that applies this operation to y and z. Similarly, in this example connecting x, y, z, and w. We see that x should be combined with y first and z should be combined with w. And that's why we have the following structure of the tree. How would we compute the value of such an expression tree? We can represent these expression using the following case classes. We have the abstract class trees then we have the leaves that stores values and we have nodes. Which have only the left and right sub tree. And we would like to compute the value of sector three with a given operation. And following the order of operations indicated by the structure of the tree. Let's first look at the sequential definition of such reduce of a tree. We take Tree as an input. Then we pattern match on the structure of the Tree. If the Tree is Leaf, then we determine the value. If it's a Tree containing left and right sub trees then we recursively reduce the left tree and the right tree, this gives us one value for each sub tree. Then we combine these two values using the given operation f. The simple recursant definition can be thought of as taking a tree and replacing all leaves with the values that they store and replacing all nodes with the operation f that was passed into the function. Now we can take an example and run reduce on our example tree this tree has 3 and 8 combined into 1 node, and then 1 is combined with them. It has the following tree and reduce will put the given operation f into the nodes of the tree. In this case, we take subtraction is the operation which is known not associative. But if we have a tree, then the result is uniquely given. And you can see that the result will be 3 minus 8, which is minus 5 and then 1 minus that. So if we have minus here, then this subtree will evaluate to minus 5, then our result will be 6. Now, how would we do a reduce of a tree in parallel? This is again, a case where parallel is very easy to add, once we have the right structure of our function. All we need to do is compute the reduce of left and right subtree in parallel to obtain two values left value and right value. And then we apply operation f to these two values. What is the depth complexity of such reduce operation? It's just the height of the tree, it's linear in the height of the tree. What is associativity law correspond to when we represent our expressions as trees? It represents that this tree that is more shifted to the right, gives the same result as this other tree. You can see that in these two trees, the order of operations is preserved. But the next thing is slightly different. Given the definition of reduce on trees, we can write this equality as follows. We create one tree containing three elements, x y and z. Corresponding to the picture on the left. And we create another tree with these elements corresponding to the picture on the right. Then if we apply reduce to these two trees with operation f that is associated with the result is the same. Okay, so this is a restatement of associativity law as equality of reduce on two trees of size three. When we speak of the order of elements in a tree, we can describe it by converting tree into a list. In case of a Leaf, it returns single element List. Otherwise, it recursively converts the left and the right sub-tree to a list and concatenates these toLists or appends one list to the other. We have previously seen a tree map which takes a tree and a function, and replaces all elements by applying the function to them. So for Leaf, it would just compute Leaf of f of that value that was there. And for Node, it would recursively apply map to both subtrees. Now that we have seen reduce, can you express toList as a combination of the map, and reduce. Here's the compact way to state it. It turns out the toList on a tree is equal to first mapping all the leaves of the tree to singleton list. And then reducing the resulting Tree with the associative operation of appending lists. Now that we have the notion of order of elements in a tree given by the tool list function, we can state somewhat more precisely the consequence of associativity. This consequence says that if you consider two expressions that have the same list of operands connected with our operator, but possibly different parentheses. Then these expressions evaluate to the same result when the operation is associated. Can you express this consequence using a scalar expression or a conditional expression using the functions that we have seen so far? Here's the restatement. If the function f is associative, and we have two trees t1 and t2 map to the same list of elements. Then the result of doing reduce on both of these trees is the same. So when the operation is associative, the only thing that matters for the result of reduce is the order in which the elements appear in the tree. Now I stated it as a consequence, can you prove that this fact, in fact, follows from associativity? Recall that associativity stated that search inequality holds for two particular trees, t1 and t2, of size three. Now the consequence set says that, in fact, then it extends to trees of arbitrary size that have the end order of elements. Here's the intuition why this consequence holds. Associativity law says that doing a so called tree rotation on a tree preserves the result of the sub tree. Note that this rotation preserves the order of elements. Now, what associativity law says that it also preserves the value, now using these rotations, we can convert any tree into a tree that essentially looks like a list. Here's an example used. If we have the following tree containing x, y, p and q, then by applying the above transformation and by identifying this sub-tree with z in the transformation rule, you can see that we then obtain a tree who's left children are always just individual values and never trees themselves. So it turns out we can do such rotations to arbitrary trees and bring them to this normal form. This process preserves the toList value of such trees, and it is straightforward to see that if two trees are in such normal form and have the same toList value, then they are in fact identical trees. So reduce will give the same value on such identical trees. But because this value was preserved throughout dissertations that means that the original trees also gave the same value. Having seen the reviews on trees, let's now look at doing reviews on other kinds of collections. From the outside, clients often do not have access to the exact structure of a collection such as we had in case of a tree. In case of array, it's not even immediately clear why there should be a tree structure. However, it is useful to think about reduction in terms of a tree. If we take for example array, we can think of reusing array as conceptually converting it into an approximately balanced tree. Then doing the tree reduction, which we have seen is efficient and then we get the result of reusing the array. Now it is because of associativity that we can choose how we do the conversion of an array into a balance tree. And so we choose balance tree, because that will give us low height, and therefore, good parallelism. When I say convert into a tree, it is not really necessary to build an actual tree in memory. Because the reduction will anyway replace these Node constructors of a Tree with our binary operation, f. So in place of constructing a node, we can just immediately apply this binary operation, f, and recall just as in previous cases, that when we have small segments of an array. It's better not to try to paralyze operations on them but just do the simplest possible sequential computation. This gives us the following code. We computer reduce on our a with some function f by invoking this auxiliary function reduce segment, giving the entire length of the array as the segment boundary. So all the work is done in the function reduce segment. I have mentioned previously that the base case is handled sequentially. So we have left and right boundary of our array segment and we need to combine these operations using r function, left. Here, we are combining them front left to right, using a simple while loop. Otherwise, if we have a long segment, we'll divide the segment into approximately equal subsegments. We will invoke recursively reduceSeg on each of these subsegments and we will do this in parallel. This will give us two values, a1 and a2, which we can then combine using the function f.
