Functional Programming

Functional Programming is a style of programming in the same way as Object Oriented Programming is a style of programming. Writing great functional programs requires a slight mindset shift compared to the procedural (step-by-step) programming approach that comes naturally to most people, but it’s a powerful concept and one that you will already have used in some of the C# coding you have done to date.

What is Functional Programming?

Functional Programming is a programming style where you think primarily in terms of functions, in the mathematical sense of the word.

A mathematical function is something that takes some inputs, and produces an output. Importantly that’s all it does – there are no side effects such as reading data from a web page, writing text to the console or modifying some shared data structure. In the absence of such side effects, the only thing that can influence the function’s behaviour is its inputs – so given a particular combination of inputs, we will always get back precisely the same outputs. A function that has these properties is called a pure function.

Functional programming is all about using pure functions as the building blocks of a program. Consider the following procedural (non-functional) piece of code:

static void Main()
{
  int[] input = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  var list = new List<int>();

  foreach (int i in input)
  {
    if (i % 2 == 0)
    {
      list.Add(i);
    }
  }

  var output = list.ToArray();
}

This code takes an input array of integers, and produces an output array containing all the even numbers.

We call this code “procedural” because it defines a procedure for the computer to follow, step by step, to produce the result. We are talking to the computer at a detail level, specifying precisely which numbers to move around. We are also creating data structures that are modified as the program executes (the list).

Consider the functional alternative, which is to perform all this using pure functions:

static void Main()
{
  int[] input = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  var output = input.Where(i => i % 2 == 0).ToArray();
}

This version is shorter. But that is not its main selling point. The real benefit is that we’re talking at a much more abstract level about what we want the program to achieve, rather than what we want it to do step by step. You can read the second line of code fairly directly:

• Take input
• Apply a filter to it
  • The filter is “number is even”
• Convert the result to an array

Deep inside the computer’s CPU it will still be doing pretty much the same operations as the previous version, but we don’t need to know that – it’s a level of detail we don’t care about and it might not even be true. In the more general case where we don’t know the concrete type of input (we might define it just as IEnumerable<int>, for instance), it may be a data structure that intrinsically supports parallel programming and is in fact doing the filtering on a multitude of different threads. We don’t care, because we’re talking at a much higher level about what we want to achieve (filtering, via the Where method), rather than how we want to achieve it (a foreach loop, or perhaps some cunning multithreaded processing).

The benefits of Functional Programming

The example above is well representative of the benefits of functional programming. We can summarise these as follows:

• Readability. By expressing our intentions at a higher level than in the procedural style, we can show our intent.
• Conciseness. By the same token, we can implement the same functionality in fewer lines of code. Fewer lines means fewer bugs (certainly fewer characters you can mistype), so provided we retain readability conciseness is a good thing.
• Intrinsic support for parallelism. Even if there’s no magic parallelism happening behind the scenes, functional programming is inherently well suited to multithreaded computing and carrying out different work strands in parallel. This is because its focus on pure functions means that we generally have immutable data structures – that is, data structures whose contents never change. As pure functions do not modify any state of the program, two functions never try to modify the same shared state concurrently, thus avoiding race conditions.

The limitations of Functional Programming

Clearly, there are some spheres in which Functional Programming fits naturally and makes obvious sense. For instance, complex banking calculations will naturally fit the functional pattern because they are all about performing calculations on data. Even less obvious programs generally have elements which can be expressed more clearly and concisely in the functional style – a large proportion of for and foreach loops could be replaced with functional alternatives, as in the example above.

However, strict adherence to Functional Programming principles leads to challenges that make it harder to write many programs. For instance, if side effects are outlawed how can we read user input or write files to disk? Truly functional languages have workarounds for this that “hide” the side effect behaviour in a way that allows you to treat absolutely everything as an apparently pure function call.

The great thing about languages like C# is that they provide support for functional concepts when useful, but still let you use the procedural style when that makes more sense. Hence you can use Console.WriteLine and accept that it’s not very functional in style, but couple it with a neat series of chained function calls to calculate the value to write.

The golden rule is as always: look for the programming style that lets you write a given bit of code in the simplest and most expressive manner possible. That’s often, but certainly not always, a functional style.

Immutable data structures

We mentioned above the benefits of avoiding changes to data. The best way to ensure this guideline is followed is to create immutable data structures – ones that cannot be changed. In C# this is just a case of ensuring that all fields are set in the constructor, and cannot be modified subsequently (so no set on properties, no public fields, and the public methods on the class should never modify its private variables).

It is worth noting that the vast majority of common classes in the .NET libraries are not immutable. For example List<T>, Dictionary<TKey,TValue>, etc. This is largely because .NET is not always well optimised for immutability (creating new objects is relatively expensive), and so using mutable data structures will achieve better performance if you’re doing a lot of operations.

