Fold - 7 higher order functions

This is the second blog post in a series about higher order functions. Fold is one of my most commonly used higher order function.

• map
• fold
• partition
• reduce
• expand
• collect
• scan

Fold

Fold lets you run an aggregate function over the items in a list to return an aggregated result. This is extremely useful in many scenarios where you wouldn't even think about it. This function already exists in the .NET Framework as part of LINQ, called Aggregate.

Examples

In this example we have a couple of cats from the database and we would like to aggregate their ages. We could map out their age to a list, and then run sum, but that would be traversing the list twice. Using fold is more appropriate here.

var cats = new[]
{
    new Cat(name : "Miss Marple", age : 4),
    new Cat(name : "Mr. Quincy", age : 12),
    new Cat(name : "Darcy", age : 8)
};


cats.Fold((acc, cat) => acc + cat.Age, 0);
// => 24

Here's another less trivial example. Let's say we have a sequence that should be transformed to an array. Sure, the LINQ framework already has this functionality, but it would be interesting to investigate how we could accomplish this with Fold.

private T[] GrowArray<T>(T[] acc, T item)
{
    var newArray = new T[acc.Length + 1];
    acc.CopyTo(newArray, 0);
    newArray[acc.Length] = item;

return newArray;

}

var list = new List<int> { 1, 2, 3 };
list.Fold(GrowArray, new int[0]);
// => [1, 2, 3]

Disclaimer: Don't do this at home. List already has a ToArray function. This was made to illustrate an example with Fold.

Implementation

The implementation of the fold function is pretty straight forward.

public static U Fold<T, U>(Func<U, T, U> fn, IEnumerable<T> list, U init)
{
    if (fn == null)
    {
        throw new ArgumentNullException("fn", "Supplied function to Fold is not allowed to be null");
    }

if (list == null)
{
    throw new ArgumentNullException(&quot;list&quot;, &quot;Supplied list to Fold is not allowed to be null&quot;);
}

var result = init;
foreach (var item in list)
{
    result = fn(result, item);
}

return result;

}

public static U Fold<T, U>(this IEnumerable<T> list, Func<U, T, U> fn, U init)
{
    return Fold(fn, list, init);
}

Loop through the list and accumulate an result.

Conclusion

Both map and fold can take you far, writing code that is easy to test and read by extracting essential logic into their own functions. I've seen so many foreach accumulate code snippets that would be a fold one liner in my days, and I hope this will help anyone to shorten their code and clarify its purpose.