Friday, March 14, 2008

Recently, I was refactoring some trivial F# code, and the results were so elegant that I felt it would be instructive to share them. My tale begins simply with a list of lists...

> let lists = [[1;2];[5;6;7];[9;10];[3;4];[8]];;

val lists : int list list

Now, suppose we wanted to sort lists by the lengths of the inner lists. How might we do that? Easy! The F# libraries include a List.sort function which does the trick.

val sort: ('a -> 'a -> int) -> 'a list -> 'a list

List.sort takes two arguments. The first argument is a function used to compare elements from the list, and the second argument is the list to be sorted. Obviously, most of the work is in defining the first argument. This comparison function returns a negative value if the first element is less than the second, a positive value if the second element is less than the first, or zero if the two elements are, in fact, equal. With that in mind, we could sort lists using List.sort and List.length like so:

> List.sort (fun x y -> if (List.length x) < (List.length y) then -1
-                       elif (List.length x) > (List.length y) then 1
-                       else 0) lists;;

val it : int list list = [[8]; [1; 2]; [9; 10]; [3; 4]; [5; 6; 7]]

OK. It worked, but that's an awful lot of code. Typing all of that into the F# Interactive Environment is fraught with peril ([ed.] the author spelled "length" as "lentgh" at least twice).

Thankfully, F# provides a function, compare, which can be used to calculate a generic comparison of two arguments.

val inline compare: 'a -> 'a -> int

compare can do most of the heavy lifting and greatly decreases the amount of code we have to write.

> List.sort (fun x y -> compare (List.length x) (List.length y)) lists;;

val it : int list list = [[8]; [1; 2]; [9; 10]; [3; 4]; [5; 6; 7]]

That's much better!

NeRd Note
Did you know that the .NET Framework also provides an API for generic comparison? For types that implement IComparable or IComparable<T>, System.Collections.Generic.Comparer<T>.Compare() can handle the dirty work!
int CompareGuids(Guid x, Guid y)
{
  return Comparer<Guid>.Default.Compare(x, y);
}

Our sort is looking pretty good, but we can do better. Let's take a closer look at the comparison function we're passing to List.sort.

(fun x y -> compare (List.length x) (List.length y))

What exactly are we doing here? Essentially, we're inserting a function application for each argument before calling compare. It sure would be nice to have a function that generalizes this for us. Perhaps something like this:

let inline compareWith f x y = compare (f x) (f y)

I can already sense the snickers. Some of you are thinking, "How could that possibly work? There aren't any types! How would F#'s statically-typed compiler handle that?"

The answer to my hecklers is yet another reason why I love F#: automatic generalization. If necessary, F# will attempt to insert generic type parameters into a function as part of its type inference. This allows very sophisticated code to be written with breathtaking succinctness. The following code shows automatic generalization in action.

> let inline compareWith f x y = compare (f x) (f y);;

val inline compareWith : ('a -> 'b) -> 'a -> 'a -> int

As you can see, F# allows us to define the essence of a function without the noise of type annotations. It looks very similar to code written in dynamically-typed languages, but has all of the benefits of static-typing.

Armed with our new compareWith function (any chance of getting that into the libraries Don?), we can sort lists using List.length like so:

> List.sort (fun x y -> compareWith List.length x y) lists;;

val it : int list list = [[8]; [1; 2]; [9; 10]; [3; 4]; [5; 6; 7]]

But wait! There's more!

I intentionally inserted what I consider to be a sophomoric blunder in that last bit of code. Try to find it. Notice that both of the parameters of our anonymous comparison function are passed, in order, as the last two arguments of compareWith. That's a big clue. Here's another. Consider the signatures of List.sort and comparewith. I'll highlight the interesting bits.

val sort: ('a -> 'a -> int) -> 'a list -> 'a list

val inline compareWith : ('a -> 'b) -> 'a -> 'a -> int

Do you see it? compareWith returns a function whose signature matches the signature of the comparison function expected by List.sort. In essence, the anonymous function is an extra "function layer" that really isn't necessary. Instead, we could write this1:

> List.sort (compareWith List.length) lists;;

val it : int list list = [[8]; [1; 2]; [9; 10]; [3; 4]; [5; 6; 7]]

This an excellent example of the benefits of currying and partial application (and yet another reason why I love F#). If you need to brush up, I've written about these topics in the past here, here and here.

There is one final bit of refactoring that I'd like to do. Notice how lists appears at the very end of the argument list for List.sort. We can make the code more readable by moving lists ahead of List.sort and using the forward pipe operator (|>) like so:

> lists |> List.sort (compareWith List.length);;

val it : int list list = [[8]; [1; 2]; [9; 10]; [3; 4]; [5; 6; 7]]

Now the code reads like an English sentence:

"Take lists and sort it, comparing with List.length."

It's a tiny jump to see that other functions could be easily used to sort lists. For example, we might sort using the head of each inner list (assuming that none of the inner lists is the empty list).

> lists |> List.sort (compareWith List.hd);;

val it : int list list = [[1; 2]; [3; 4]; [5; 6; 7]; [8]; [9; 10]]

Or, we could sort lists by the sum of each inner list (using List.fold_left with the + operator to perform the sum).

> lists |> List.sort (compareWith (List.fold_left (+) 0));;

val it : int list list = [[1; 2]; [3; 4]; [8]; [5; 6; 7]; [9; 10]]

The possibilities are endless!

Next time, we'll take a closer look at the wickedly clever forward pipe operator to see how its very existence hangs upon currying.

1If you don't immediately see why this works, try again. Work it out on paper. The reward is worth the effort.

posted on Friday, March 14, 2008 10:18:34 AM (Pacific Standard Time, UTC-08:00)  #    Comments [1]

kick it on DotNetKicks.com