Identifying Patterns and creating Higher Order Functions

A higher order function is a function which takes functions as parameters or returns a function. As an example, let us consider the following

1) Sum of all integers between two integers a and b
def sumInts(a:Int,b:Int):Int ={
if (a>b)
0
else
a+sumInts(a+1,b)
}

2) Sum of square of all integers between two integers a and b

def square(x:Int) :Int=x*x

def sumSqaure(a:Int,b:Int):Int ={
If(a>b)
0
else
square(a) +sumSquare(a+1,b)
}

3) A function to square all the powers 2^n where n betweentwo integers a and b

def powerOfTwo(x:Int):Int={
if(x==0)
1
else
2*powerOfTwo(x-1)
}

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

These functions are all instances of {Summation from a to b} for different values of f . We can factor out the common pattern by defining a function sum

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

Using sum, we can formulate the three summing functions as follows.

def sumInts(a: Int, b: Int): Int ={
sum(id, a, b)
}

def sumSquares(a: Int, b: Int): Int ={
sum(square, a, b)
}

def sumPowerOfTwo(a: Int, b: Int): Int = {
sum(powerOfTwo, a, b)
}

where
def id(x: Int): Int = x

def square(x: Int): Int = x * x

def powerOfTwo(x: Int): Int = {
if (x == 0)
1
else
2 * powerOfTwo(x-1)
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: