Recently, I googled my first name. The search yielded some startling results. Not only was I surprised to find my modest blog on the front page, but... well... see for yourselves.

Sadly, soon after came the inevitable smack down.

It's on. Now that I've had a taste of power, I'm willing to go to great lengths to quench my thirst. Look out Hoffman! I don't care if you are my namesake...

You're next Screech. No bell will save you this time.

Last month, I was scheduled to speak at the Findlay Area .NET Users Group (FANUG), but the meeting was canceled due to weather. This month, my good friends Jason Follas and Greg Huber were scheduled to speak, but a last-minute conflict has thrown a monkey wrench into the works. After passing a few emails back and forth, Jason and Greg have decided to reschedule. Instead, I'll be giving my Functional C# talk in Findlay tomorrow night. I hope to see you there!

Title: Functional C#

Abstract: In recent years, many features have been added to the C# language that make it possible to write programs using techniques from other programming paradigms. Chief among these is functional programming. Often regarded as only being academically useful, functional programming has many practical uses, some of which appear within the .NET Framework itself. In this session, we'll examine some ideas taken from functional programming and see how they might be implemented using language features that already exist within C#. In addition, we'll highlight ways in which the .NET Framework APIs borrow from functional programming.

A few days ago, my friend Michael Letterle (the artist formerly known as Michael.NET) twat the following tweet:

The story Michael referred to is Landon Dyer's "Donkey Kong and Me" blog post, which chronicles his conversion of the Donkey Kong arcade game to the 8-bit Atari 400/800 systems. (Screenshots and a review of the port can be found here.) A fascinating yarn, Dyer's post evokes a feeling of nostalgia for the swashbuckling coder days of more than two decades ago. His recent post about the development of the Atari ST is equally enjoyable.

I've often shared Michael's sentiment. Sometimes, I feel like I was born a bit too late. At the advanced age of 0x20, I am fascinated by stories of the Herculean coding efforts of those who came before me—the original early adopters. (Although, there's a strong argument that the present day is just as, if not more, exciting.) Perhaps the most interesting aspect of tech history is how our forefathers were forced to invent creative solutions for just about everything. For me personally, that's what makes "Donkey Kong and Me" so much fun. The same appeal can be found in the early-Macintosh hardware-tweaking stories at Andy Hertzfeld's Folklore.org.

To fuel my interest in computer tech history, I've recently begun re-reading its bible: Programmers At Work.

Published in 1986, this book features interviews with an amazing array of programmers, including figures like Gary Kildall, Charles Simonyi, Jaron Lanier and even Bill Gates. It's out-of-print but can still be purchased used. (I "borrowed" my water-damaged copy from my father's bookshelf). Thankfully, Susan Lammers, the author, has recently started a "Programmers At Work" blog where she's posting the original interviews. So, if you can't find the book, these classic interviews should all be available soon.

What interesting tech history articles or books have you read recently?

Yesterday, I attended the Microsoft Detroit Launch Event and the Geek Dinner that immediately followed. (Important thanks go to Microsoft for graciously picking up our food tab at the Geek Dinner.)

What a blast! It was exciting to visit with old friends and meet new people. Here are a few shout-outs:

• James Bender: Night elves are totally lame. You need to re-roll on WoW dude. Really, I'm kidding. Let's get together on Dalaran sometime.
• Amanda DaPanda: I feel so bad that I wasn't following you on Twitter. The issue has been corrected. Let's talk some more about F#. Do you have a blog?
• Michael Eaton: Someday you'll make it to a Metallica show.
• Keith Elder: Awesome Geek Dinner! Thanks for setting this up. Also, thank you for suggesting that I use Windows Live Writer. I am a changed man.
• Jason Follas: Thanks for driving, hanging out and being such an all-around amazing guy.
• Steven Harman: Your T-shirt was fantastic, and our discussion about Ruby was illuminating.
• Nate Hoellein: It was good talking F# with you again.
• Jim Holmes: Still nursing the wounds of your defeat at DevConnections, eh? As always, it was a joy to see you.
• Josh Holmes: Your advice was a blessing. It was wonderful to slow down and spend a little time together.
• Ryan and Joel Lanciaux: It was cool finally meeting you guys in person. It's amazing that our lives have so many connections.
• Michael Letterle (the artist formerly known as Michael.NET): I really do like your new handle and blog theme.
• Jeff McWherter: Sorry for my huge faux paux! I'll make it up to you.
• David Redding: It was a horrible feeling to realize that you are actually five years younger than me.
• Chris Woodruff: Where the heck were you? You were missed.
• Jay Wren: I keep forgetting that you're easily the funniest person I know.

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 this¹:

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.

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

Google has released Google Calendar Sync, which will automatically sync your Google Calendar to and from Microsoft Outlook. As an avid user of both calendars, I rushed to download and install the tool. It installed quickly, accepted my Google Apps email, and was ready to go. However, after the first sync, I was puzzled as to why the items from Google Calendar hadn't shown up in Outlook yet. I tried a few manual syncs, but still nothing happened.

I have to admit that I rarely read instructions before installing software, so I had missed the following important information on the Google Calendar Sync: Getting Started page, which reads:

"Keep in mind that it's not possible to sync events on secondary calendars at this time. Google Calendar Sync will only sync events from your primary Google Calendar and your default Microsoft Outlook calendar."

Ugh. I didn't notice my events coming into Outlook because I don't have much in my primary Google Calendar. I was expecting to see everything come into Outlook, but the tool doesn't actually support that.

Are they serious about this? So, I can't use multiple color-coded calendars in Google Calendar? That's right. Any events not on the primary calendar will simply not be synced. And of course, the problem exists on both sides. If you happen to use multiple calendars in Outlook, you're out of luck.

