Higher Order Functions in Functional Programming

Function programming paradigm treats functions as its first class citizens which means

• you can pass a function as an argument to another function
• you can return a function from a function and
• you can compose a function inside another function and assign it to a variable too just as we do with any other value or reference type.

This provides a flexible way to compose programs.

To build up this concept, consider a summation function which gives sum of elements in the range a to b.

This can be written recursively as follows.

def summation(a: Int, b: Int): Int = {
    if (a > b) 0
    else a + summation(a + 1, b)
  }                                               //> summation: (a: Int, b: Int)Int

  summation(3, 6)                                 //> res0: Int = 18

There are 2 problems with the above piece of code.

• The parameter b doesn't change, still I have to pass it to all the recursive calls as summation requires 2 parameters.
• The summation function is not tail recursive. If the range of a and b is huge then the piece of code may result into stack overflow.

If you think, summation is internally running a loop from a to b. So the new code with tail recursivenes will look like,

  def summation(a: Int, b: Int): Int = {

    def loop(a: Int, acc: Int): Int = {

      if (a > b) acc
      else
        loop(a + 1, a + acc)

    }

    loop(a,0);
  }                                               //> summation: (a: Int, b: Int)Int

  summation(3, 6)                                 //> res0: Int = 18

Note that you must always specify the return type of the recursive function, otherwise the Scala compiler will not be able to infer the type, as while doing the type inference it will end into a never ending recursive calls.

Taking this a step ahead, the requirement might be to

• find sum of squares of numbers between a and b
• find sum of cubes of numbers between a and b
• find sum of factorials of numbers between a and b

The final thing is to do sum of numbers between a and b, just the function f to be applied on the number is changing. This can be expressed mathematically as

where f can be
f(x) = x*x
f(x) = x*x*x
f(x) = factorial(x)

So the summation function will take one more argument f i.e. the function to be applied on each a before adding it to the accumulator. The function f takes an Int argument and returns an Int value. Hence the summation function can be redefined as,

  def summation(a: Int, b: Int, f: Int => Int): Int = {

    def loop(a: Int, acc: Int): Int =
      if (a > b) acc
      else
        loop(a + 1, f(a) + acc)

    loop(a, 0);
  }                                               //> summation: (a: Int, b: Int, f: Int => Int)Int

Summation of factorial of numbers between a to b - Define a function fact in tail recursive way to find factorial of a number and then pass it  to summation as an argument.

  def fact(a: Int): Int = {

    def f(a: Int, acc: Int): Int =
      if (a == 0) acc
      else f(a - 1, a * acc)

    f(a, 1)
  }                                               //> fact: (a: Int)Int

  summation(3, 5, fact)                           //> res0: Int = 150

Lambda expressions - For small functions, like square, cube of a number we can define the functions inline as lambda expressions while making summation function call.

summation(1,5,x=>x*x)                           //> res1: Int = 55
summation(1,3,x=>x*x*x)                         //> res2: Int = 36

Currying the function - In Currying, a function takes only one argument and returns a value. Let's apply some currying on summation function named as summation1.

def summation1(f:Int=>Int):((Int,Int)=>Int) = {
 def FSum(a:Int, b:Int):Int = {
  
  def loop(a:Int, acc:Int):Int = {
   if(a>b) acc
   else
    loop(a+1,f(a)+acc)
  } 
  loop(a,0)
 }  
 FSum
} 

The advantage is that we can create different flavors of summation function and then call them with proper arguments when required. The illustration is as follows.

def sqrSummation = summation1 (x=>x*x)    //> sqrSummation: => (Int, Int) => Int
sqrSummation(5,7)                         //> res1: Int = 110
  
def cubicSummation = summation1 (x=>x*x*x)//> cubicSummation: => (Int, Int) => Int
sqrSummation(1,3)                         //> res2: Int = 14
 
def factoSummation = summation1(fact)     //> factoSummation: => (Int, Int) => Int
factoSummation(3,5)                       //> res3: Int = 150

summation1(x=>x)(1,10)                    //> res4: Int = 55

Taking currying to the advanced level - Rather than having a sub function being returned by a function, we can logically aggregate the parameters into the same function by passing them in separate groups. This will help in reusing the function.

Q. Can we have a series function which will do operation x (instead of only summation) and at the same time apply a function (e.g. square, cube, factorial) on the element before adding it to the result? Most importantly can it be designed in a reusable fashion?

The answer is yes. Following is the series function where Op is a function which takes two arguments and returns an integer value. Op can be summation, product or any other operation. The acc value can be 0 for summation or 1 for product which represents the unit value with respect to the operation.

def series(Op: (Int, Int) => Int, acc: Int)(f: Int => Int)(a: Int, b: Int): Int =
    if (a > b) acc
    else series(Op, Op(f(a), acc))(f)(a + 1, b)

The function can be used to do summation of squares of numbers between 1 to 5.

series((x,y)=>x+y,0)(x=>x*x)(1,5)               //> res0: Int = 55

The function can be used to define factorial function.

def fact (n:Int):Int =
 series((x,y)=>x*y,1)(x=>x)(1,n)           //> fact: (n: Int)Int
 
fact(5)                                   //> res1: Int = 120