Map and Fold | Basics

Map and fold is a different approach of solving a problem then we normally do in our daily computations.

Basic steps

• The problem basically is a list of some values(eg a number array), and we have to do some operation on it to get the output.
• There is a mapper f(x) which takes one value at a time, and creates another value as its output. The created value may be same or different depending upon the required result.
• The Fold(g(x,y), I) function takes a function g(x,y) and an initial value I.
• Given a problem in Map and fold, as a solution, we have to find the 
• function f(x), 
• function g(x,y), 
• initial value I, 
• And the interpretation of the final result.

Lets learn it with an example.

Problem) We have an array of numbers {2, 7, 9}. Find the sum of squares of the numbers in the array using map and fold.

Solution:

{2, 7, 9}                   - f(x) ->                                                     {4, 49, 81}  

{4, 49, 81}              - Fold(g(x,y), 0) ->                                   134

{0 + 4=4, 4+49=53, 53+81=134}

f(x) = x^2

g(x,y) = x + y

Initial value = 0

final result is the solution(ie, sum of the squares of the numbers in the array)

.

Lets look at the fold diagram of map and fold.

You can see that the initial value is the first y of the g(x,y) function. The output of the first call to g(x,y) is passed to the g(x,y) again as next y value. So the Fold operation is done sequentially, but the f(x) can be done parallel.

Problem 2)

Write a Map and Fold Algorithm to classify an array into three different category.

A)Has more even numbers

B)Has more odd numbers

C)Has equal number of even and odd numbers

Solution 2=>

int f(x){

    return (x%2==0?1:-1;)

}

int g(x,y){
     return x+y;
}

Initial value = 0

+ integer : more evens, - integer: more odds, 0: equal