To make matters worse, the tool doesn't handle event collisions very well. So, if the same event exists in each calendar before the first sync, you'll wind up with two items in both calendars. Yup. If you have "St. Patrick's Day" in your Google Calendar and Outlook, you'll find two "St. Patrick's Day" events in each after syncing for the first time.

C'mon Google, you can do better than this! Supporting only the most basic use case isn't enough. I need a tool that does it all with the ease-of-use that I've come to expect from Google's tools. I don't need a tool that 1) requires babysitting, or 2) limits the number of features that I can use.

Somebody please let know when this really works. Until then, it's uninstalled.

Help! I've painted myself into a corner. While writing articles for this series, I try very hard to introduce only a little F# syntax at a time. It is a personal goal of mine not to use syntax that hasn't already been introduced in a previous article. Because of this, my hands are now tied. You see, I have some very cool articles in the queue, but I simply cannot post them until I've introduced (what is arguably) the most fundamental data structure in functional programming: the list.

In functional programming (and F#), lists are actually linked lists of the singly-linked variety. As a classic data structure, the linked list should be familiar to any programmer. In the everyday imperative world, a linked list is simply a group of nodes (or "cells"). Each node represents a value in the list and contains a pointer to the next node. The main benefit of a linked list is that insertion and removal are, asymptotically, O(1) operations. ([ed.] The use of large computer science terms helps the author to feel smarter than he actually is.) In other words, insertion and removal are constant time operations whose performance is not affected by the number of items in the list.

The lists of functional programming are very different from their imperative cousins. For instance, functional lists are recursive data structures.¹ A functional list is really just a value (or the "head") and another list (or the "tail"). Consider a list containing the elements 1, 2, and 3. In the functional world, that would be a list with 1 as its head, and a tail containing a list with 2 as its head, and a tail containing a list with 3 as its head, and a tail containing the special "empty list"—which has no head or tail. Did you get all that? No? Well, a picture is worth a thousand recursive words:

In the above diagram, lists are represented by boxes, and their heads are represented by circles.² The empty list is represented by the square containing the special value, []. Because all of those boxes are pretty cumbersome to draw, we'll use diagrams like the one below. However, the diagrams are equivalent.

Make sense so far? OK, enough jibber-jabber! Let's see some syntax.

As you can see, the F# syntax is nearly identical to the diagrams above. We even have to append the empty list explicitly. In fact, the F# interactive environment complains if we forget.

Thankfully, F# provides a more compact syntax for declaring lists. Just place the contents inside of square brackets, separated by semi-colons—no empty list required.

There are lots of other ways to declare lists in F#. Many of you will be pleased to know that range expressions are supported.

In addition, powerful list comprehensions are available.

As I stated earlier, the lists of functional programming (and hence, F# lists) are very different from imperative linked lists. Another fundamental difference is that F# lists are immutable. Once created, the contents of an F# list can't be changed³—that is, nothing can be added or removed.

Wait. Stop. Didn't I state at the beginning of this very article that the primary benefit of linked lists is fast insertion and removal? If a list can't be changed, haven't we lost the primary motivation for using a linked list in the first place? Well, yes and no.

If we were hoping to use an F# list like an imperative linked list, immutability is deal-breaker.⁴ However, if we use an F# list in a more functional style, our goals are different, and immutability actually helps us achieve those goals. One primary goal of functional programming is to avoid side effects—e.g., when a function modifies some bit of state in addition to returning the value of a calculation. If values are immutable, many side effects aren't even possible. However, it is possible to perform basic operations with an immutable list. Such operations (e.g., insertion and removal) return a new list. Let's look at a simple example: appending two lists.

Appending lists in F# is trivial. In fact, F# even provides a special @ operator to do the trick.

You see? Trivial.

OK, let's define a couple of lists.

At this point, our lists look like the following diagrams:

Now, let's append the two lists, creating a new list.

So, what do our lists look like now?

(Downshiftng to the imperative world...)

In the imperative world, linked lists support mutation. If we append two linked lists, the result must be a new list containing a copy of every node. The new list cannot share nodes with the original two lists. Why? Because node sharing would mean that any mutation to the original lists would mutate the new list.

(Shifting gears back to the functional world...)

In the functional world, lists are immutable. This means that node sharing is possible because the original lists will never change. Because the first list ends with the empty list, its nodes must be copied in order to point its last node to the second list. After the append operation, our lists look like so:

At this point, the more skeptical among you might be saying, "Well, that's a pretty interesting theory, but can you prove it?"

No problem.

Using the knowledge that F# lists are recursive, we can retrieve the last half of combined (the inner list starting at 4) by taking the tail, of its tail, of its tail. List.tl is the function that F# provides for extracting a list's tail.

Finally, because F# is first-class citizen of the .NET Framework, we have full access to all of the base class libraries. So, we can use the Object.ReferenceEquals method to test whether or not lastHalf and second are indeed the same instance.

And there you have it. Believe it or not, appending two immutable lists can actually be faster and more memory efficient than appending mutable lists because fewer nodes have to be copied.

Hopefully this is enough to whet your appetites for more information. If so, Nate Hoellein has a series of posts that explore many of the facets of F# lists and the libraries supporting them. Check out his posts here, here and here.

¹The recursive structure of lists in functional programming was discussed in my mind-twisting article, Building Data Out Of Thin Air.
²It might be helpful to visualize the diagram without arrows.
³To be fair, F# lists don't enforce any sort of "deep" immutability. Since F# is a multi-paradigm language that fully supports imperative and object-oriented programming, it is certainly feasible to stuff an F# list full of mutable objects.
⁴If you really want to use a mutable linked list in F#, you don't have to look any further than the .NET Framework. Just use the System.Collections.Generic.LinkedList<T> class.