Fun with folding

Fold is a general purpose ‘higher order function’ (HoF) that combines the members of a list in some way, for example to count, add, or concatenate them. Most modern programming languages support Fold, though sometimes with a different name. (In this post I’ll use Python, in the main text but will append C# and VB equivalents at the bottom or as comments)

From the above description it is easy to conclude that Fold is only of interest when you are explicitly processing a list. But another interesting use is to calculate mathematical functions that are defined by some kind of series. A nice example is calculating factorials, like this:

def factorial(x) :

  return reduce(lambda a,b : a *b, range(1,x+1))

Notes:

• This factorial function doesn't use either a procedural loop or recursion!
• reduce is Python’s version of Fold (I’m deliberately avoiding getting into the difference between ‘fold left’ and ‘fold right’)
• lambda a,b : a *b is a 'lambda' - a way to define an ‘anonymous’ function (not given a name) ‘in line’. Read this code as ‘given a and b, return a times b'. Here, the lambda is given as the first argument to the reduce function.  (We could have just use the mul operator, but I introduced a lambda because we’re going to need another later.)
• range generates a list of numbers in a specified range (at least, that’s a good enough quasi-explanation for understanding this code). In Python, the upper bound of the range is ‘exclusive’ hence x+1.
• Try calling e.g. factorial(5)

Lots of functions in mathematics are defined by a ‘Taylor series’, usually written as a capital sigma specifying the sum of terms from n=0 (or sometimes 1) to infinity. In practice, only the first few terms are needed for most purposes.

We could implement this for a specific series using the range and fold/reduce functions as above but lets reinforce the practice that we should write a function for each part of the calculation that we could re-use elsewhere, hence:

def sigma(fr, to, f) :

  return reduce(lambda a,b : a + f(b), range(fr,to+1),0)

The first two parameters specify the ‘from’ and ‘to’ (inclusive) range for n. The third, f, is a function that will be applied to each value of n.

Note that we have added a third argument to the reduce function: 0. This is known as the ‘seed’ value. This way the first time the lambda is called within reduce it will be called with a as 0, and b as the first value of n (to which the function will be applied). Without specifying a seed, the function f would not get applied to the first value in the specified range.

We can call sigma with a pre-defined function, but we will again use a lambda. Try this, and make sure you understand what the result represents

sigma(1,4, lamba n : n**2)

Now let’s combine our first two functions and write a function to calculate the Sine of a number (in radians), using the Taylor series: 

def sin(x) :

  return sigma(0,6, lambda n : (-1)**n*x**(2*n+1)/factorial(2*n+1))

test this by calling e.g. sin(pi/4)

Notes:

• This is definitely not an efficient implementation. There are many ways it can be made far more efficient that you can explore. 
• We have ‘hard wired’ this function to calculate the first seven terms of the series only. Try altering this number to see how many iterations are needed to match the accuracy of the in-build Sin function.
• You could change the function signature so that as well as specifying x, you specify the number of terms to evaluate – according to your application need.

C# version of code examples:

int Factorial(int x) => Enumerable.Range(1, x).Aggregate((a, n) => a * n);

Notes;
1. I am using 'expression syntax' - a very terse and elegant way to write a function that returns the value of a single  expression. If your C# version does not support this, change it to:

int Factorial(int x) 
{
    return Enumerable.Range(1, x).Aggregate((a, n) => a * n);
}

2. Aggregate is C#'s equivalent to Fold/reduce.

3. (a, n) => a * n is C# syntax to define a 'lambda' 

4. Unlike Python, the Enumerable.Range upper limit is inclusive.

double Sigma(int fr, int to, Func<int, double> f) => Enumerable.Range(fr, to).Sum(f);

Note: Sum is actually a more specific implementation of the Fold concept.

double Sin(double x) => Sigma(0, 6, n => Math.Pow(-1, n) * Math.Pow(x, 2 * n + 1) / Factorial(2 * n + 1));

VB version of code examples:

    Function Factorial(x As Long) As Long

        Return Enumerable.Range(1, x).Aggregate(Function(a, n) a * n)

    End Function

Notes:

1. Aggregate is VB's equivalent to Fold/reduce.

2. Function(a, n) a * n is VB syntax to define a 'lambda' 

3. Unlike Python, the Enumerable.Range upper limit is inclusive.

 

    Function Sigma(fr As Integer, [to] As Integer, f As Func(Of Integer, Double)) As Double

        Return Enumerable.Range(fr, [to]).Sum(f)

    End Function

Notes:

1. [to]  is in square brackets because to is a reserved word in VB. i have kept it for consistency with other examples, but you could change this parameter name to something else if preferred.

    Function Sin(x As Double) As Double

        Return Sigma(0, 7, Function(n) Math.Pow(-1, n) * Math.Pow(x, 2 * n + 1) /
                                                                                                                  Factorial(2* n + 1))

    End Function