However, where you are not doing anything performance critical and want immutability, you are not stuck with creating your own classes. The secret is to use an appropriate interface that shows your intent to be immutable and prevents code from changing data when you don’t want it to. So for instance you may well create a List<int>, but if you don’t need to subsequently change it you should use IEnumerable<int> in your code – an interface which supports iterating over the members of the list, but not making changes to it. Thus you get the benefit of using immutable data structures in most of your code, without losing the flexibility to, for instance, take advantage of mutation when initially creating the list.

Iterator blocks

Iterator blocks are a powerful way to create immutable lists of data dynamically, on demand. This can be a useful technique to bridge the procedural and functional styles.

Here’s an iterator block that generates an infinite stream of even numbers:

public IEnumerable<int> Evens
{
  get
  {
    int next = 0;
    while (true)
    {
      yield return next;
      next += 2;
    }
  }
}

The magic is in the yield return. Every time someone tries to examine the next integer in the list, this method will be executed until it hits a yield return, at which point it will provide that value to the caller and pause until more of the list is read.

You can use this in any code that takes a list. For example to add up the first 10 even numbers:

var sum = Evens.Take(10).Sum();

(The functional style again – we could have implemented the same thing more verbosely with a for or foreach loop)

Needless to say you should never run this:

var infiniteSum = Evens.Sum();

Since Evens represents an infinitely long list of numbers, this code will never complete. (Or more likely will hit an overflow exception when the sum becomes too large for an int.)

Iterator blocks are not just for infinite lists. Here’s one that reads a file line by line, naturally stopping when the file has been entirely read:

private IEnumerable<string> ReadLines(string filename)
{
  using (var reader = new StreamReader(filename))
  {
    while (!reader.EndOfStream)
    {
      yield return reader.ReadLine();
    }
  }
}

It’s worth understanding what’s going on under the cover, so you can correctly determine how a program will execute. Consider the following:

var lines = ReadLines(filename);
Console.WriteLine(lines.Take(1));
Console.WriteLine(lines.Take(1));

What does this do? The answer is that it prints the first line of the file, twice. It does not print the first two lines. It also carries out the processing involved in reading the file twice, so there are, in total, two calls to new StreamReader, and so on.

Why does this happen? When you define an iterator like this, behind the scenes the compiler creates a class which implements IEnumerable<string>. The lines variable in the example is an instance of this class. When you try to iterate over this enumerable, for example via a foreach or one of the LINQ methods (which themselves use foreach behind the scenes), .NET invokes this class’s GetEnumerator method. This returns a new instance of IEnumerator<string>, which again has been auto-generated by the .NET compiler and implements the body of the ReadLines method. Thus the two separate calls to Take above both create an instance of the enumerator, and it’s that instance that has the bulk of the file-reading behaviour in it – hence this code gets executed twice.

It is relatively rare that this is the behaviour you actually want.

• If this is the output you want, you probably don’t want to actually read the file twice. The standard pattern to prevent this is to add a .ToList() to the line that creates lines. That way you fully evaluate the iteration once, and use the regular list of results at the end.

• If you actually want to return the first line, and then the second line, you’ll need to implement this explicitly. For example:

  var firstTwoLines = ReadLines(filename).Take(2).ToList();
  Console.WriteLine(firstTwoLines[0]);
  Console.WriteLine(firstTwoLines[1]);
  

Lazy evaluation

The iterator block examples used above are an example of lazy evaluation. This is a useful concept in functional programming and allows you to, for example, implement infinite lists, or just avoid executing expensive code until it’s strictly necessary.

Lazy evaluation can help reducing coupling in your code. Coupling is where one module depends on another module’s code. Consider the infinite list of even numbers; without using lazy evaluation, you would need to pass the number of even numbers required into the method as a parameter. You have to complicate your even number code (albeit only slightly), to take into account the requirements of the caller. Consider what happens if, rather than taking the first 10 even numbers, you want to ask for “all the even numbers less than 100”? That requires different code in your method – the change to how you use the list of numbers has caused a change to the code that creates the list. Lazy evaluation via the iterator block avoids this – you just implement an infinite list, and let the calling code deal with the consequences.

There are two risks to bear in mind. Firstly, you might accidentally try to consume an infinite list. While in many cases your list won’t be infinite, so this concern won’t apply, you might still run into the “multiple evaluation” problem (the example above where we accidentally create the StreamReader twice).

