Simplifying fold function concept.

Lets us first revise mathematical function quickly.

example 1:
f(x) = 2x+3
f(3) = 2*3+3 = 9
example 2:
f(x,y) = 3x+2y
f(4,5) = 3*4 + 2*5 = 22
example 3:
f(x) = 4x 
f(f(3)) = ?
Here, first we will solve f(3) = 4*3 = 12
Then f(f(3)) = f(12) = 4*12 = 48

A binary function is a function that takes two arguments.

example 4:
f(x,y) = x+2y
f(2,3) = 2+2*3 = 8
example 5:
f(x,y) = x+2y
f(f(2,3), 4) = ?
Here, we will first solve f(2,3) = 2+2*3 = 8
Then f(f(2,3),4) = f(8,4) = 8+2*4 = 16

Fold

• You will come across this word while learning a functional programming langugae.
• Fold is also termed as reduce.
• Fold is a kind of higer order function.
• A higher order function is a function that takes a function as an argument, or returns a function.
• A fold operation can be foldl and foldr. foldl stands for fold left and foldr stands for fold right.
• A fold function will usually take 3 arguments -
  1. A binary function , f(x,y)
  2. A starting value or accumulator
  3. A list or array

Fold definition can be very confusing, so we will try to understand the concept using an example.

Question:
Given a binary function, f(x,y) = 2x +3y 
starting value, i = 1
and a list, L = [2, 3, 4]
find foldl and foldr?
Solution
A. To calculate foldl, we will will traverse the list from left.
Step 1:
Calculate f(x,y) , where x= starting value or accumulator ie 1, y=first element of list from left ie 2.
f(x,y) = 2x+3y 
f(1,2) = 2*1+3*2 = 8
Step 2:
find f(x,y) such that x = output of step1, y=second element of list from left ie 3.
f(x,y) = 2x+3y 
f(8, 3) = 2*8+3*3 = 25
Step 3:
find f(x,y) such that x = output of step2, y=third element of list from left ie 4.
f(x,y) = 2x+3y 
f(25, 4) = 2*25+3*4 = 62
Hence, foldl ( f, i, L) = 62
In terms of composite function,
foldl(f,1,[1,2,3]) = f(f(f(1,2),3),4)
If we store the intermediate results of foldl in a new list we get the result of scanl.
scanl (f,i,L) = [8,25,62]
B . To calculate foldr, we will traverse the list from right.
Step 1:
find f(x,y) where x = starting value or accumulator ie 1, y=first element of list from right ie 4.
f(1,4) = 2*1+3*4 = 14
step 2:
find f(x,y) such that x = output of step1, y=second element of list from right ie 3.
f(14,3) = 2*14+3*3 = 37
step 3:
find f(x,y) such that x = output of step2, y=third element of list from right ie 2.
f(37,2) = 2*37+3*2 = 80
Hence, foldr(f,i,L) = 80
In terms of composite function,
foldr(f,1,[1,2,3]) = f(f(f(1,4),3),2)
Similarily, If we store the intermediate results of foldr in a new list we get the result of scanr.
scanr (f,i,L) = [14,37,80]

Generalized formula would be

foldl(f, i, [x₁,x₂,…, xₙ₋₁,xₙ]) = f(f(…f(f(i,x₁),x₂),…,xₙ₋₁),xₙ)

foldr(f, i, [x₁,x₂,…, xₙ₋₁,xₙ]) = f(f(…f(f(i,xₙ),xₙ₋₁),…,x₂),x₁)

Now let us try to summarize foldl function in words.

A foldl takes a binary function, a starting value (or accumulator) and a list to fold up. The binary function is called with the accumulator and the first element of list and produces a new accumulator. Then, the binary function is called again with the new accumulator and the now second element, and so on. Once we’ve walked over the whole list, only the accumulator remains, which is what we’ve reduced the list to.

Credits:
1. https://www.joachim-breitner.de/blog/753-Drawing_foldl_and_foldr [image]
2. http://learnyouahaskell.com/higher-order-functions [definition]