Recently on Twitter, I’ve stated that many times when explaining these functional programming terms that we don’t get the real reason why, and I hope with some of these posts in the future to change that perception.* Instead of just showing you some examples, I’ll try to step from imperative to functional.*

In my previous adventure “Fun With Folds”, I explained a bit about folds as well as a challenge to rewrite some standard Haskell prelude functions as folds in both Haskell and F#.* After this, I thought to myself that I’d give myself another challenge, this time to implement several functions as folds in C# using the Aggregate operator.*

Aggregate / Fold in LINQ



If you recall from the previous post, I explained the basic notion of folds.* A fold is a higher-order function that knows how to reduce a given a sequence of elements into a single return value.* We could describe it as* doing something to each value in the list, updating an accumulator as we go, and returning the value of the accumulator when we’re finished.* There are two sorts of folds, a left fold and a right fold. The difference is the way the data is "folded".

The LINQ Aggregate function is an implementation of a left fold.* Let’s look at the signatures of the Aggregate overloads to get an idea of how they work:

// Apply an accumulator function over the sequence
public*static TSource Aggregate(
* this IEnumerable source,*
* Func func);

// Apply accumulator with initial seed
public*static TAccumulate Aggregate(
* this IEnumerable source,*
* TAccumulate seed,*
* Func func);

// Apply accumulator with initial seed and projection
public*static TResult Aggregate(
* this IEnumerable source,*
* TAccumulate seed,*
* Func func,*
* Func resultSelector);
So, what can we do with this knowledge?* Some of the easy LINQ operators that you can implement with a left fold are Sum and Count.* Let’s implement each with a set of tests to verify behavior.

Count

The first item is to calculate the number of all items in the list.* Traditionally, in a more imperative coding style, you might calculate it in the following style:

public*static*int CountItems(
*** this IEnumerable items)
{
*** var count = 0;
*** foreach (var _ in items)
******* count++;

*** return count;
}
Instead, we could implement as a left fold in order to reuse existing higher-order functions and write in a bit more functional style.* Let’s write a test to verify the behavior of our CountItems and the Count LINQ operator.* Since these can be described as purely functional, we could write them as property-based checks ala QuickCheck.* Alas, QuickCheck does not exist for C#, so instead, we could do one better and use Pex to generate our test data and use xUnit.net to do our assertions.* Our code might look like the following:

[PexClass(typeof(Extensions))]
public*partial*class ExtensionsSpecs
{
*** [PexMethod]
*** public*void CountItems_should_equal_Count(
******* [PexAssumeNotNull]int[] items)
*** {
******* Assert.Equal(items.Count(), items.CountItems());
*** }
}

public*static*class Extensions
{
*** public*static*int CountItems(this IEnumerable source)
*** {
******* return source.Aggregate(0, (acc, x) => 1 + acc);
*** }
}
*
What this allows us to do is generate a non-null array of integers to test whether the property of my CountItems should always equal the Count function.* We can then run Pex to verify this behavior.* But, getting back to the CountItems function, we simply seed the length with a 0 and then with the accumulator and our current index, we add 1 to the accumulator which is then returned.* Sum

The second easy LINQ operator you can implement as a fold would be the Sum function.* This function simply adds all of the numbers from the sequence together from left to right.* Typically in an imperative coding style, it might look like the following:

public*static*int SumNums(this IEnumerable<span style="color:blue;"int/span> items)
{
*** var acc = 0;
*** foreach(var item in items)
******* acc += item;

*** return acc;
}
Once again, we can eliminate the foreach loops with a fold once again in a manner very similar to above.* While using Pex, we can write our property based tests and our implementation as follows:

[PexClass(typeof(Extensions))]*
public*partial*class ExtensionsSpecs*
{*
*** [PexMethod]
*** public*void SumInt_should_equal_Sum(
******* [PexAssumeNotNull]int[] items)
*** {
******* Assert.Equal(items.Sum(), items.SumInt());
*** }
}*