Secondly, you lose control over precisely when your code gets executed. When it’s just generating a list of numbers that’s fine. But suppose you had some other code that created the file whose lines are read by ReadLines. The behaviour of the ReadLines iterator will vary depending on whether you create the file before, during or after you do a foreach over the output from ReadLines – and this will happen at some arbitrary time, outside of the control of the code in the ReadLines method. There are new and unusual failure cases to consider, such as what happens if the file gets deleted half way through the operation. If you’re building some code that uses lazy evaluation, make sure you think about what will happen when the code actually executes, not just when you call into the iterator block in the first place.

LINQ

We have used several examples of LINQ methods in the examples above, and you have probably used it in your earlier programming as well. Let’s briefly review what LINQ actually is.

LINQ stands for Language INtegrated Query. It was originally used mostly for providing a more fluent language for reading from databases, akin to the Structured Query Language used by database engines such as Microsoft SQL Server. However, it rapidly evolved into a more general functional approach to dealing with lists of data in C#.

LINQ consists primarily of a library of methods on IEnumerable<T>. These are all functional in nature (they don’t allow side-effects). The most common and most useful are:

• Where – filter a list
• Take and Skip – use or discard the first n elements in the list
• First and Last – pick the first or last element in the list
• Count – count how many elements there are in the list (optionally only those matching some condition)
• Contains – test whether a list contains a particular value
• Select – create a new list by applying some operation to each element in the original list, in turn
• Aggregate – iterate over the list maintaining a “running total” type result
• GroupBy – group the elements in a list into sub-groups based on some criterion
• OrderBy – create a new list containing the elements of this list sorted into some order
• ToList, ToArray and ToDictionary – convert this list into a List<T>, array, or Dictionary<TKey,TValue>

There are many more. Most of these are fairly straightforward and you can see how they work just by playing about. We’ll consider Aggregate and GroupBy in a bit more detail below since they’re harder to get to grips with.

Those familiar with similar concepts in other programming languages, or mathematics, may recognise Where as filter, Select as map and Aggregate as fold.

Note that in the descriptions above, we have referred to “lists”. In fact, there is nothing special about a “list” in this context – we mean anything that implements IEnumerable<T>. That might be a List<T>, or it might be some special object that represents a database access layer. It might even be an array, since the compiler recognises arrays as implementations of IEnumerable<T>.

Aggregate

The Aggregate operation (also known as fold, or fold left) is used to apply some operation to each element in turn, maintaining a “running total” as you go. The final result is the value of that running total at the end of the list.

Here’s an example of how to add up all the integers in a list (although note that in practice you would use the equivalent LINQ method Sum!):

var sum = list.Aggregate(0, (acc, v) => acc + v);

To break this down:

• The 0 is the “seed” – the starting value of our running total. If there are no elements in the list, this is the value that gets returned.
• The (acc, v) => acc + v is our aggregation function. Here it’s a lambda expression, but it could be any method reference. This gets executed once for each item in the list in turn; for the first item we pass in 0 for acc and the first item in the list as v; then we pass in the result of that call as acc for the next item in the list, and so on.

This can be a useful and concise way of expressing certain operations on lists. It’s a way of squishing all the values in the list down into a single result, taking just one element at a time.

GroupBy

GroupByallows you to create subsets of a list based on some criteria. For example, consider the following list:

var apples = new List<Apple>
{
  new Apple { Colour = "Red", Poisoned = true},
  new Apple { Colour = "Red", Poisoned = false},
  new Apple { Colour = "Green", Poisoned = false}
};

Suppose you wanted to group the apples together by colour. You would achieve this as follows:

var groups = apples.GroupBy(apple => apple.Colour);

Console.WriteLine(groups.Count());

var redApples = groups.Single(grouping => grouping.Key == "Red");
Console.WriteLine(redApples.Count());

The first WriteLine will print “2” – there are two groups, one of red apples and one of green. The second WriteLine will print “2” as well – there are two apples in the red group.

The return value fromGroupBycan be a little confusing. It’s anIEnumerable<IGrouping<TKey,TSource>>. In other words, a “list of groupings”. Each “grouping” has aKeyproperty which returns the key value that caused all the items in that grouping to be grouped together. Confusingly there’s noValuesproperty or equivalent – theIGroupingitself isIEnumerableand hence you just iterate over the grouping itself to see its contents:

Console.WriteLine(redApples.Key);
foreach (var apple in redApples)
{
  Console.WriteLine(apple.Poisoned);
}

GroupBy is often most useful in conjunction with ToDictionary, since you can use it to create a lookup table:

var applesLookup = apples
                    .GroupBy(apple => apple.Colour)
                    .ToDictionary(grouping => grouping.Key, grouping => grouping);
Console.WriteLine(applesLookup["Red"].Count());

Note that the ToDictionary call needs two things, a way to work out the dictionary key (the same as the grouping key in this case), and then a way to work out the dictionary values (here, the grouping itself, i.e. the list of apples of this colour). The grouping => grouping can in fact be omitted in this case – using the contents of the input list as the values in the dictionary is the default behaviour.

