Ever since the pundits predicted that the doomsday of Moore’s Law was fast approaching* (*debatable) . There’s been an eerie feeling amongst the producer – consumer cycle of microprocessors. The question on everybody’s mind seems to be- So what is the consequence of this ? Does it mean that the microprocessor developers like Intel, AMD et al. would close their shop and get into other domains ? (for the love of God not another browser !) Well the answer is astounding NO. Parallel computing, Multi core architectures were an indirect consequence of this.
As a co-consequence of this, something that was ignored for almost 60 years ago made it way back into limelight and became a buzz word. Lo and behold for here cometh Functional Programming ! Ever since Parallel Programming, Multi Core architecture and Google’s Map Reduce came into the ZONE. Functional Programming is making sinusoidal waves all over the developer circuit. Functional Programming is as old as computers themselves and they rightly deserve all the credit people have been pouring all over it.
This is part 0 of an n part series – of my humble attempt in exploring the functional programming concepts using C#.
To understand the ‘F’ in Functional Programming, we need to step back a little and revisit the approaches we used to hitherto to solve a trivial problem say - filtering a sequence of numbers to make it contain only odd numbers.
Procedural
In the grand old days of procedural languages we would have probably written something like this.
void Main()
{
List numbers = new List{1,2,3,4,5};
result = FilterOnlyOddNumbers(numbers);
}
List FilterOnlyOddNumbers(List numbers)
{
List result = new List();
foreach(int n in numbers)
{
if(i%2 !=0)
{
result.Add(n);
}
}
return result;
}
The problem with above code is every time I need a new filtering logic, I would end up adding a new a method. Like the code below that filters out the even numbers.
List FilterOnlyEvenNumbers(List numbers)
{
List result = new List();
foreach(int n in numbers)
{
if(i%2==0)
{
result.Add(n);
}
}
return result;
}
And what is hard to miss from the above code is that the only change between FilterOnlyOddNumbers and FilterOnlyEvenNumbers is the line #6 !!
Object Oriented
Enter Object Oriented paradigm – a paradigm that promised to cure us from the above problem of code redundancy using Abstraction..!!
And here’s what an object oriented junkie would have done with the problem of filtering numbers. Abstract out the logic for filtering the numbers to an interface IPredicate
(line #6 of the earlier code segments)
interface IPredicate
{
bool FilterCondition(int n);
}
And we would rewrite our Filtering method to use the abstraction provided by the interface IPredicate
List FilterNums(List numbers,IPredicate p)
{
List result = new List();
foreach(int n in numbers)
{
if(p.FilterCondtion(n))
{
result.Add(n);
}
}
return result;
}
Notice how line 6 checks for the predicate of the filter condition. To use the FilterNums method we would need to create classes which implement the IPredicate interface. And Yes. this is the Strategy design pattern !
class OddFilter:IPredicate
{
public bool FilterCondtion(int n)
{
return n%2!=0;
}
}
class EvenFilter:IPredicate
{
public bool FilterCondition(int n)
{
return n%2==0;
}
}
And invoking the FilterNums using poor man’s dependency injection.
List oddNums = FilterNums(ints,new OddFilter()); List evenNums = FilterNums(ints,new EvenFilter());
Ah Sweet ! Before this design inflates your object-oriented design purist ego and you start grinning ear to ear. Lets look at the shortcomings of this OO design.
In an OO universe everything is an object. If you look carefully at our OO design above, all we need is a predicate FilterCondition to achieve a trivial filtering function but we’re forced to abstract it into an interface and implementing the interface in a Filter subclass. And what’s worth noticing further, is that you would require as many filter classes implementing the interface, each containing a just a couple of lines of code. Better fix that before the class proliferation police come knocking at your door.
To draw a trivial analogy – consider the class OddFilter as a box which contains method FilterCondition – the ball inside the box OddFilter, whenever an Oddfilter is passed between functions, it is passed as boxes (objects) to and fro between functions. In short the boxes are the objects and member methods are the balls in the boxes.
With respect to our FilterNums method - FilterNums receives the OddFilter object (box) and then unpacks the box (references to the method) to find the ball (FilterConditon method). Looking closely we find that all we truly need is the ball (method) but we are over engineering the design by packing the ball into the box (object). But wait a minute I cannot just throw a ball alone (method) between function calling boundaries because *my programming language* is object oriented everything which goes in and comes out of the function are objects !! *my programming language* only knows to throw and catch boxes !!
Or is it ?? :)
Functional Programming
One of the core concepts of Functional Programming is that all your functions in your programs are First Class functions. Err.. Well OK that sounds cool but what on God’s green earth is a First Class Function ?
It just means that Functions in the language gets same First Class treatment like the objects – meaning you can throw and receive just the functions between a function calling boundary without wrapping them in objects.
With respect to our earlier analogy we can just throw around just the ball between the methods with out unnecessarily packing them into boxes!
In C#, this is achieved using delegates and lambda expressions.
And rewriting our FilterNums method using Predicate<int> delegate
List FilterNums(List ints,Predicate Filter)
{
List result = new List();
foreach (int n in ints)
{
if(Filter(n))
{
result.Add(n);
}
}
return result;
}
And invoking the FilterNums method is easy and elegant. And you do not have to create additional classes for each of additional filter logic.
List oddTodds = FilterNums(ints,i => i %2!=0); List evenStevens = FilterNums(ints,i=> i %2==0);
The FilterNums takes a first class function (Filter) as a parameter. Such functions that take in a functions as parameters or/and whose return types are functions are called as Higher Order Functions.
Now that you know the definitions and meanings of First Class functions and Higher Order functions you can now speak to a Haskell programmer.
This concludes Part 0 of this series, In the next post we’ll look at currying of a function and before I forget – you can you leave your chef’s hat at home :)
Tags: .NET, C#, First Class functions, First Class Objects, Functional, Functional Programming, Haskell, Higher Order Functions, Lamda Expressions, programming
Good stuff! I was looking at some f# for map and reduce type algorithms and came across this one.
Thanks for the comment Nikhil,
Feel free to subscribe to the RSS :)
Planning to do a series on Functional Programming and F#