Functional Programming

A programming paradigm which thinks of computing in terms of mathematical functions and it avoids state and mutable data. Imperative programming is based on the idea of state and mutable data and it corresponds to the kind of assembly language instructions which are understood by the CPU. Functional programming involved greater abstraction and code is written in a manner which looks more similar to the notation of functions in Mathematics textbooks.

Here's the Wikipedia definition :

In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state. Functional programming has its roots in lambda calculus, a formal system developed in the 1930s to investigate function definition, function application, and recursion. Many functional programming languages can be viewed as elaborations on the lambda calculus.

First Order Functions

These are functions like Sin(x), Cos(x), tan(x), fibonacci(x); they all directly execute on "x".

Higher Order Functions

These are functions of functions. For instance CubeOf(sin(x)), CubeOf(cos(x)), CubeOf(tan(x)). In this case, CubeOf is a function which operates on another function (sin or cos or tan). This, is a higher order function. We might also evaluate it this way :

CubeOf(lambda,x) where lambda is a function which could be sin or cos or tan.

Recursion

These are functions which call themselves.

For example :

Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2)

// Starting conditions : Fibonacci(0) = 0, Fibonacci(1) = 1

Currying

Instead of making a function call to :

CubeOf(sin,x) which then calls sin(x), CubeOf(cos,x) which then calls cos(x), CubeOf(tan,x) which then calls tan(x)

It would be neater to call functions in this way: (function1 (function2)) (x) Where function1 = CubeOf, function2 = sin/cos/tan

Commonly used ideas in Functional Programming

Lambda Calculus

This is an entire subject of its own. However, here's a quick and a very, very basic idea.

Take the algebraic expression : x² - 20x + 5. In Lambda Calculus the notation λx.F is used to denote a function with parameter x and body F.

So, the expression above can be re-written as :

λx.(x² - 20x + 5)

Which is read as the function of x whose value is given by x² - 20x + 5

Lambda Calculus uses the Prefix form, so we reduce the expression step by step :

λx.(+(x²-20x)5)

λx.(+(-(x²)(20x))5)

λx.(+(-((*x)x)((*20)x))5)

Note, that we use "Currying" in the last step because lambda calculus curries its functions which have multiple variables so (* x y) is written as ((* x) y), the function (* x) is the function which multiplies something by x.

To evaluate this function with x = 1 :

λx.(+(-((*x)x)((*20)x))5).1

= (+(-((*1)1)((*20)1))5

=(+(-(1)(20))5)

=(-20 + 5) = -15

Lambda in Functional Programming

This refers to "anonymous" functions. CubeOf(some_function,x) => CubeOf({5x+1} , x).

Here {5x+1} is the anonymous function or a lambda. CubeOf({5x+1} , x) = (5x+1)³

^{Here is a simple Python example with Lambda -}

def multiplier(x):
return lambda y: x + y

multiply5 = multiplier(5)
multiplier5(2)
# Answer = 10 ...(2*5 = 10)

Filter in Functional Programming

Let x be a list of natural numbers from 1 to 20. Now, we want to generate a list of only even numbers between 1 and 20. This desired list can be thought of as : x.filter( isDivisibleBy2(n)).

Or let us start with a list "x" of natural numbers between 1 and 100. Suppose we want to generate a list of only those natural numbers which are prime. The desired list can be thought of as :

x.filter( isTheNumberPrime(n))

This, is a very basic idea of what a "filter" function is about. To put it in a more formal way, a filter function is a Higher Order function, which operates on a data structure such as a list and it produces a new data structure which retains only those elements from the original data structure, which satisfy a certain predicate function p.

In Ruby, the filter is available in the form of "select" as shown in the example below :

[1..10].select{ |x| x%3 == 0}

# [1..10] is the list of natural numbers from 1 to 10

# x%3 == 0 is the predicate which we wish to satisfy

# Result [3,6,9] # These are the multiples of 3 between 1 and 10 - this is our desired result.

In Python, the filter is available in this form: filter(function,list)

In C# the filter is available as: ienum.Where(pred)

The Learning Point

Navigation

Navigation