Functional Programming: Explained in Detail

I hope you liked my previous article on Functional Programming and we discussed what is Functional Programming and the support in .NET. So, I am not going to give a definition for Functional Programming (FP) as you can get it by searching it in Google anytime. This article basically discusses the aspect of programming in terms of functions and then discuss how C# supports functional programming.

 

Why Functional Programming

 

You can say FP is used to eliminate code redundancies and to create a better coding style. Let us think of functions first. What is a function?

 

A function is that performs the same thing every time you ask it to. We all know that in Trigonometry the Sine function is defined as the "Opposite Side/Hypotenuse". You provide the value of the opposite side and Hypotenuse; it calculates the value for you. It does the same for various arguments but returns a different output based on the input. For the same input, it gives the same output at any point in time. We all know Tangent is defined as "Opposite/Adjacent". In other words, it is Sine/Cos values.

 

If we write a function for calculating the value of a Tangent angle what is the methodology we need to follow? Do you want to derive the whole step of finding the sine value and cosine value by writing the formulae and then dividing the Sine/Cos value to get the Tangent angle? Will, it is not good if the Tangent angle takes the Sine function and Cosine function as parameters and calculates the Tangent angle for you? By allowing functions to be passed as parameters the code will be greatly reduced and makes your programming more abstract and reusable.

 

Even if we take arrays, we can pass arrays as a parameter to a function and do many operations on them. At any moment of time, if you call arrayVariable [number], it gives you the value at that position or gives you an error if the position you are expecting is beyond the size of the array. If arrays do not provide the function to give you the value of the element at the position you are asking for, we should have ended writing a lot of code.

 

Had Google not used the MapReduce (MapReduce is a programming model for processing large data sets, and the name of an implementation of the model by Google. MapReduce is typically used to do distributed computing on clusters of computers.[1]), we would not have been able to search the data anywhere in the world in a fraction of seconds. MapReduce is inspired by the two functions map and reduce in the commonly used in Functional Programming and Lisp.

 

Here are the main characteristics of any functional programming language:

• First-Class Functions
• Higher-Order Functions
• Pure Functions
• Currying or Partial Application
• Recursion
• Pattern Matching
• Memoization

Functions as first-class objects

 

What we have noticed in the preceding discussion is that if we can use functions as a different object or an entity there are more benefits. We need to consider them as a separate object since if they are part of a class then to use the functions in other classes we then need to create an instance of those classes or if it is a part of a static class, we need to use the class name thus this introduces dependencies in the code. It would be more beautiful if we can support functions as they are giving them a first-class priority along with the other objects in our code. If they are independent then they can be used more effectively.

 

Microsoft C#/VB.NET supports functional programming

 

Microsoft has realized the importance of functional programming and hence supports this feature in C#. With the introduction of LINQ and Lambda expressions, functional programming came into existence. For example, consider the LINQ statement below:

SomeCollection
.Where(c => c.SomeProperty < 10)
.Select(c => new { c.SomeProperty, c.OtherProperty });

You can also call FP declarative programming where you are interested in specifying what to do instead of how to do it. If you look at the preceding code, we have a collection and we want to get the results where the property of the collection objects are less than 10. Here we are not writing code to retrieve all the collection objects and checking if the property is less than 10. Instead what we are doing is asking the C# compiler to do that. We specify what we want to accomplish and the C# compiler internally generates logic for looping through all the collection objects and find each object if the property is less than 10 and if so, adds the objects to its list and then finally returns the results.

 

Note: LINQ is just one implementation of FP.

 

Function Types

 

Wherever we are using a strongly-typed delegate we can use generic function types. Let us see how to use a function type in the place of the delegate.

 

Let us take a delegate that matches the function which takes two integer parameters and returns an integer.

delegate int MyDelegate(int a, int b);
static int SumOfTwoNumbers(int a, int b) {
    return a + b;
}
MyDelegate myDelegate = SumOfTwoNumbers;
int result = myDelegate(5, 6);
Console.WriteLine(result);
Console.ReadLine();

 

The preceding delegate can be replaced with a Generic Function Type introduced in .NET 3.5 as below.

 

The syntax of the function type is:

 

Func<T1,T2...TResult> where T1, T2, and so on are arguments of a function and TResult is the return type of the function.

Func<int, int, int> f = SumOfTwoNumbers;
int result = f(5, 6);

The preceding code is still working as a delegate but supports functional programming. Let us see what its metadata reveals about the generic type Func. If you look at the metadata of above Func<int,int,int>, you will find the following:

