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
 Monday, March 03, 2008
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.1 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:

Simple list (recursive structure)

In the above diagram, lists are represented by boxes, and their heads are represented by circles.2 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.

Simple list

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

> 1::2::3::[];;

val it : int list = [1; 2; 3]

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.

> 1::2::3;;

  1::2::3;;
  ------^^

stdin(16,6): error: FS0001: This expression has type
        int
but is here used with type
        int list
stopped due to error

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.

> [1;2;3];;

val it : int list = [1; 2; 3]

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

> [1..3];;

val it : int list = [1; 2; 3]

In addition, powerful list comprehensions are available.

> [for x in 1..3 -> x * x];;

val it : int list = [1; 4; 9]

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 changed3—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.4 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.

> [1;2;3] @ [4;5;6];;

val it : int list = [1; 2; 3; 4; 5; 6]

You see? Trivial.

OK, let's define a couple of lists.

> let first = [1;2;3];;

val first : int list

> let second = [4;5;6];;

val second : int list

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

Simple lists (before append)

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

> let combined = first @ second;;

val combined : int list

> combined;;

val it : int list = [1; 2; 3; 4; 5; 6]

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:

Simple lists (after append)

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.

> let lastHalf = List.tl (List.tl (List.tl combined));;

val lastHalf : int list

> lastHalf;;

val it : int list = [4; 5; 6]

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.

> System.Object.ReferenceEquals(lastHalf, second);;

val it : bool = true

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.

1The recursive structure of lists in functional programming was discussed in my mind-twisting article, Building Data Out Of Thin Air.
2It might be helpful to visualize the diagram without arrows.
3To 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.
4If 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.

posted on Monday, March 03, 2008 6:24:53 AM (Pacific Standard Time, UTC-08:00)  #    Comments [3]

kick it on DotNetKicks.com
 Monday, February 25, 2008
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) union1, 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.

> let someValue = Some(42);;

val someValue : int option

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

> let noValue = None;;

val noValue : 'a option
NeRd Note
Notice that, in the above code, F# infers the type of noValue as the generic, 'a option, rather than int option. That's because, unlike the declaration of someValue, no information indicates an int. If you really want to declare a None value as type int option, you'd declare it like so:
> let noValue : int option = None;;

val noValue : int option

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

> let isFortyTwo opt =
-   match opt with
-   | Some(42) -> true
-   | Some(_) -> false
-   | None -> false;;

val isFortyTwo : int option -> bool

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

> isFortyTwo someValue;;

val it : bool = true

> isFortyTwo noValue;;

val it : bool = false

> isFortyTwo (Some(41));;

val it : bool = false

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.

