In the
last installment of Functional C#, I covered a bit about creating delayed evaluation lists based upon unfolding constructs and generating lists from external resources. Those are some of the higher level high order functions you can do in C#, but let's look at a few more, plus those that are already available to us in .NET 3.5. We'll take samples from F# and show that some of them already exist in the base class libraries and you can use them today without having to reinvent any wheels.
Iterators
One of the most simple operations in functional programming is just the simple iterator. In F#, we have two ways of iterating through any given list or sequence, by index or through the enumerator. Below are simple examples in F# doing just that:
[1..10] |> List.iteri(fun i j -> printfn "%d - %d" i j) // By index
[1..10] |> List.iter(fun i -> printfn "%d" i) // By enumerator
If we inspect the List<T> class and the Array class, we'd find that we have methods that does the enumerating by using the enumerator that looks like this:
List<T>:
void ForEach<T>(Action<T> action);
Array:
static void ForEach<T>(T[] array, Action<T> action);
So, that I could iterate a list much like this:
Enumerable.Range(1, 10).ToList().ForEach(Console.WriteLine);
One thing I thought was critically missing from the IEnumerable<T> class was the ForEach or Iterate as the F#'er in me would say. Implementing one is pretty simple using the C# 3.0 techniques:
public static void ForEach<T>(this IEnumerable<T> items, Action<T> action)
{
if (items == null)
throw new ArgumentNullException("items");
if (action == null)
throw new ArgumentNullException("action");
foreach (var item in items)
action(item);
}
But, what about by index? IEnumerable<T> has no such concept of this, so it doesn't really do us any good to try. But, it works very nicely with IList<T> or System.Array. Let's do both just for grins.
public static void IterateIndex<T>(this T[] items, Action<int, T> action)
{
if (items == null)
throw new ArgumentNullException("items");
if (action == null)
throw new ArgumentNullException("action");
int lower = items.GetLowerBound(0);
int upper = items.GetUpperBound(0);
for (int idx = lower; idx < upper; idx++)
action(idx, items[idx]);
}
public static void IterateIndex<T>(this IList<T> items, Action<int, T> action)
{
if (items == null)
throw new ArgumentNullException("items");
if (action == null)
throw new ArgumentNullException("action");
for (int idx = 0; idx < items.Count; idx++)
action(idx, items[idx]);
}
And then we can do a simple iteration this way:
Enumerable.Range(1, 10).ToArray().IterateIndex((i, j) => Console.WriteLine("{0}-{1}", i, j));
Like I said, nothing too complex here. But, let's get more advanced, shall we?
Folding
In the functional programming world, the
fold, also known as reduce and accumulate, is a family of high order functions that process a data structure in a given order and build up a return value. The data structure processed in this type of function is usually a list of some sort. They are pretty powerful which help you avoid a lot of looping and recursion in your code. These functions are in direct contrast to the unfold function that I talked about last time which took a function to generate a list.
In the F# world, we have a couple of ways about thinking about folds, we have support for both left and right folds. The Seq.fold function is applied from a left to right fashion as is the List.fold_left function. The List.fold_right function is the inverse which applies from the right to left. The Seq does not have this as it is a forward only evaluated collection much like IEnumerable<T>.
Some basic examples in F# would look like this:
[1..10] |> Seq.fold(fun acc x -> acc + x) 1
[1..10] |> List.fold_left (fun acc x -> acc + x) 1
Or using simple operator function such as sum would look like this:
[1..10] |> Seq.fold (+) 1
Where the basic structure is:
val fold_left : ('b -> 'a -> 'b) -> 'b -> 'a list -> 'b
The fold right example would look something like this:
List.fold_right max [3; 5; 7; 9; 1; 2;] System.Int32.MinValue
Where we'd want to get the maximum value from our given list, and the Int32.MinValue is our accumulator.
Where the basic structure is:
val fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b
So, how would we implement this in C#? Let's do a simple implementation of fold (or fold_left) in C#. It's a rather easy implementation. Let's first do one for IEnumerable<T> and then for IList<T>:
public static T Fold<T, U>(this IEnumerable<U> list, Func<T, U, T> func, T acc)
{
foreach(var item in list)
acc = func(acc, item);
return acc;
}
Enumerable.Range(1, 10).Fold((acc, x) => acc + x, 1);
And now for the IList<T> would look something like this:
public static T FoldLeft<T, U>(this IList<U> list, Func<T, U, T> func, T acc)
{
for (int index = 0; index < list.Count; index++)
acc = func(acc, list[index]);
return acc;
}
new List<int> { 1, 2, 3, 4, 5 }.FoldLeft((acc, x) => acc + x, 1);
Seems simple enough where we keep executing the function with the accumulator and the current item in the collection until we are complete. The same implementation can also be said for the FoldRight function which does the reverse of
public static T FoldRight<T, U>(this IList<U> list, Func<T, U, T> func, T acc)
{
for (int index = list.Count - 1; index >= 0; index--)
acc = func(acc, list[index]);
return acc;
}
int foldRight = new List<int> { 5,9,1,3,4,3 }.FoldRight((acc, x) => Math.Max(acc, x), int.MinValue);
Where the answer would be 9 as the maximum number.
But, wait! Don't we already have these things in .NET 3.5? With LINQ, the answer is yes, well, partly. Let's look at the
Enumerable.Aggregate function:
public static TAccumulate Aggregate<TSource, TAccumulate>(
this IEnumerable<TSource> source,
TAccumulate seed, Func<TAccumulate, TSource, TAccumulate> func)
And an implementation might look like this:
Enumerable.Range(1, 10).Aggregate(1, (acc, x) => acc + x);
So, as you can see, it solves the Fold and FoldLeft operations, but does not cover the case of FoldRight, unless I were to somehow use the Reverse extension method also available on Enumerable class. But of course that could be bad if my collection were infinite...
Filtering
Another idea from F# is the filter function. This gives us the ability to filter a given collection by the criteria given. The function looks like this:
val filter : ('a -> bool) -> 'a list -> 'a list
And a simple implementation would look like this:
let mod3List = [1..100] |> List.filter(fun x -> x % 3 = 0)
But, how would we do something similar. Let's mock something up in C# using extension methods.
public static IEnumerable<T> Filter<T>(this IEnumerable<T> source, Predicate<T> func)
{
foreach (var item in source)
{
if(func(item))
yield return item;
}
}
Enumerable.Range(1, 100).Filter(x => x % 3 == 0);
That's great, but... we already have that in .NET 3.5 once again through LINQ, so no need to reinvent the wheel here either. Instead, let's look at the
Enumerable.Where method:
public static IEnumerable<TSource> Where<TSource>(
this IEnumerable<TSource> source,
Func<TSource, bool> predicate)
And then I can write my function as follows:
Enumerable.Range(1, 100).Where(x => x % 3 == 0);
So, once again, the core libraries have a lot of the functional programming things in mind already that we can take advantage of. Let's look at one final one for this installment.
Mapping
The map function in functional programming is to take a function and apply it to each item in the collection. The function will look like this:
val map : ('a -> 'b) -> 'a list -> 'b list
let cubeList = [1..100] |> List.map(fun x -> x * x * x)
Now, let's prototype how this might look in the C# world to implement something like this:
public static IEnumerable<TResult> Map<T, TResult>(this IEnumerable<T> source, Func<T, TResult> func)
{
foreach (var item in source)
yield return func(item);
}
var cubes = Enumerable.Range(1, 100).Map(x => x * x * x);
But once again, .NET 3.5 and LINQ already solved this problem as well. The
Enumerable.Select method already implements this very logic:
public static IEnumerable<TResult> Select<TSource, TResult>(
this IEnumerable<TSource> source,
Func<TSource, TResult> selector)
This allows me to rewrite my function so that it looks like this:
var cubes = Enumerable.Range(1, 100).Select(x => x * x * x);
Wrapping It Up
As I gave examples above, many of the functional programming functions that are a given in the FP world have already been implemented in .NET 3.5, albeit under different names. Once again, I'll emphasize that C# is an "ok" language to understand functional programming aspects and let's you get over one hop of the programming style without having to learn the new language. But, to get the full breadth of what functional programming can do for you in terms of pattern matching, type inference, generic functions, immutability and so on, F# is the real option in the .NET world.
