In functional programming, fold (also termed reduce, accumulate, aggregate, compress, or inject) refers to a family of higher-order functions that recursively combine elements of a data structure using a function.

To In this article we’re going to be focusing on loops that make use of an accumulation variable, for example:

  • Sum of values
  • Product of values
  • Concatenation (sum of strings)

Scenario 1: Sum of Integer Values

We have an array of integers and need to return their combined sum.

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
using System;

namespace Functional
{
  internal class Article2
  {
    internal int sum(int[] values)
    {
      int accumulator = 0;
      foreach (int value in values) {
        accumulator += value;
      }
      return accumulator;
    }
  }

  class MainClass
  {
    public static void Main(string[] args)
    {
      Article2 art2 = new Article2();
      Console.WriteLine(art2.sum(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 })); 
    }
  }
}
OUTPUT : Scenario 1: Sum of Integer Values
45

Ok, quite easy. We created a pure function with a values parameter to accept an array of integers to be summed; but what if instead of summing the values, we need to find the product of the values.

Scenario 2: Product of Integer Values

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
using System;

namespace Functional
{
  internal class Article2
  {
    internal int product(int[] values)
    {
      int accumulator = 1;
      foreach (int value in values) {
        accumulator *= value;
      }
      return accumulator;
    }
  }

  class MainClass
  {
    public static void Main(string[] args)
    {
      Article2 art2 = new Article2();
      Console.WriteLine(art2.product(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 })); 
    }
  }
}
OUTPUT : Scenario 2: Product of Integer Values
362880

Ok, again a fairly easy task… but did you notice how much of the code is similar between the sum and product functions? Essentially we only changed the name, and these two lines:

C#
1
2
var accumulator = 0     --->  var accumulator = 1
accumulator += value    --->  accumulator *= value

The rest of the code is essentially duplication.

Ok, but how can we do this in a more “functional way”?

I say “more functional way”, because if you look at both of the above functions; they meet the requirements of a Pure Function, i.e. no side effects.

Well…, so let’s frame this question slightly differently: how can functional techniques assist us to reduce the amount of code duplication. So for this section we’re going to use a Higher-order Function;

Fold (reduce, accumulate, aggregate).

This takes a function, a collection of items and returns a value that is created by combining the items.

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
using System;
using System.Linq;

namespace Functional
{
  class MainClass
  {
    public static void Main(string[] args)
    {
      Console.WriteLine(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 }
                        .Aggregate(0, (total, value) => total + value));

      Console.WriteLine(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 }
                        .Aggregate(1, (total, value) => total * value));
    }
  }
}
OUTPUT : Fold (reduce, accumulate, aggregate)
45
362880

Huh?

I agree it’s less code, … but how exactly does that work, confused?

What’s is most likekly confusing the picture a bit is that we’ve chosen to use some Syntactic Sugar; shortened syntax within a programming language that is designed to make things easier to read or to express. Before we try to understand what’s going on; let’s first remove the sugar and reveal the expanded version:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <vector>
#include <numeric>
#include <functional>

int main() {

  // For the sake of legibility, I'll declare an initialised vector.
  std::vector<int> v{1, 2, 3, 4, 5, 6, 7, 8, 9};

  std::cout << std::accumulate(v.begin(), v.end(), 0, 
        [](int total, int value) { 
            return total + value; 
        }) << std::endl;
  
  std::cout << std::accumulate(v.begin(), v.end(), 1, 
        [](int total, int value) { 
            return total * value; 
        }) << std::endl;

  return 0;
}

Ok, so let me help you with understanding of this; we basically have a function called

  • aggregate
  • accumulate
  • array_reduce
  • fold
  • reduce

that operates on a list of values (the array) and also takes two additional parameter values:

  • The Initial or starting value; which in this case is 0 for sum, and 1 for product.
  • A Closure (or a block of code to process the values); this closure receives two values: total & value; to which we then apply an operator, for example: + for sum, and * for product.

Process: operation-by-operation:

The process starts with an initial value of 0 for the accumulator. The closure is then iteratively passed the current accumulator and the next value in the sequence, the closure then returns the sum of the accumulator plus the value; the result is then stored in the accumulator; overriding the previous value.

Reducing Process

Underlying Operational Code

Too further alleviate any confusion, let’s have a look at a function for this:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static TSource Aggregate<TSource> (
    this IEnumerable<TSource> source, 
    Func<TSource, TSource, TSource> func)
{
  Check.SourceAndFunc (source, func);

  // custom foreach so that we can efficiently throw an exception
  // if zero elements and treat the first element differently
  using (var enumerator = source.GetEnumerator ()) {
    if (!enumerator.MoveNext ())
      throw EmptySequence ();

    TSource folded = enumerator.Current;
    while (enumerator.MoveNext ())
      folded = func (folded, enumerator.Current);
    return folded;
  }
}

Huh?… it’s quite a complicated function; however let’s ignore most of that and focus in on the just the middle part:

C#
1
2
3
4
TSource folded = enumerator.Current;
while (enumerator.MoveNext ())
  folded = func (folded, enumerator.Current);
return folded;

Does this seem at all familiar? Go back and look at the two functions (sum & product) that we defined at the beginning of this article. Yes, it’s essentially the same process; the only key differences here are:

- use of a enumerator to step through the sequence as opposed to the `foreach` - a closure called `func` that receives two parameters: - `folded`; the accumulated value - `enumerator.Current`; which is the last value retrieved from the sequence.
C#
1
folded = func (folded, enumerator.Current);

Let’s look again at our expanded single line solution for sum:

C#
1
2
Console.WriteLine(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 }
                        .Aggregate(0, (total, value) => total + value));

The passed in closure (or block of code) refers to this part:

C#
1
(total, value) => total + value)

This basically says, we receive two values total, value, and then proceed to add them together total + value. This is a rudimentary example of a block of code (closure); far more complex logic and/or process can be performed in a closure. The only restrictions is that your block of code at the end, conforms to type of the closure:

C#
1
2
3
public static TSource Aggregate<TSource> (
    this IEnumerable<TSource> source, 
    Func<TSource, TSource, TSource> func)

i.e. We are provided two values; we add our processing code and finally we received a TSource, which is just a generic placeholder for the return value (the accumulated result). To further understand this function definition you should refer to Microsoft’s .Net definition: https://msdn.microsoft.com/en-us/library/bb548651(v=vs.110).aspx.

Conclusion

Whew, ok that’s enough for this article… I really hope you’re were able to follow along; please feel free to ask for more examples if you need them, even for more clarity on anything that you’re struggling with.

Performance Note:

It's also important to appreciate that the underlying code for Higher-order Functions are built by the compiler teams of each language, meaning they would have taken additional steps to ensure that this code is highly optimized.

Bonus

As a bonus we’re going to include code on how to solve the first Euler challenge using:

  • aggregate
  • accumulate
  • array_reduce
  • fold
  • reduce

The problem is as follows:

Multiples of 3 and 5: If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

The solution is intentionally hidden, to give you an opportunity to try this yourself. Click on the Show / Hide button to see our solution.

The solution:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
using System;
using System.Linq;

namespace Functional
{
  class MainClass
  {
    public static void Main(string[] args)
    {
    Console.WriteLine(Enumerable.Range(1, 999)
      .Aggregate(0, (total, value) => total + 
        (value % 3 == 0 || value % 5 == 0 ? value : 0)));
    }
  }
}

…and that’s it, until next time.

Thanks to Xennox for contributing some of the C++, JavaScript and Python code examples.