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.

I had resisted advertisements on this blog for a long, long while. It's not that I have anything in particular against ads. I think it's reasonable for a blogger to add advertising to offset the cost (mostly time) of maintaining a solid blog. I just hate it when nice, clean-looking blogs start to look like this:

I suppose that I share a lot of the same sentiments on the subject as Jeff Atwood over at Coding Horror.

About a month ago, I added Google AdSense (at the suggestion of my good friend Keith Elder). I've tried to keep the ads relatively low key in order to keep the clutter down. That doesn't result in as many clicks as it might if I threw them in your faces, but I'm OK with that. I like to keep my layout clean for those who do come in via the web (and not just the feed).

The truth is, I don't trust Google AdSense all that much. Context-sensitive ads are great, but they aren't always accurate. For example, I've mentioned the word "Haskell" several times in reference to the pure functional programming language, Haskell. However, the very use of this relatively uncommon word has triggered Google Ads for the Haskell Indian Nations University. Sigh. It's really hard to get behind advertised products when you're not 100% certain that they'll be relevant to your content.

Recently though, I found a product that I can whole-heartedly recommend. It's a product that falls directly into my demographic of humor-loving, technology-lusting geeks: RiffTrax.

What's RiffTrax you ask? Well, do you remember the TV show Mystery Science Theater 3000¹? That's right. The one with the guy and the robots and the making fun of old B-movies. Well, RiffTrax is that without robots and with blockbusters instead of B-movies. It still has the guy though. In fact, it's the same guy from MST3K.

In essence, RiffTrax are feature-length commentaries in MP3 format that you can purchase, download and sync to your DVDs. Some RiffTrax feature stars and writers from MST3K, and some even have celebrities joining in on the fun. For example, my current favorite is a riff on Jurassic Park that features none other than Weird Al Yankovic.

Pants-wettingly hilarious. Seriously.

Below is a small sampling of the films that have received the RiffTrax treatment. There are lots of others. Some have Jar Jar Binks. Some have Keanu Reeves. All will make you howl with laughter.

Honestly, I don't think of this as advertising. This is a public service announcement. You need this. I promise.

¹Some may have missed out on the delights of Mystery Science Theater 3000 (MST3K). You can catch up here.

Welcome to the eighth article in my series about why I look upon the F# language with the hormone-driven lust of a 16-year old boy. ([ed.] Dustin's trophy wife has indicated that the previous metaphor might be a little too vivid.)

If you're just joining us, below is the path that has brought us to this point.

1. The Interactive Environment
2. Type-safe Format Strings
3. Tuples
4. Breaking Up Tuples
5. Result Tuples
6. Functions, Functions, Functions!
7. Pattern Matching

Today, we're taking a high-level look at F# option types. Option types are a simple example of a discriminated (or tagged) union¹, although understanding that isn't necessary in order to use them. Simply put, an option type wraps a value with information indicating whether or not the value exists. For C# or VB programmers, it may be convenient to think of option types as a mutant cross between .NET 2.0 nullable types and the null object design pattern.

There are two constructors that instantiate option types. First, there's the Some constructor, which takes a value to be wrapped.

And then, there's the None constructor, which doesn't take anything.

One of the properties of option types that makes them so compelling is the ability to pattern match over them.

Now, we can call our isFortyTwo function to show that the pattern matching works as expected.

This is all well and good, but we need a practical example to sink our teeth into. Let's use the .NET Framework Stream.ReadByte function as a guinea pig. ([ed.] Dustin is not implying that you should sink your teeth into guinea pigs. That's disgusting. Shame on you.)

Stream.ReadByte has a pretty bad code smell. First of all, it returns an int instead of a byte. Initially, that should seem strange since the method specifically states that it's a byte generator. ReadByte returns -1 when the current position is at the end of the stream. Because -1 is not expressible as an unsigned byte, ReadByte returns an int. Of course, that's the second problem: extra non-obvious information is encoded into the result value of this function. However, unless you read the documentation, there's no way of knowing that.

By employing an option type, we can clarify the function and be a bit more honest about its result.

Now, the semantics of the function are better expressed thanks to the option type.

In addition, we can write a function that pattern matches over the result of our readByte function.

