Sunday, December 6, 2009

A bit of F# in your C#

At work, I'm using way more C# than F#.

I have however noticed that functional programming concepts from F# have found their way into my C# code. The first sign of this is when LINQ extension methods start appearing where foreach loops used to be.

F# has a higher-order function called "fold" which can be used for collecting information from a sequence into a single object. A common use is for summing, but it can also be used for extracting one item from the sequence. For instance, it can be used for finding the minimal item according to a specific ordering.

This is a problem Jon Skeet has tackled in a blog from 2005 entitled A short case study in LINQ efficiency.

For instance, given a sequence of pairs of string*number denoting names and ages of people, find the youngest person. Note that we are not only interested in finding the age of the person, we want both the name and the age.

Here is a solution in F# which uses "fold".

let people = [("me", 32.0); ("someoneelse", 75.0)];;
let cmp a b =
match a, b with
| Some (_, a1), (_, a2) when a1 <= a2 -> a
| _ -> Some b;;

let youngest = List.fold cmp None people;;

Function "fold" iterates over each item in the list. For each item, it invokes a function to which it passes the item together with a value called the accumulator. The function returns the new value for the accumulator.

In the example above, the type of the accumulator is "Some person or None", where "None" denotes "no one".

Function cmp simply compares an accumulator with a person, and returns the person if the accumulator is "None", the youngest of the person and the accumulator otherwise.

This solution, when translated to C# 4.0, gives an elegant and efficient solution. I wonder why Jon Skeet did not mention it. If he missed it, he's not alone, a search on Google for how to implement one's own LINQ extension method shows many articles using precisely this problem as illustration.

var people = new Tuple<string, double>[] {
Tuple.Create("me", 32.0),
Tuple.Create("someoneelse", 75.0) };

var youngest =
people.Aggregate(null as Tuple<string, double>,
(youngestSoFar, v) =>
(youngestSoFar != null && youngestSoFar.Item2 <= v.Item2) ?
youngestSoFar : v);

I haven't done any time measurements, but this solution should iterate over the array of people no more than once, and might even be just as efficient as the method using foreach.

1 comment:

Laurent Le Brun said...

Note there's a shorter F# solution:
let youngest = List.minBy snd people

(although it raises an exception on empty list)