namespace System
{
    // Summary:
    //     Encapsulates a method that has two parameters and returns a value of the
    //     type specified by the TResult parameter.
    //
    // Parameters:
    //   arg1:
    //     The first parameter of the method that this delegate encapsulates.
    //
    //   arg2:
    //     The second parameter of the method that this delegate encapsulates.
    //
    // Type parameters:
    //   T1:
    //     The type of the first parameter of the method that this delegate encapsulates.
    //
    //   T2:
    //     The type of the second parameter of the method that this delegate encapsulates.
    //
    //   TResult:
    //     The type of the return value of the method that this delegate encapsulates.
    //
    // Returns:
    //     The return value of the method that this delegate encapsulates.
    public delegate TResult Func<T1, T2, TResult>(T1 arg1, T2 arg2);
}

You can replace the preceding code with a lambda expression as in the following:

Func<int, int, int> f = (i, j) => i + j;
int result = f(5, 6);

In both cases, f is a function type with two integer parameters and returns an integer. There are two other generic types available in C#. One is Predicate and the other one is Action. These two are in a way variants of Func.

 

Predicate<T > represents a function that returns true or false. This is equivalent to Func<T,bool>.

 

Predicate takes 1-N number of arguments and it always returns a boolean value.

Func<int,bool> f = (i) => i==5;
bool result = f(5);

Can be replaced with:

Predicate<int> f = (a)=>a==5;
bool result = f(5);

The other generic function type available is Action. This type takes a parameter and returns a void. This is equivalent to a Func with the return type void (logically, but do not try the syntax since void is not a return type).

 

Note: Fun<> and Action<> takes only up to 4 parameters. If you want to write a delegate that takes more than 4 it is considered to be a bad practice or sloppy code.

 

An example is as below:

Action<string> print = Console.WriteLine;
for (int i = 0; i < 5; i++)
{
    print(i.ToString());
}

Higher-order Functions

 

One of the characteristics of Functional Programming is that a function should accept another function as a parameter and also return a function type as a return type of the function.

 

Let us see it by example.

 

Let us say I have a function that accepts an integer and adds a value of 5 and returns the total value; see:

 

Func<int, int> g = (b) => b + 5;

 

Another function is going to take an integer and multiply it by 5 and return that as the result:

 

Func<int, int> f = (a) => a * 5;

 

Now I am writing a function using these two functions as parameters and returns a function that accepts an integer parameter and returns an integer value. For more generic use, instead of specifying the types as integers we have declared the types as more generic; see:

static Func < A, D > Calculate < A, B, C, D > (Func < A, B > f, Func < B, C > g, Func < C, D > h) {
    return (x) => h(g(f(x)));
}
static void Main(string[] args) {

    Func < int, int > f = (a) => a * 5;
    Func < int, int > g = (b) => b + 5;
    Func < int, int > h = (c) => c * (c - 1);
    Func < int, int > k = Calculate(f, g, h);
    Action < string > print = Console.WriteLine;
    print(k(4).ToString());
    Console.ReadLine();
}

The output will be 600.

 

This can be somewhat represented in mathematics. As best as I can remember it is as follows (Please go through any mathematics book for a better understanding of functions and mapping; do not rely on my words):

 

If f maps from A to B and g maps from B to C and h maps from C to D then f(g(h)) maps from A to D.

 

f:A->B g:B->C h:C->D k:A->D

 

Pure Functions

 

Pure Functions are also one of the characteristics of FP. A function is said to be a pure function if it is transparent to the user. Or you can say a function is pure if it always evaluates the same result given the same argument values. The function result does not depend upon any internal state of the program or any of the variables in the program or any external input such as from I/O devices. Also, the function must not cause side effects.

 

For example, pure functions are as below:

1. Sin(x) - This always returns the same value for the same x value.
2. Length(s) - This function also returns the same value for the same argument.

Impure functions are like date functions or random functions in programming languages.

 

For example in C#, we can consider the following method is a pure function:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace FunctionalProgramming {
    class Program {
        public static int SumOfTwoNumbers(int x, int y) {
            return x + y;
        }

        static void Main(string[] args) {
            Console.WriteLine(SumOfTwoNumbers(4, 5));
            Console.Read();
        }
    }
}

Currying

 

Here's what Wikipedia says:

 

"[Currying] is the technique of transforming a function that takes multiple arguments in such a way that it can be called as a chain of functions each with a single argument." - en.wikipedia.org/wiki/Currying

 

In simple terms, currying is splitting the multiple arguments in a function into a function that takes an argument and then returns a function that takes the next argument. This is a little bit confusing and very hard to understand at first. Please go through the example 3 to 4 times if you face difficulty in understanding the code.

 