And here's the above printStream function in action:

Option types provide an elegant way to attach a bit of extra boolean information to a value. It's important to become comfortable with them as they are used extensively throughout the F# libraries.

Have fun! Next we'll explore... well... I haven't decided yet. If you have any suggestions, feel free to email me at dustin AT diditwith.net.

¹We'll explore discriminated unions in a future article.

I don't know about you, but around my house, computer books have a habit of multiplying like rabbits. Sometimes it seems as if you can't put up your feet without resting them on a pile of old programming books. There are several reasons why these books proliferate so:

• I like my shelves to reflect an intelligence that I don't actually possess.
• I feel the need to own reference books that I never need to reference.
• I purchase books on the latest and greatest technology before I realize that I'm not actually interested in said technology.
• When I become interested in a topic, I tend to purchase every book ever written about it—even if a new book duplicates information I already have.
• I buy classics that I have the best intentions of reading... but never do.
• I acquire books for a specific project at work, and the project ends.

Because my shelves are bursting at the seams (and the Wife Acceptance Factor for them has become quite low), it's time for an early Spring cleaning. If you're interested in some reasonably-priced programming tomes, previously owned by a lesser-known blogger, feel free to browse my Amazon storefront.

(Quiz: How many of the books in above picture do you own?)

(Clarification: The books pictured above are not for sale. Those are keepers!)

Greetings fellow F#-philes! Today we're looking at another reason that I am completely infatuated with the F# language—pattern matching.

Pattern matching is a simple idea. Essentially, a pattern match takes an input and a set of rules. Each rule tests the input against a pattern and returns a result if they match.

The following naive implementation of the tired, old Fibonacci function shows simple pattern matching at work.

Pattern matching syntax is simple and clear. It should be readable by any programmer worth their salt. In fact, the above match .. with block is completely equivalent to the following C# switch statement:

That's pretty unimpressive. I mean, if pattern matching were identical to standard switch statements, there really would be nothing exciting about them. Fortunately, there are some enormous differences that demote switch statements to a very distant cousin.

The first difference is subtle but profound: pattern matches return values. A pattern match is very much like a function that takes an argument and returns a value. Consider the following rewrite of our F# fib function:

The above example might be a bit contrived, but it illustrates the point. Simulating that with a switch statement is awkward.

Switch statements don't return values, so we can't assign a switch statement to a variable. Instead, we must use mutable state and pepper the cases with break statements. In essence, a pattern match is like a function while a switch statement is like a big GOTO.

In addition, pattern matching supports a wealth of features that truly set it apart from standard imperative switch statements.

Patterns can:

1. Contain guard rules (e.g. match x but only when x is less than zero).
2. Bind values to names.
3. Decompose type structures.

Let's examine each of these in turn.

First, consider our original fib function with an additional pattern containing a guard rule:

Now that's a bit more interesting! In C# or Visual Basic, we would have to introduce an if-statement at the beginning of the function to test for an invalid argument. In F#, the guard is inserted directly as a pattern rule.

Another indispensible feature of F# pattern matching is the ability to bind values to names.

So far, we've used the match .. with syntax to define pattern matches. This time, we'll use an alternative syntax that, although it is not required, easily demonstrates how values can be bound to names within pattern rules.

The alternative syntax can be used in the case where a function is defined with one argument and simply returns the result of a pattern match on that argument. In this syntax, the argument is not specified, and the keyword function is inserted. The match .. with statement needs to reference the argument name, but because the argument is unspecified, it has no name. Consequently, the match .. with statement must be removed, leaving us with a function that is defined entirely in terms of pattern matching rules. Because the argument is unnamed, values must be bound to names within the pattern rules.

A code sample is worth a thousand words.

In the above code, we bind the name x in each pattern to make up for the fact that the argument is unspecified. In addition, the rules for 0 and 1 and have been combined using an "or" (or "union") pattern. Note that there are two different ways to bind a value to a name within a pattern rule. First, a name can simply be explicitly specified, substituted within the pattern. The other way is to use the as keyword. Both ways are demonstrated above.

The last feature of pattern matching that we'll look at is its capability to decompose type structures.