public*static*class Extensions*
{*
*** public*static*int SumInt(this IEnumerable<span style="color:blue;"int/span> source)
*** {
******* return source.Aggregate(0, (acc, x) => x + acc);
*** }
}
This time, instead of adding one to the accumulator, we are adding the current item.* We are using a seed of 0 because if the list is empty, there will be no proper return value.* These are interesting, yet simple examples of how you can use higher-order functions to express simple operations and lets you lose that for/each loop.

But, let’s move onto the real challenge.

The Challenge

The challenge this time is to implement other standard LINQ operators that are a little bit more challenging to express as folds.* These functions are:

  • Map (Select LINQ Operator)
  • Filter (Where LINQ Operator)
  • Append (Concat LINQ Operator)
  • Flatten (C# Implementation of the F# Seq.concat library function)
Map

The map higher-order function applies a given function to a sequence of elements and returns a sequence of the results.* In LINQ, this has been implemented as the Select function.* Typically, using sequences, a map might be implemented as follows:

public*static IEnumerable Map(
*** this IEnumerable items,*
*** Func func)
{
*** foreach (var item in items)
******* yield*return func(item);
}
But, just as above with the other LINQ functions, we can express this one as a fold, moreover, a right fold.* In the previous post, I showed how to express a factorial as a right fold using the LINQ Aggregate function, so we’ll apply some of that same logic in this instance.

[PexClass(typeof(Extensions))]*
public*partial*class ExtensionsSpecs*
{*
*** [PexMethod]
*** public*void Map_should_equal_Select(
******* [PexAssumeNotNull]int[] items)
*** {
******* Func<span style="color:blue;"int/span, span style="color:blue;"int/span> multiplyByTwo = x => x * 2;

******* Assert.Equal(
*********** items.Select(multiplyByTwo).ToArray(),
*********** items.Map(multiplyByTwo).ToArray());
*** }
}*

public*static*class Extensions*
{*
*** public*static IEnumerable Map(
******* this IEnumerable items, Func proj)
*** {
******* return items.Aggregate(
*********** x => x, (f, c) => x => f((new[] { proj(c) }).Concat(x)))
*********** (Enumerable.Empty());
*** }
}
* Don’t be alarmed at what you see here.* What you need to pay attention to is inside the f function which applies the projection to c and then concatenates it to the accumulator.* You also will notice we seeded the function with an empty result list.* We can run Pex and it will verify the results that indeed they produce identical results when we apply the multiplyByTwo function to all items in the sequence* Why a right fold?* We want to work our way from the right on the empty sequence and pre-pend our projected result onto it, this producing our sequence in proper order.

Filter

The next higher-order function we can represent is the filter function.* This function processes a given list to produce a new list which contains only those element satisfied by the predicate function.* In LINQ, this function is expressed as the Where function.* Typically, we could express this using a foreach loop much as we have with the other solutions such as this:

public*static IEnumerable Filter(
*** this IEnumerable items,*
*** Func pred)
{
*** foreach(var item in items)
******* if(pred(item)) yield*return item;
}
Instead, we could apply the lessons we learned from above and implement this as a right fold as well.* Let’s review what that might look like with associated test to verify our behavior.

[PexClass(typeof(Extensions))]**
public*partial*class ExtensionsSpecs**
{**
*** [PexMethod]
*** public*void Filter_should_equal_Where(
******* [PexAssumeNotNull]int[] items)
*** {
******* Func<span style="color:blue;"int/span, span style="color:blue;"bool/span> isEven = x => x % 2 == 0;

******* Assert.Equal(
*********** items.Where(isEven).ToArray(),
*********** items.Filter(isEven).ToArray());
*** }
}**

public*static*class Extensions**
{**
*** public*static IEnumerable Filter(
******* this IEnumerable items,*
******* Func pred)
*** {
******* return items.Aggregate(
*********** x => x, (f, c) => x => f(pred(c) ? (new[] { c }).Concat(x) : x))
*********** (Enumerable.Empty());
*** }
}
*
We can test our behavior by applying a isEven function to the list to return only even numbers.* Once implemented, we can turn the lamp green by implementing the filter function much as we did above.* The difference is we apply the predicate function to c, and if true, we concatenate to the accumulator, else we return the accumulator.* As you will also note, we seed the accumulator with an empty sequence.* Once we understand the pattern here, this gets easier.* The reasoning for using a right fold is exactly the same as above.*** Append

The append function is a function that takes two lists and appends the second to the first.* In LINQ, this is implemented as the Concat function.* I don’t really like the name that they used as to me, Concat means flatten, which we’ll get to next.* Anyhow, since this is a more difficult function to express as I have above for the map and filter, let’s skip ahead to our implementation.*

[PexClass(typeof(Extensions))]***
public*partial*class ExtensionsSpecs***
{***
*** [PexMethod]
*** public*void Append_should_equal_Concat(
******* [PexAssumeNotNull]int[] left,*
******* [PexAssumeNotNull]int[] right)
*** {
******* var expected = left.Concat(right);
********
******* var result = left.Append(right);

******* Assert.Equal(
*********** expected.ToArray(),*
*********** result.ToArray());
*** }
}***

public*static*class Extensions***
{***
*** public*static IEnumerable Append(
******* this IEnumerable source,*
******* IEnumerable other)
*** {
******* return source.Aggregate(
*********** x => x, (f, c) => x => f((new[] { c }).Append(x)))(other);
*** }
}
You’ll start to notice a pattern here.* Why am I using a right fold?* In order to append properly, we start with the other sequence and work our way from the right, pre-pending the rightmost item from the source sequence.* We can use Pex to verify this behavior as well.* I hope you’re starting to see a pattern in these examples.

Flatten

The final example is the flatten function.* This function takes a sequence of sequences and flattens it to a single sequence.* In F#, we use the Seq.concat function to express this.* As this is a more involved implementation, I won’t bore you with the details of how it can be simply implemented, so let’s skip ahead to our implementation.

[PexClass(typeof(Extensions))]****
public*partial*class ExtensionsSpecs****
{****
*** [PexMethod]
*** public*void Flatten_should_concat_inners(int[][] items)
*** {
******* PexAssume.IsNotNull(items);
******* PexAssume.TrueForAll(items, x => x != null);

******* // Calculate length of array with fold
******* var length =*
*********** items.Aggregate(0, (acc, x) => acc + x.GetLength(0));

******* Assert.Equal(length, items.Flatten().Count());
*** }
}****

public*static*class Extensions****
{****
*** public*static IEnumerable Flatten(
******* this IEnumerable items)
*** {
******* return items.Aggregate(
*************** x => x, (f, c) => x => f(c.Concat(x)))
*************** (Enumerable.Empty());
*** }
}
My test was to ensure that the number of items in the resulting sequence is equal to the sum the length of each item in the array.* Our implementation is much like the Append example above, the difference being that the c parameter is now a collection itself, so we can call the Concat method to append the x accumulator.

Conclusion

So, what did we learn here?* By understanding the basic nature of folds, we can understand what problems it can solve for us.* Were some of the examples above the most efficient?* Probably not, but it does give you a basic understanding of how powerful a fold can be.* By applying our knowledge of higher-order functions, we can create a lot of function reuse and rid ourselves of the explicit iterator patterns, explicit recursion and so on.*

Programming in the small is where functional programming fits best and with this knowledge in hand, we can create concise and composable functions in a much more declarative manner.* C# can be an interesting language to teach some fundamental functional programming concepts as over time, it has gained more and more functional features.* Is it the best fit to apply such things as partial application and currying?* Probably not, as it isn’t automatic and requires some work, but if we understand the basic high-order functions, we can get very far in our learning.

In a future post, I’ll get more into testing with Pex in contrast to the FsCheck and QuickCheck implementations I’ve done in the past with my Functional Programming Unit Testing series.* The ideas of testing our pure algorithmic code is a powerful story and I want to explore that further in both C# and F# alike.



More...