A few weeks ago, I wrote a simple mini-framework in Java, providing the kind of higher-order functions available to C++ developers. After that, I was asked to hold a short seminar about Higher-Order Functions in a regular OO language by a company Lab49. The languages I chose were Java and C#, which are the languages they use the most.

The seminar consisted of my (sometimes futile) attempt to create a HOF framework from scratch in Java and C#, and constrasting the use of that framework to the more traditional approach to specific problems. Since my Camtasia recording failed, you cannot see that seminar here, but I will create a short version and upload it as a Flash movie soon.

Since I have already talked about HOF in Java before in this blog, I will focus on C# here. This blog post is a quite condensed version of the seminar at Lab49. Again, look out for a new blog post with a recording of the material at that seminar, including comparisons of the "old way" of doing things in C# (and Java) and contrasting it to C++.

Functions to functoids
Most imperative languages - OO languages included - provide two features for dealing with functions:

1. define a function with a specific name
2. apply a named function

This is fine and dandy for most applications - or at least one can get away with it. The problem arises when one wants to apply the same function over and over again, on elements of a collection, for instance, or when one wants to apply some function, but not sure which one yet. This latter problem often occurs in callback or visitor patterns.

So, one needs a way to pass a function around.

Well, what about just supplying a pointer to that function?

That works for simple cases, and (1) only in some, pretty low level, languages, and (2) opens up for quite intricate bugs.

In C, one could do as:

which will yield the following output:

20
100


C++ has extended their idea of "function" to include objects handling being juxtaposed to the left of arguments, like obj(arg1, arg2). I.e., whatever looks like a function is a function. That generic notion is often refered to as functoid to distinguish from regular free functions.

In C#, as in Java, we can only pass around objects and primitiva values, so we have to find a way there as well to have an object mimic the behavior of a function. I.e., to define a proper functoid specification.

In Java, we had no choice but to create an interface with a specific method, such as apply, with the understanding that this particular method is invoked whenever that functoid is to be applied.

In C#, we do have a special kind of object, a delegate, that can do the job. And in C# 2.0, there are two very helpful extensions to the language - at least syntactically - making our lives much easier:

1. methods can be converted to - or wrapped in - proper delegates automatically when needed; this is analogous to the boxing of primitiva values
2. delegates - or the logic contained - can be defined in-place, where the delegate is needed

We will see examples of both these extensions later. One further note: the introduction of generics in the language also applies to delegates, which can now be generic.

We start creating our HOF by defining our functoids:

We only support unary and binary functoids for now.
NOTE: one should distiniguish generic from higher-order, in that it is possible to create a higher-order library that is type-specific - such as constrained to integers. We here use generic delegates to allow for any types for arguments and return type.

It is quite easy to convert simple methods to functiods; in fact, it is often done automatically.

I will cut to the chase and provide a test of this HOF.

// File: TestHof.cs
// Author: David Bergman
//
// This file is testing a mini framework for higher-order functions
// that I implemented during a seminar at Lab49
//
 
using System;
using System.Collections.Generic;
 
public class Test {
 
public static int Add(int m, int n) { return m+n; }
 
public static void Main(string[] args) {

  // Transform strings to ints

  IList<int> myInts = new List<int>();
  // We can provide raw method references, and
  // they will be automatically wrapped into a
  // proper delegate - our chosen functoid type
  // - thanks to a C# 2.0 extension
  Hof.Transform(args, myInts, Int32.Parse);
 
  // Calculate the sum

  int sum = Hof.Accumulate(myInts, 0, Add);

  // Pick max
 
  // We can create a functoid on-the-fly, with inline definition
  // thanks to a C# 2.0 extension
  int max = Hof.Accumulate(myInts, 0,
       delegate(int m, int n) { return Math.Max(m, n); });
 
  Console.WriteLine("Sum is {0}", sum);
  Console.WriteLine("Max is {0}", max);
}
}

Download this code: TestHof.cs

We here see that we use two generic functions: Transform and Accumulate defined in our HOF library. In functional programming corners you should use the terms map and fold. We choose to use the C++ names instead.

Once you have defined the functoids (our Fun1 and Fun2), the rest is pretty easy. There is usually only one notion to define beside functoids to get a proper meta structure for HOF, and that is the iterator. That should give us the most generic sequence the language can offer. In C#, that is IEnumerable.

There is just one last note before I introduce HOF itself, and that is that one cannot alter those IEnumerables. To use C++ lingo: there are no Output Iterators in C#. This means that we have to forego that abstract notion for destination sequences and instead used the tiny more concrete IList. This will, of course, exclude arrays as destinations for these algorithms

Here is the code. Enjoy!

// File: Hof.cs
// Author: David Bergman
//
// This file implements a mini framework for higher-order
// functions that I implemented during a seminar at Lab49
 
using System.Collections.Generic;
 
 
public class Hof {
public delegate R Fun1<R, A>(A n);
public delegate R Fun2<R, A1, A2>(A1 a1, A2 a2);
 
// This function adapter combines two functions.
// This is called "function composition" in FP-land.
public static Fun1<T3, T1> Comp<T1, T2, T3>(
   Fun1<T3, T2> fun1, Fun1<T2, T1> fun2)
{
  return delegate(T1 t) { return fun1(fun2(t)); }
}
 
public static void Transform<T1, T2>(IEnumerable<T1> seq,
			     IList<T2> dest,
			     Fun1<T2, T1> fun
			     ) {
  foreach (T1 t in seq)
    dest.Add(fun(t));
}
 
public static T Accumulate<T>(IEnumerable<T> seq, T start,
			      Fun2<T, T, T> fun) {
  T accum = start;
  foreach (T t in seq)
    accum = fun(accum, t);
  return accum;
}
}

Download this code: Hof.cs