0:13

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.

3:03

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.

3:33

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.

4:11

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.

5:39

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.

6:50

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.

7:36

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.

8:37

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.

9:36

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?

10:23

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.

12:21

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?

12:58

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.

14:13

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.

17:15

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.