Recently, we saw that F# would automatically convert the result of Dictionary<TKey, TValue>.TryGetValue to a tuple if a variable isn't specified for the out parameter. In a comment to that article, Derek Slager presented a helper function that returns a default value if TryGetValue returns false. This helper function is an excellent practical example of a pattern match that decomposes a tuple value.

In addition to the tuple decomposition, the first rule elegantly binds the second part of the tuple to the name value. Sweet!

Because pattern matching is intrinsic to F# programming, we'll see more of it in upcoming articles. As features supporting pattern matching are introduced in this series, we'll build on the basics presented here.

Next up: the option type. See you then!

Welcome back for another installment in my series on why I find Microsoft F# to be an exciting language for the .NET platform. If you're just joining us, below are links to the articles in the series so far.

1. The Interactive Environment
2. Type-safe Format Strings
3. Tuples
4. Breaking Up Tuples
5. Result Tuples

I have around 15-20 more articles planned, but I'm always looking for suggestions. If you have a topic idea for the series, feel free to email me at dustin AT diditwith.net.

One of the main reasons that I find F# to be so provocative is that it fully embraces three programming paradigms: functional, imperative and object-oriented. Of these, functional programming is the most favored, mostly due to its OCaml heritage. Because of this, we can't move any further in this series without introducing what functional programming is all about: functions!

In F#, a function declaration consists of the fun keyword, an argument, the -> operator and finally, the function body.

In the F# interactive environment, we can declare a function that takes an argument x and returns its increment like so:

If the -> operator looks strange to you, remember that it's just a divider that separates function arguments from function bodies.

The code above is somewhat equivalent to the following C# 3.0 lambda expression:

Or this VB 9.0 lambda expression:

The biggest difference is that the F# function does not need to be assigned to a .NET delegate (or expression tree) as the C# 3.0 and VB 9.0 lambda expressions do. This is an important point: F# functions are not delegates. They're something else entirely.

Another point of interest is F#'s type inference. We didn't specify a type for x in the function above, but F# determined that x is of type int and that the function returns an int. F# worked this out from the literal 1 that appears in the function body. 1 is an int. Therefore, x must be an int because it is being added together with 1. Finally, the function must return an int since its body returns the result of adding two ints, x and 1.

Because the literal that is added together with x is what triggers the type inference, changing the literal will change the type of the function. For example, changing 1 to 1.0 produces a function that increments floats.

This really isn't anything to write home about. After all, C# 3.0 and VB 9.0 handle type inference similarly for their respective lambda expressions. However, F#'s type inference algorithm is extremely advanced. As this series progresses, you'll see functions without any type annotations that the compiler will successfully type infer, leaving you scratching your head.

At this point, we've successfully declared a function in F#. Unfortunately, we can't use our function yet because it doesn't have a name. We've declared an anonymous function. So, how do we give our function a name? Well, let's back up a little bit to examine some syntax from a previous article.

The above example shows a variable, pair, being defined and assigned a value of (37, 5). The heart of this syntax is the keyword let.

Simply put, let binds a value to a name.

In F#, functions are values. That's a small thing to say, but it has enormous implications. Functions are treated in the same way as any other value. That means that functions can be passed as arguments to other functions, returned by other functions, contained within data structures and bound by names as variables.

Because functions are values, we can give our function the name inc using let.

And, we can call inc like so:

After learning to declare a function of one argument, the next logical step is to declare a function of two arguments. This is actually done with two functions. Consider the code below:

That might look a bit confusing at first. If so, look again carefully. We're declaring a function of one argument, x. This function's body is another function of one argument, y. The body of the inner function is x + y. To call our function, we pass the first argument. That returns the inner function to which we pass the second argument and finally receive the result of the calculation. In essence, calling add requires two function calls. Normally, this is done all at once, as below:

add is an example of a curried function. The idea behind currying is simply transforming a function of multiple arguments into a series of functions that each take one argument. That's all it is. It's not hard. In fact, you can even torture .NET delegates to curry functions in C#. Currying is a simple concept, but it's hard to grasp if you've never encountered it before.

An interesting property of curried functions is the ability to partially apply them. For example, if we pass 1 to our add function above but don't pass the second argument, we are left with a function of one argument that increments by 1. That is, we can define our inc function in terms of add:

Cool!

The reality of our add definition above is that it is far too verbose. It's easy to imagine the nested functions quickly getting out of control when functions of more arguments are declared. For this reason, F# provides a more concise way to declare functions of multiple arguments.

That's better. However, F# provides an even more concise syntax.

That's much better. Note that all three declarations of add are equivalent. Each syntax produces a curried function. In F#, we get currying for free. If you need to declare a function that isn't curried (e.g. to be called easily from C# or VB), you'd use a slightly different syntax. But, that's another article.

I should also point out that F# managed to infer the type of add as int -> int -> int even though there weren't any literals to trigger off of. In future articles, we'll see F#'s type inference algorithm work "miracles" like this over and over again.

Next time, we'll be looking at pattern matching and how it fits into F#. See you then!

As promised, today I'm demonstrating a compelling way in which F# uses tuples to make .NET programming more elegant.

A question that comes up early in F# demonstrations is, "Can I use F# to access code written in my favorite .NET language, <BLANK>?" The answer is an emphatic yes. F# is a first-class .NET citizen that compiles to the same IL as any other .NET language. Consider the following code:

The above code¹ instantiates a new System.Collections.Generic.Dictionary<TKey, TValue> for int and string, and adds three key/value pairs to it. Note that Dictionary is not written in F#. It is part of the .NET base class library, written in C#.

Retrieving values from d is easy. We simply pass the value's key to the dictionary's indexer like so:

However, if we pass a key that isn't found in the dictionary, an exception is thrown.²

Fortunately, Dictionary provides a function that allows us to query using an invalid key without throwing an exception. This function, TryGetValue, has the following signature (shown in C#):

The purpose of TryGetValue is obvious. If key is found, the function returns true and the value is returned in the output parameter³. If key is not found, the function returns false and value contains some throwaway data. The C# code below demonstrates how this function might be used.

So, how can we use this function in F#? Well, there're a few ways.

The first approach is almost exactly the same as the C# version above. First, we declare a variable to pass as the output parameter. Note that this variable must be declared as mutable so TryGetValue can modify it.

Now, we can call TryGetValue, passing v by reference.

OK. That worked but displayed an ugly warning about non-verifiable code. Yikes! Fortunately, F# provides another way to declare variables which support mutation: reference cells.⁴

Declaring a variable as a reference cell is trivial:

We can pass the reference cell into TryGetValue without receiving that nasty warning.

That's much better.

At this point, many of you are probably thinking, "Wait a minute! Wasn't this article supposed to be about tuples? What's all this mutable-variable-output-parameter stuff?" Don't worry. There's a method to my madness. Are you ready?

Consider what happens if we call TryGetValue without specifying a variable for the output parameter:

Did you catch that? When calling a function containing output parameters in F#, you don't have to specify variables for them. The F# compiler will automatically consolidate the function's result and output parameters into a tuple (in this case, a pair). Awesome! If you were paying attention last time, you've probably already realized that we can bind the TryGetValue call to a pattern that extracts the values from the resulting pair.

Now, we can easily query our dictionary using an invalid key without an exception being thrown. Best of all, we don't have to declare an awkward mutable variable to store the value. What takes two lines of code in C# consumes just one in F#.

It is the attention to detail that makes it a joy to code with F#. This is just one example of how F# can consume .NET framework classes in ways more elegant than even C#, the lingua franca of the .NET universe!

I haven't decided what the next article will cover yet. Are there any requests? Feel free to email them to dustin AT diditwith.net.

¹The #light directive in the first line of the code sample enables the F# lightweight syntax. We'll look closer at this in a future article.
²This might be frustrating to users of the System.Collections.Hashtable class from .NET Framework 1.0. Unlike Dictionary, Hashtable returns null when a key isn't found rather than throwing an exception. The reason for this behavior difference is detailed here.
³Normally, I would consider the use of output parameters to be a code smell. However, TryGetValue is an example of a scenario where an output parameter is justified.
⁴We'll be looking more deeply into reference cells in a future article.

Nate Hoellin has a great article on setting up an F# project for TDD with NUnit. Check it out:

Sample setup for Visual Studio 2008 for F# Unit Testing with NUnit