For example, I have a requirement that my function should accept 3 integer parameters and it multiplies the first number with the sum of the other two numbers; see:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace FolderTest {
    class Program {
        static void Main(string[] args) {
            Func < int, int, int, int > func = (a, b, c) => a * (b + c);
            Console.WriteLine(func(3, 4, 5));
            Console.Read();
        }
    }
}

The output will be 3 * (4+5) = 27.

 

Now we have seen in the preceding code that if we want to do a*(b+c) we were passing 3 parameters and it is executing the code to produce output.

 

But will it not be good if we can write a function in such a way that it adds more meaningful syntax while accepting parameters? Like following??

 

func(4,5,6) to func(4)(5,6)

 

So we will change the code to the following:

Func<int, Func<int, int,int>> add_mul = i => (j,k) => i * (j+k);
Console.WriteLine(add_mul(3)(4,5));

In the preceding code add_mul(3) actually returns a function. We invoke that function immediately by passing 4, 5 which the function sums up the two numbers 4, 5, and then it is multiplied by 3 to give the total output.

 

Let us see how it works. First let us pass 3 to the function variable, as in:

Func<int, Func<int, int, int>> add_mul = i => (j, k) => i * (j + k);
var myfunc = add_mul(3);

 

If you see in the preceding figure, myfunc holds a method. Add_mul(3) has returned a function back and now we pass 4,5 and see what happens:

 

 

Now you see that it has summed 4 and 5 and then multiplied with 3 to give the final output as 27. Here are curried function is partially applied and we can reuse this function as needed.

 

Now let us go a step forward and split the function that sums two numbers into partial functions so that it is more curried as in the following:

Func<int, Func<int, Func<int, int>>> mult_c = i => j => k => i * (j + k);
Console.WriteLine("Second version output is {0}",mult_c(3)(4)(5));

See now the format of the function is changed to mult_c(3)(4)(5). That means a function that takes a function that takes another function and returns a function back to each other until the end of the output is calculated.

 

Here is the final program:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace FunctionalProgramming
{
    class Program
    {
        static void Main(string[] args)
        {
            //First version
         Func<int, Func<int, int, int>> add_mul = i => (j, k) => i * (j + k);
         Console.WriteLine("First version output is {0}", add_mul(3)(4, 5));
            //More refined version
          Func<int, Func<int, Func<int, int>>> mult_c = i => j => k => i * (j + k);
          Console.WriteLine("Second version output is {0}", mult_c(3)(4)(5));
            Console.Read();
        }
    }
}

Now run the program to see if both methods return the same output:

 

 

Recursion

 

According to Wikipedia,

 

"Recursion […] is a method of defining functions in which the function being defined is applied within its own definition"

 

We all know what a recursion function is. We all have done factorial programming during our initial days of learning programming and so here I do not dwell much on that.

 

Let us discuss something in terms of functional programming. I have a requirement that a function takes a function parameter (a function that does some operation on parameter values), a source of values (IEnumerable type), and a final value. This function recursively executes by calling itself until it reaches an exit condition that is it has completed operating on the entire set of data.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace FolderTest {
    class Program {
        static int RecursiveFunction(Func < int, int, int > func, IEnumerable < int > values, int final) {
            return (!values.Any()) ?
                final :
                RecursiveFunction(func, values.Skip(1), func(final, values.First()));
        }
        static void Main(string[] args) {
            Func < int, int, int > add = (i, j) => i + j;
            var integers = new [] { 1, 2, 3, 5 };
            var sum = RecursiveFunction(add, integers, 0);
            Console.WriteLine(sum);
            Console.Read();
        }
    }
}

In the preceding example, the recursive function takes a function, add, that sums two numbers and array values as the second parameter and a final value.

 

So, the function always checks if the values still exist and if they do then get each value and sums them until the values have been exhausted. The Skip function in the preceding code bypasses a specified number of elements in a sequence and returns the remaining sequence.

 

So, the code is taking the first element in the sequence every time and summing up with the previous one until all the elements are processed and finally the sequence has become empty. If it is empty then it returns the final value.

 

 

Iteration 1

 

The value of func(decrement, values.First()) is 1. Now the final value is 1. So, it loops through the elements and assigns the sum to the final parameter. After all the sequence is empty the function returns the final parameter value i.e. sum of all the values.

 

 

I hope you have become exhausted with the preceding code and so let us stop at this moment.

 

In the next article, we will discuss the other two characteristics Pattern Matching and Memoization. Also, we will explore F# programming, the true functional programming by Microsoft.