Query comprehension syntax

The LINQ examples we have used here are written in standard C# syntax. There is an alternative “query comprehension syntax” which endeavours to look rather more like the SQL typically used to query databases. So you could replace this:

var poisonedRedApples = apples.Where(apple => apple.Colour == "Red").Select(apple => apple.Poisoned);

with this:

var poisonedRedApples =
  from apple in apples
  where apple.Colour == "Red"
  select apple.Poisoned;

This rarely adds significantly to readability, but might be recommended by some coding standards. You should at least be aware of the existence of this syntax, so you can understand it if you see it.

Other things you can use LINQ on

As mentioned earlier, LINQ is not restricted to use on simple C# data structures such as lists. One classic use case is in talking to SQL databases, via “LINQ to SQL”. Given some suitable db object representing your database, and assuming you have a Users table, you could write this:

db.Users.Where(user => user.Name == "John")
        .Select(user => user.LastLogin);

For all intents and purposes, this works in exactly the same way as the same LINQ operators on a list.

However, behind the scenes something more subtle is going on. Using list operations would require fetching the entire Users table from the database into memory, which is potentially a very expensive operation. SQL databases allow much more efficient operations, such as SELECT LastLogin FROM Users WHERE Name = 'John'. The above C# will actually be translated by LINQ to SQL into this efficient SQL query, rather than being executed as a list operation.

How does this work? In short, because the Where method in this case (which is actually on IQueryable<T>, not IEnumerable<T>) doesn’t take a Func<User,bool> as you might expect, but an Expression<Func<User,bool>>. The Expression type tells the compiler to pass the C# code expression user.Name == "John" into the method, instead of evaluating that expression and creating a function as instructed by the lambda expression. The Where method can then pick apart this C# code and convert it into the equivalent database command.

Inevitably this limits the expressions you’re allowed to pass in (you must use a simple lambda expression such as the example, not a more complex method call). But it’s an impressively powerful feature.

Further reading

Microsoft Virtual Academy’s A Guide to Object-Oriented Practices course has a section on Functional Concepts which covers some of this material.

Learning C# 3.0 has some slightly dated material on LINQ in Chapter 21.

Head First C# provides a more up-to-date examination of LINQ in Chapter 14, although focussing primarily on the “query comprehension syntax”.

Other programming paradigms

A programming paradigm is a way of structuring and expressing the code that implements a software development solution. This module has been focused on the functional programming paradigm, and it should be clear how that differs from other ways of programming that you’re familiar with. There are many other programming paradigms, but the following are the most important at this stage of your learning.

• Procedural
  • Code is structured as a set of procedures
  • This is a form of imperative programming, which means that the steps that the computer needs to follow are expressed in order
  • In procedural programming, you approach a problem by deciding how the necessary logical steps should be divided up
  • This used to be the dominant programming paradigm, before the widespread adoption of object-oriented programming
• Object-oriented
  • Code is structured using classes and objects
  • As explored in the Object-Oriented Programming module, some of the strengths of this approach are:
    • Encapsulation of an object’s properties (data) and behaviour (methods) into a single entity
    • Abstraction, which means hiding details of an object’s implementation behind its interface
    • Inheritance of properties and methods from an ancestor class
    • Polymorphism, through which an object can be interacted with as if it were an instance of an ancestor class, while it behaves according to its actual class
  • In object-oriented programming, you approach a problem by dividing it up into entities (objects) that have particular properties and behaviour
  • This is a very popular programming paradigm for general-purpose software development, particularly as there are OO patterns for many common situations – e.g., MVC (Model-View-Controller) is an OO pattern for application development
• Functional
  • As this module has explored, code is structured using functions
    • As much as possible, functions are pure and do not have side effects (input/output are exceptions to this)
    • Programs are made up of functions composed together so that the output of one is the input for another
    • This can make programs more readable
  • In functional programming, you approach a problem by breaking down the computations into stateless (pure) functions comprised of other functions
  • Functional programming is especially suited to complex manipulation of large amounts of data
• Event driven
  • Code is structured as units that are executed in response to particular events
  • We will see some event driven programming in the Further JS: the DOM and Bundlers module, because the JavaScript code that runs in a web browser is executed in response to events (e.g., when a button is clicked or an API call responds)
  • In event driven programming, you approach a problem by identifying the events and defining the response to each one separately; the important concept to keep in mind is that the “flow” of the program logic is controlled by external events
  • This is particularly suited to game development and device drivers

It used to be the case that each programming language had a particular paradigm that needed to be followed. There are still some languages like that, but many modern languages support multiple paradigms – as this module and the Object-Oriented Programming module have shown.