The AntiChris

Ever since reading Joel’s Can Your Programming Language Do This?, I’ve been obsessed with Functional Programming, and with my shiny new hammer, everything looks like a nail. A few months ago, I got it into my head that it’d be a good idea to implement Map, Filter, and Reduce in .NET 1.1. It was actually simple enough to do, albeit in no way type-safe, and still vulnerable to side effects. Naturally, I named the library QAFP (Quarter-Assed Functional Programming), since it was half-half-assed. As an example, here was my Map function:

public delegate object MapFunction(object obj);

public static IList Map(IList list, MapFunction func)
{
    if (null == list || null == func)
    {
        return null;
    }

    IList mappedList = new ArrayList(list.Count);

    foreach (object o in list)
    {
        mappedList.Add(func(o));
    }

    return mappedList;
}

public object Square(object obj)
{
    int i = (int) obj;

    return i * i;
}

public void MapTest()
{
    IList numbers = new ArrayList(5);

    for(int i = 1; i <= 5; i++)
    {
        numbers.Add(i);
    }

    numbers = Map(numbers, Square);
    // list should now contain [1,4,9,16,25]
}

It was ugly, but it worked. Pass it a list of mixed items and forget to do your type checking, and you’re boned. It wound up being very useful, and cut down on some of our development time, until we finally moved up to .NET 2.0. I know all of this stuff is old news to those of you using .NET 3.5 and LINQ, but given that we’ve just updated to 2.0, 3.5 is a long way off for us, so bear with me. If you’re stuck using .NET 2.0, you may enjoy this.

The upgrade to half-assed functional programming came with generics and anonymous delegates. Since side-effects are still possible, it’s not pure functional programming, but it’s close enough to be very useful, as long as you’re careful with it. The new code doesn’t look all that different, but it’s much safer, and any type errors should be caught by the compiler. Here’s the new Map function:

public delegate TOutput MapFunction<tinput, TOutput>(TInput obj);

public static void Map<tinput, TOutput>(List<tinput> inputList, MapFunction<tinput, TOutput> func, out List<toutput> outputList)
{
    outputList = new List<toutput>();

    if (null == inputList || null == func)
    {
        return;
    }

    outputList.Capacity = inputList.Count;

    foreach (TInput obj in inputList)
    {
        outputList.Add(func(obj));
    }
}

public int Square(int i)
{
    return i * i;
}

public void MapTest()
{
    List<int> numbers = new List<int>(5);
    List<int> squaredNumbers;

    for(int i = 1; i <= 5; i++)
    {
        numbers.Add(i);
    }

    Map(numbers, Square, out squaredNumbers);
    // list should now contain [1,4,9,16,25]
}

Filtering a list is also needed quite a bit, and the generic List<T> in .NET 2.0 already has this covered, through the use of Predicates. A Predicate is basically a function that takes an object of type T, and returns true or false if it matches some criteria. Combine that with List<T>’s FindAll function, and it’s easy to return a list of Ts matching that criteria. I still wrapped everything in a filter function, just to ensure no empty lists or missing predicates. As an example, to strip out all odd numbers from a list:

public static List<tinput> Filter<tinput>(List<tinput> inputList, Predicate<tinput> func)
{
    if (null == inputList || null == func)
    {
        return null;
    }

    return inputList.FindAll(func);
}

public List<int> GetEvenNumbers(List<int> numbers)
{
    return Filter(numbers, delegate(int i){ return (i % 2) == 1; });
}

Last, but certainly not least, is Reduce, also known as foldr to those of you who speak with a LISP. For those not in the know, it performs an operation on each item in the list and the total (or aggregate) of every item before it, starting with an initial value for the total. The way this total is implemented is completely up to you, as you can see below:

public delegate TAggregate ReduceFunction<tinput, TAggregate>(TAggregate aggregate, TInput obj);

public static TAggregate Reduce<tinput, TAggregate>(List<tinput> inputList, ReduceFunction<tinput, TAggregate> func, TAggregate initialValue)
{
    TAggregate aggregate = initialValue;

    inputList.ForEach(delegate(TInput input) {
        aggregate = func(aggregate, input);
    });

    return aggregate;
}

public int Sum(int total, int i)
{
    return total + i;
}

public int Product(int total, int i)
{
    return total * i;
}

public StringBuilder Concatenate(StringBuilder sb, string s)
{
    return sb.AppendFormat("{0}", s);
}

public void TestReduce()
{
    List<int> numbers = new List<int>(5);

    for(int i = 1; i <= 5; i++)
    {
        numbers.Add(i);
    }

    int sum = Reduce(numbers, Sum, 0);
    int product = Reduce(numbers, Product, 1);

    List<string> strings = GetListOfStringsToConcatenate();

    StringBuilder sb = new StringBuilder();

    sb = Reduce(strings, Concatenate, sb);
}

Now, where and why would you use this? Functional Programming is usually used for math-intensive applications, but like I said, everything looks like a nail. To improve network performance, when making remote function calls, we don’t send entire objects if we only need their ID number. So, given a list of patients, let’s say we want to find those with fatal allergies, to keep them from falling into our strategically placed peanut, grass, and pet dander bins (let’s also say we’re witch doctors).

public List<int> GetAllergiesForPatientsAboveSeverity(List<int> patientIDs, Severity severity)
{
    List<patient> patients;
    List<int> allergyIDs;

    Map(patientIDs, GetPatientObjectFromID, out patients);

    List<allergy> allergies =
        GetAllAllergiesForPatients(patients)
        .Filter(delegate(Allergy allergy) {
            return allergy.Severity >= severity;
        });

    Map(allergies, GetAllergyIDFromObject, out allergyIDs);

    return allergyIDs;
}

public List<allergy> GetAllAllergiesForPatients(List<patient> patients)
{
    // Grab the allergies for the given patients…
}

public Patient GetPatientObjectFromID(int patientID)
{
    return PatientCache.Find(delegate(Patient p) { return p.ID == patientID; };
}

public int GetAllergyIDFromObject(Allergy allergy)
{
    return allergy.ID;
}

We’d end up only sending a few ints to the server, and getting a few ints in return. Why is this important? Hell if I know, I just think it’s elegant code, if a contrived example. So, if you’re stuck with .NET 2.0 for the moment, like I am, and you’re into Functional Programming, give this a shot. I’m sure you’ll find all sorts of nails you never noticed before.