Introduction to Functional Programming using F# - Part 1

Introduction

In this article, I am going to explain the fundamental concepts behind functional programming and advantages of these languages over procedural programming.

What is Procedural Programming?

Generally, we call procedural programming as "imperative" meaning specifying the steps the program should take to achieve the result. Mathematically, modifying the values of variables by statements and expressions like:

See the following code snippet:

// Code 1
int i = 0;
i = Convert.ToInt32(Console.ReadLine());
i = i + 10;

Variables and their values make procedural programming as "state" based means changing from input state to output state. Here, the output is deterministic as

where, f is a function.

Simply we can say, procedural programming contains the following type of statements:

• Sequential
• Conditional
• Repeated

What is Functional Programming?

In this section, let us first understand where functional programming differs from procedural programming.

Variables are Values

There is no state mechanism in functional programming that is variables are to be considered as values.

Sequence is Meaningless

In functional programming, sequential statements are meaningless meaning that there are no repetitive statements. Instead, it provides a mechanism called recursive meaning a function calls itself. For example, let us write a program to calculate the sum of the given range in both procedural and functional programming.

// Code 2
// Sum of range in C# (Procedural)
int SumOf(int fromValue, int toValue)
{
    int result = 0;
    for(int i = fromValue; i <= toValue; i++)    
        result += i;
    return result;
}

The above procedural program gives a deterministic output using states result and i. Let us see a functional programming code.

// Code 3
//Sum of range in F# (Functional)
#light
let rec SumOf fromValue toValue =   
    if fromValue > toValue then 0 else (SumOf (fromValue + 1) toValue) + fromValue

In the above functional program, you can see the power of recursive approach and variables are treated as values. The recursive as shown in the above program is possible in modern procedural languages including C++, C# and Java. However, I'll show the real benefit of this in functional programming in later sections.

Functions are Values

Functions can be treated like values so you can pass these as argument, return as function values and calculate it with others (this one is shown in Code 3).

Immutable Data Structure

We know that immutable means state of an object cannot be modifiable after creating it. In .NET, string is one of the good examples for this. Immutability makes programs much simpler since there is no need to perform copying and comparing. However, immutable to all objects does not make sense in the real world programming. This would affect system performance. In pure functional perspective, objects are immutable. Let us find how the functional programming implementation handles this in a later section.

Let us consider an immutable collection, every time you add an item into this, as per theory, a new object will be created. So, to add four integers into an immutable collection MyList:

MyList result = new MyList().Add(100).Add(101).Add(102);

This actually means that:

MyList l0 = new MyList();
MyList l1 = l0.Add(100);
MyList l2 = l1.Add(101);
MyList result = l2.Add(102);

High Order Functions

A function which accepts another function as an argument is called high order function. Let us see a high order example in F#.

// Code 4
//High order function example in F# (Functional)
#light
let rec factorial n = if n <= 1 then 1 else n * factorial (n-1);;
let square (f : int -> int) n = f(n) * f(n);;
System.Console.WriteLine(square factorial 3); // 36

The function square requires a function with an integer as argument and returns an integer, and n. This function applies f into n then calculates the square.

Curried Functions

A function that returns a function as its result is called curried. Let us see a curried example in F#.

// Code 5
//Curried function example in F# (Functional)
#light
let rec XPowerN x n =
    match n with
    | 0 -> 1
    | n -> x * XPowerN x (n-1);;
let Square x= XPowerN x 2;;
let Cube x = XPowerN x 3;;
System.Console.WriteLine(Square 4); 	// 16
System.Console.WriteLine(Cube 2); 	// 8

Code 5 shows that the XPowerN is curried in functions Square and Cube.

End Note

In this section, we have seen what is functional programming and how it differs from procedural programming. In the next part, I'll explain the origin of functional programming lambda calculus and advantages of functional programming.

Read Part 2 of this article.

References

View my two part screen cast about Functional Programming with C# 3.0 at http://www.screencast.com/t/a0lgbHiF7cF and http://www.screencast.com/t/dndqkp4r, or, download both from http://cid-1ea86c1fb1c134b8.skydrive.live.com/browse.aspx/ScreenCast.

History

• 3^rd February, 2009: Initial post