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...
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.
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:
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.
compare can do most of the heavy lifting and greatly decreases the amount of code we have to write.
That's much better!
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.
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:
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.
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:
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.
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:
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:
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).
Or, we could sort lists by the sum of each inner list (using List.fold_left with the + operator to perform the sum).
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.
Page rendered at Sunday, May 19, 2013 10:02:44 PM (Pacific Standard Time, UTC-08:00)
If feel a bit behind and need to catch up on WPF, this is the book.
Great book on F# containing from Beginner to Advanced. It even has chapters on more arcane features of the language, such as Computation Expressions and Quotations.
Because this book provides source code in Standard ML, it's a fantastic
resource for learning F#. One bit of warning: this book does not teach classic
data structures. While structures such as binomial heaps and red-black trees
are presented, it is assumed that the reader already knows and understands
The opinions expressed herein are my own personal opinions and do not represent
my employer's view in any way.