Is Fold operation the same as Reduce operation in MapReduce programming model? If not, what's the difference?

@sirah in cs242 we learned that Fold differs from Reduce in that Fold allows us to specify both an initial value and a binary operation, while Reduce only allows us to specify the operation. In this case, we're running "fold 10 +" on our vector, which defines 10 as the initial value that we're adding the items in our vector to.

@sirah I think another difference is that functions used in reduce are associative so reduce is very easy to parallelize. For fold, this function can be any binary function. For example, if the function is division: f(a,b)=a/b, then we will have to run folding following the correct order. That's why we have parallel folds next slide that uses a combiner function to enable parallelism.

is there any difference in foldl vs. foldr depending on context? what should you consider?

Is it true that a function is parallelizable if it is commutative and associative?

@joshcho. Think about what foldl and foldr would do in the case where the operator is exponentiation.

foldl raises the base to successive powers, while foldr exponentiates until you reach a larger and larger number to exponentiate with the base.

foldl 2 [1 2 3 4] = (((2^1)^2)^3)^4 = (4^3)^4 = 64^4 foldr 2 [1 2 3 4] = 2 ^ (1 ^ ( 2 ^ (3 ^4))) = 2 ^(2^3^4) = 2^(2^81), which is much larger

Originally I thought the seed appeared more in the operation than I thought it did, but turns out it's just used in the initial computation. In this particular example, the binary operation of addition takes two scalars and returns a resulting scalar. 10 is just the first value added to the array. I wonder why the seed is so important though: why not just think about how to parallelize the addition of all elements in the array?

@linden Perhaps it's just so that there is some "initial" value when you do the operations. In the case of just adding all the elements in a new expanded sequence with 10 at the front, there is some implication of starting the total at 0 and then add to that. If the op was different, e.g. multiplication, perhaps you would start at 1. Or there could be other ops that might require a different initial value to start from.