> open System.IO
-
- let readByte (s : #Stream) =
-   match s.ReadByte() with
-   | i when i < 0 -> None
-   | i -> Some(Byte.of_int i);;

val readByte : #System.IO.Stream -> byte option

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.

> let rec printStream s =
-   match readByte s with
-   | Some(b) ->
-       printfn "%d" (Byte.to_int b)
-       printStream s
-   | _ -> ();;

val printStream : #Stream -> unit

And here's the above printStream function in action:

> let bytes = [|1uy .. 10uy|];;

val bytes : byte array

> let memStream = new MemoryStream(bytes);;

val memStream : MemoryStream

> printStream memStream;;
1
2
3
4
5
6
7
8
9
10
val it : unit = ()

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.

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

posted on Monday, February 25, 2008 3:56:21 PM (Pacific Standard Time, UTC-08:00)  #    Comments [3]

kick it on DotNetKicks.com
 Tuesday, February 19, 2008
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.

#light

let rec fib n =
  match n with
  | 0 -> 0
  | 1 -> 1
  | _ -> fib(n - 1) + fib(n - 2)

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:

static int Fib(int n)
{
  switch (n)
  {
    case 0:
      return 0;
    case 1:
      return 1;
    default:
      return Fib(n - 1) + Fib(n - 2);
  }
}

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:

#light

let rec fib n =
  let result = match n with
               | 0 -> 0
               | 1 -> 1
               | _ -> fib(n - 1) + fib(n - 2)
  result

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

static int Fib(int n)
{
  int result;
  switch (n)
  {
    case 0:
      result = 0;
      break;
    case 1:
      result = 1;
      break;
    default:
      result = Fib(n - 1) + Fib(n - 2);
      break;
  }
  return result;
}

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:

#light

let rec fib n =
  match n with
  | _ when n < 0 -> failwith "value cannot be less than 0."
  | 0 -> 0
  | 1 -> 1
  | _ -> fib(n - 1) + fib(n - 2)

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.

#light

let rec fib = function
  | x when x < 0 -> failwith "value cannot be less than 0."
  | 0 | 1 as x -> x
  | x -> fib(x - 1) + fib(x - 2)

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.

#light

open System.Collections.Generic

let getValueOrDefault (dict : #IDictionary<'a,'b>) key defaultValue =
  match dict.TryGetValue key with
  | true, value -> value
  | _ -> defaultValue

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!

posted on Tuesday, February 19, 2008 7:39:00 AM (Pacific Standard Time, UTC-08:00)  #    Comments [5]

kick it on DotNetKicks.com
 Wednesday, January 30, 2008

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.

fun arg -> body

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

> fun x -> x + 1;;

val it : int -> int = <fun:clo@0>

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:

x => x + 1;

Or this VB 9.0 lambda expression:

Function(x) x + 1

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.

> fun x -> x + 1.0;;

val it : float -> float = <fun:clo@0>

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.

> let pair = 37, 5;;

val pair = int * int

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.

let name = value

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.

> let inc = (fun x -> x + 1);;

val inc : int -> int

And, we can call inc like so:

> inc 41;;

val it : int = 42

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:

> let add = (fun x ->
-             (fun y -> x + y));;

val add : int -> int -> int

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 37 5;;

val it : int = 42

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:

> let inc = add 1;;

val inc : (int -> int)

> inc 41;;

val it : int = 42

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.

> let add = (fun x y -> x + y);;

val add : int -> int -> int

> add 29 13;;

val it : int = 42

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

> let add x y = x + y;;

val add : int -> int -> int

> add 23 19;;

val it : int = 42

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!

posted on Wednesday, January 30, 2008 7:16:05 AM (Pacific Standard Time, UTC-08:00)  #    Comments [2]

kick it on DotNetKicks.com
 Tuesday, January 29, 2008
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:

> #light
- open System.Collections.Generic
-
- let d = new Dictionary<int, string>()
- d.Add(1, "My")
- d.Add(2, "F#")
- d.Add(3, "Dictionary");;

val d : Dictionary<int,string>

> d;;
val it : Dictionary<int,string> = dict [(1, "My"); (2, "F#"); (3, "Dictionary")]

The above code1 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:

> d.[1];;

val it : string = "My"

> d.[3];;

val it : string = "Dictionary"

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

> d.[4];;

System.Collections.Generic.KeyNotFoundException: The given key was not present in the dictionary.
   at System.ThrowHelper.ThrowKeyNotFoundException()
   at System.Collections.Generic.Dictionary`2.get_Item(TKey key)
   at <StartupCode$FSI_0013>.FSI_0013._main()
stopped due to error

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#):

bool TryGetValue(TKey key, out TValue value)

The purpose of TryGetValue is obvious. If key is found, the function returns true and the value is returned in the output parameter3. 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.

using System;
using System.Collections.Generic;

class Program
{
  static void Main()
  {
    var d = new Dictionary<int, string>();
    d.Add(1, "My");
    d.Add(2, "C#");
    d.Add(3, "Dictionary");

    string v;
    if (d.TryGetValue(4, out v))
      Console.WriteLine(v);
  }
}

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.

> let mutable v = "";;

val mutable v : string

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

> d.TryGetValue(1, &v);;

  d.TryGetValue(1, &v);;
  -----------------^^^

stdin(19,17): warning: FS0051: The address-of operator may result in non-verifiable code.
Use only when passing byrefs to functions that require them.

val it : bool = true

> v;;

val it : string = "My"

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.4

Declaring a variable as a reference cell is trivial:

> let v = ref "";;

val v : string ref

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

> d.TryGetValue(2, v);;

val it : bool = true

> !v;;

val it : string = "F#"

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:

> let res = d.TryGetValue(3);;

val res : bool * string

> res;;

val it : bool * string = (true, "Dictionary")

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.

> let res, v = d.TryGetValue(2);;

val res : bool
val v : string

> res;;

val it : bool = true

> v;;

val it : string = "F#"

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#.

> let res, v = d.TryGetValue(4);;

val res : bool
val v : string

> res;;

val it : bool = false

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.

1The #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.
2This 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.
3Normally, 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.
4We'll be looking more deeply into reference cells in a future article.

posted on Tuesday, January 29, 2008 11:30:29 AM (Pacific Standard Time, UTC-08:00)  #    Comments [3]

kick it on DotNetKicks.com
 Monday, January 21, 2008
Last time, I demonstrated the basics of tuple types in the F# language. However, I (intentionally) failed to answer a couple of important questions about tuples:
  1. Once values are bound together in a tuple, how can they be retrieved?
  2. How are tuples useful?

I'll leave the second question for next time. Today, we'll see how the values of a tuple can be extracted.

Here is the tuple that we began with last time:

> let pair = 37, 5;;

val pair = int * int

> pair;;

val it : int * int = (37, 5)

Extracting the values from this tuple is a simple matter of using the fst and snd functions (which F# held over from its ML heritage). These functions retrieve the first and second values, respectively, from a two-value tuple.

> fst pair;;

val it : int = 37

> snd pair;;

val it : int = 5

The results of these functions also can be assigned to variables.

> let x = fst pair;;

val x : int

> let y = snd pair;;

val y : int

> printfn "x = %d, y = %d" x y;;
x = 37, y = 5
val it : unit = ()

That's great, but what if we need to extract the values from a tuple whose length is greater than two?

> let triple = 2, 11, 29;;

val triple : int * int * int

Is there a thrd function we can use to get the last element out of the tuple above? Nope. In fact, the fst and snd functions that we used on pair won't even work with this tuple. The problem is that those functions are intended to be used only with tuples of two values. This becomes clear when their definitions are considered:

let fst (a,b) = a
let snd (a,b) = b

If we try to use either fst or snd with our triple tuple, a type mismatch error occurs.

> fst triple;;

  fst triple;;
  ----^^^^^^^

stdin(27,4): error: FS0001: Type mismatch. Expecting a
        'a * 'b
but given a
        int * int * int.
The tuples have different lengths
stopped due to error

Fortunately, F# provides a very natural syntax to extract the values from any tuple. The idea is to use a simple let statement. However, instead of binding to a single name, we bind to a pattern made up of several names. For example, we can extract the values from our triple tuple like so:

> let x, y, z = triple;;

val x : int
val y : int
val z : int

> printfn "x = %d, y = %d, z = %d" x y z;;
x = 2, y = 11, z = 29
val it : unit = ()

The obvious follow-up question is, what if we only want to retrieve one or two values from triple? Put another way, is it really necessary to bind each value of a tuple to a name even when we aren't interested in all of the values? The answer is, no, it isn't necessary to bind each value of a tuple of a name. F# provides an ultra-handy wildcard pattern that trivializes this problem. Wildcards allow us to bind only the information that we're interested in by adding "holes" to a pattern. In code, they are represented by an underscore (_) character.

> let x, _, z = triple;;

val x : int
val z : int

> printfn "x = %d, z = %d" x z;;
x = 2, z = 11
val it : unit = ()

Very cool. We'll see more uses of wildcards as this series progresses.

That should answer the first question above. Next time, we'll explore some important uses of tuples that make them very compelling—especially for .NET developers.

posted on Monday, January 21, 2008 7:41:25 AM (Pacific Standard Time, UTC-08:00)  #    Comments [3]

kick it on DotNetKicks.com
 Friday, January 18, 2008
Another feature of the F# language that I crave desperately when writing C# or VB code is F#'s built-in support for tuples. What's a tuple? Simply put, a tuple is an ordered group of values. In one sense, a tuple is very similar to the anonymous types of C# 3.0. The chief difference is that the values in an F# tuple are not named like the properties of a C# anonymous type.
NeRd Note
Most pressing on your mind is likely the question of how one pronounces the word, "tuple." Well, my British friends emphatically point out that it's "too-pull," while my red-blooded, English-language-abusing American friends1 like to say "tuh-pull."2 However, when my British friends speak, they always sound intelligent. I think it has something to do with the accent. So, I'm going with "too-pull." I like to sound smart—especially when it's easy.

In F#, a tuple3 is concisely declared as a let statement with a single name and multiple values separated by commas.

> let pair = 37, 5;;

val pair = int * int

> pair;;

val it : int * int = (37, 5)

Notice that F# infers the type of pair to be int * int. The asterisk (*) doesn't actually mean multiplication in this case. Instead, it indicates that the two types on either side are bound together as one type.

Tuples can contain any number of values, and the values don't have to be of the same type.

> let triple = 0, "F# Rules!", 12.8;;

val triple : int * string * float

Tuples can be compared for equality.

> pair = (29, 13);;

val it : bool = false

> pair = (37, 5);;

val it : bool = true

> pair = (19, 23);;

val it : bool = false

And other comparisons are also legal.

> (1, 1) < (1, 2);;

val it : bool = true

> (2, 1) > (1, 2);;

val it : bool = true

However, tuples with different types cannot be compared. Trying to compare pair, which is of type int * int, with a tuple of type int * string results in an error:

> pair = (0, "F# Rules!");;

  pair = (0, "F# Rules!");;
  -----------^^^^^^^^^^^^

stdin(12,11): error: FS0001: This expression has type
        string
but is here used with type
        int
stopped due to error

In addition, tuples of different lengths cannot be compared.

> triple = (0, "F# Rules!");;

  triple = (0, "F# Rules!");;
  ----------^^^^^^^^^^^^^^^

stdin(13,10): error: FS0001: Type mismatch. Expecting a
        int * string * float
but given a
        'a * 'b.
The tuples have different lengths
stopped due to error

Interestingly, in the above code, the F# compiler doesn't bother inferring the types in the tuple, (0, "F# Rules!"). It is left generic: 'a * 'b. The F# compiler sees that the tuples have a different number of values and stops.

Next time we'll look at some cool ways to use tuples in F# programming.

1Please don't hurt me Keith!
2Usually while sucking down a can of Schlitz.
3too-pull

posted on Friday, January 18, 2008 10:14:39 AM (Pacific Standard Time, UTC-08:00)  #    Comments [5]

kick it on DotNetKicks.com
 Wednesday, January 16, 2008
I'm continuing my series showing ways in which F# is a exciting .NET language. As I mentioned before, if you have any suggestions for future topics please feel free to email them to dustin AT diditwith.net.

While F# can easily access the standard .NET formatting functions (e.g. String.Format()), it also provides its own set of functions for outputting formatted text. In fact, F# offers the a printf-based family of functions that should be familiar to C programmers. Consider the following simple example using F#'s interactive environment.

> printf "%s %d 0x%x %.2f\n" "F# Rules!" 128 128 12.8;;

F# Rules! 128 0x80 12.80

Most of these formatting functions also have an additional "n" version that implicitly adds a new-line character. For example, we could modify the above code to use printfn like so:

> printfn "%s %d 0x%x %.2f" "F# Rules!" 128 128 12.8;;

F# Rules! 128 0x80 12.80

Of course, using an invalid argument will result in an error. Notice what happens if we pass 12 instead of 12.8 for the %f format specifier:

> printfn "%s %d 0x%x %.2f" "F# Rules!" 128 128 12;;

  printfn "%s %d 0x%x %.2f" "F# Rules!" 128 128 12;;
  ----------------------------------------------^^^

stdin(3,46): error: FS0001: The type 'int' is not compatible with any of the
types float,float32, arising from the use of a printf-style format string
stopped due to error

What should give .NET developers pause is the fact that the error above does not occur at runtime. This isn't some exception being thrown—it's a compiler error. In other words, the compiler actually parses and type-checks format strings!

This behavior becomes more useful inside of Visual Studio. When a type mismatch occurs within a format string, the F# background compiler marks the problem with a red squiggly underline:

Type-safe Format String Error

Hovering the mouse over the error will show a tooltip containing the same message that the interactive environment displayed.

Type-safe Format String Error with Tooltip

This is another example of how F# is extremely statically-typed. The F# compiler works to make even format strings type-safe.

posted on Wednesday, January 16, 2008 8:12:50 AM (Pacific Standard Time, UTC-08:00)  #    Comments [2]

kick it on DotNetKicks.com
 Tuesday, January 15, 2008
I'm starting a brand new series of short articles about F#. The plan is to describe features that, for me, make F# a compelling and enjoyable .NET language. So far, I have 10-15 articles in mind, but I'm open to suggestions. If you have any ideas for additional topics, please email them to dustin AT diditwith.net.

The Interactive Environment

Like Python, Ruby and many other programming languages, F# provides an interactive scripting environment. However, F# is different in that the interactive environment is not an interpreter. Instead, it dynamically compiles code on-the-fly.

There are two ways to load this environment:

  • Run fsi.exe from the bin subdirectory of the F# distribution.
  • Load the F# Interactive for Visual Studio add-in from the Visual Studio Add-in Manager.

Once the environment is loaded, a splash screen is displayed. (NOTE: the examples here use fsi.exe.)

MSR F# Interactive, (c) Microsoft Corporation, All Rights Reserved
F# Version 1.9.3.7, compiling for .NET Framework Version v2.0.50727

NOTE:
NOTE: See 'fsi --help' for flags
NOTE:
NOTE: Commands: #r <string>;;    reference (dynamically load) the given DLL.
NOTE:           #I <string>;;    add the given search path for referenced DLLs.

NOTE:           #use <string>;;  accept input from the given file.
NOTE:           #load <string> ...<string>;;
NOTE:                            load the given file(s) as a compilation unit.
NOTE:           #time;;          toggle timing on/off.
NOTE:           #types;;         toggle display of types on/off.
NOTE:           #quit;;          exit.
NOTE:
NOTE: Visit the F# website at http://research.microsoft.com/fsharp.
NOTE: Bug reports to fsbugs@microsoft.com. Enjoy!

>

At this point, it's easy to start typing F# code. To execute code, type a double semi-colon. The following bit of code, when typed into the interactive environment, will instantiate and display a new .NET Windows Form:

> open System.Drawing
- open System.Windows.Forms;;

> let myForm = new Form(Text = "Hello, World!", Visible = true);;

val myForm : Form

The first two lines open the System.Drawing and System.Windows.Forms namespaces. This is analogous to C#'s using and VB's Imports statements. It isn't necessary to reference the System.Drawing.dll or System.Windows.Forms.dll assemblies because they are implicitly referenced by the environment.

The third line instantiates a new Form, sets its Text and Visible properties, and binds it to the name myForm. Because the code is dynamically compiled and executed, the form is displayed immediately.

Hello, World! Form

Now that the form is instantiated, it can be manipulated at runtime.

> myForm.BackColor <- Color.Blue;;
val it : unit = ()

When executed, the above code changes the form like so:

Hello, World! Form (colored)

The F# Interactive Environment is a great way to break out of the standard edit-compile-debug rut and prototype some code. It can even output to a .NET assembly. Run "fsi.exe --help" to see more ways in which the interactive environment can be used.

posted on Tuesday, January 15, 2008 8:06:10 AM (Pacific Standard Time, UTC-08:00)  #    Comments [6]

kick it on DotNetKicks.com