exercise-2.md

Exercise 2

Use the following commands to make a fresh clone of your repository:

git clone -b exercise-2 git@gitlab.epfl.ch:lamp/student-repositories-s21/cs206-GASPAR.git exercise-2

Update the README.md file with your solutions. Don't forget to list the group members's SCIPER numbers.

Problem 1: Aggregate

In this week's lecture, you have been introduced to the aggregate method of ParSeq[A] (and other parallel data structures...). It has the following signature:

def aggregate[B](z: B)(f: (B, A) => B, g: (B, B) => B): B

Discuss, as a group, what aggregate does and what its arguments represent.

Question 1

Consider the parallel sequence xs containing the three elements x1, x2 and x3. Also consider the following call to aggregate:

xs.aggregate(z)(f, g)

The above call might potentially result in the following computation:

f(f(f(z, x1), x2), x3)

But it might also result in other computations. Come up with at least 2 other computations that may result from the above call to aggregate.

Question 2

Below are other examples of calls to aggregate. In each case, check if the call can lead to different results depending on the strategy used by aggregate to aggregate all values contained in data down to a single value. You should assume that data is a parallel sequence of values of type BigInt.

Variant 1

data.aggregate(1)(_ + _, _ + _)

Variant 2

data.aggregate(0)((acc, x) => x - acc, _ + _)

Variant 3

data.aggregate(0)((acc, x) => acc - x, _ + _)

Variant 4

data.aggregate(1)((acc, x) => x * x * acc, _ * _)

Question 3

Under which condition(s) on z, f, and g does aggregate always lead to the same result? Come up with a formula on z, f, and g that implies the correctness of aggregate.

Hint: You may find it useful to use calls to foldLeft(z)(f) in your formula(s).

Question 4

Implement aggregate using the methods map and/or reduce of the collection you are defining aggregate for.

Question 5