Saturday, February 18, 2012

A type extension is F#’s syntax for augmenting an existing type with new members – similar in spirit to C# and VB’s extensions methods. I employ type extensions to make life a bit easier when working with .NET libraries from F#. For example, I might make System.IO.Stream.ReadByte() a bit more natural to use from F# by writing a type extension like so:

type Stream with
    match x.ReadByte() with
    | -1 -> None
    |  b -> Some(byte b)

The function above captures the semantic of the int returned by Stream.ReadByte(), which might be either an unsigned byte or -1 when at the end of the stream. In F#, this semantic is easily represented as an Option and then more easily consumed by other F# code.

So yes, type extensions are dead useful. However, if you’re writing a type extension for a generic type, you’ll need to include all of the type parameters and there constraints. Normally this isn’t a big deal, but I just spent several minutes tearing (more) of my hair out trying to determine the correct incantation to write a type extension for Nullable.

In the documentation, Nullable is declared with two generic constraints: a struct constraint and a default constructor constraint. However, that’s not quite enough to make the F# compiler happy. F# expects a type constraint to System.ValueType as well. So, three constraints are needed to declare a type extension for Nullable.

type Nullable<'a when 'a : struct
                  and 'a : (new : unit -> 'a)
                  and 'a :> System.ValueType> with

    member x.AsOption() =
        match x.HasValue with
        | true  -> Some(x.Value)
        | false -> None

Of course, once you’ve written that, you shouldn’t need to write it again and you can use the extension to handle Nullable a bit more naturally in F#.

match someNullable.AsOption() with
| Some(n) -> printfn "%d" n
| None    -> ()
posted on Saturday, February 18, 2012 3:44:30 PM (Pacific Standard Time, UTC-08:00)  #    Comments [9]

kick it on
 Sunday, October 31, 2010

In my current F# project, I’ve employed a very simple library to support basic contract checking. It’s not fantastically clever, but I thought I’d post it here in case others find it useful.

To use the library, pipe values into the various functions of the “Is” module. For example…

let jz : OpcodeRoutine = fun (i, proc) ->
  i.Operands.Length |> Is.EqualTo 1
  i.HasBranchOffset |> Is.True

  let x = i.Operands.[0] |> proc.GetOperandValue
  let res = x = 0us
  if i.BranchOffset.Condition = res then
    proc.Branch i.BranchOffset

If either of the two preconditions highlighted above fail, a ContractFailureException will be thrown.

The full module is below. Again, the following code isn’t exactly rocket science, but I’ve found it dead useful, and you might, too.

exception ContractFailureException of string

module Is =

  let inline private fail message =
    raise <| ContractFailureException(message)

  let inline private failf fmt =
    Printf.ksprintf fail fmt

  let inline True condition =
    if condition <> true then
      fail "condition should be true."

  let inline False condition =
    if condition = true then
      fail "condition should be false."

  let inline Null obj =
    if obj <> null then
      fail "obj should be null."

  let inline Some obj =
    match obj with
    | Some(_) -> ()
    | None -> fail "obj should be Some."

  let inline None obj =
    match obj with
    | Some(_) -> fail "obj should be None."
    | None -> ()

  let inline NotNull obj =
    if obj = null then
      fail "obj should not be null."

  let inline EqualTo expected value =
    if value <> expected then
      failf "value should be equal to %A." expected

  let inline NotEqualTo expected value =
    if value = expected then
      failf "value should not be equal to %A." expected

  let inline LessThan high value =
    if value >= high then
      failf "value should be less than %A." high

  let inline LessThanOrEqualTo high value =
    if value > high then
      failf "value should be less than or equal to %A." high

  let inline GreaterThan low value =
    if value <= low then
      failf "value should be greater than %A." low

  let inline GreaterThanOrEqualTo low value =
    if value < low then
      failf "value should be greater than or equal to %A." low

  let inline InRange low high value =
    if value < low || value > high then
      failf "value should be in range %A to %A." low high

  let inline NotInRange low high value =
    if value >= low && value <= high then
      failf "value should not be in range %A to %A." low high

  let inline Empty (value : seq<_>) =
    if not (value |> Seq.isEmpty) then
      fail "value should be empty."

  let inline NotEmpty (value : seq<_>) =
    if value |> Seq.isEmpty then
      fail "value should not be empty."

  let inline OfType<'a> (value : obj) =
    match value with
    | :? 'a -> ()
    | _ -> failf "value should be of type %s." typeof<'a>.FullName

  let inline NotOfType<'a> (value : obj) =
    match value with
    | :? 'a -> failf "value should not be of type %s." typeof<'a>.FullName
    | _ -> ()


posted on Sunday, October 31, 2010 10:26:02 AM (Pacific Standard Time, UTC-08:00)  #    Comments [0]

kick it on
 Thursday, March 04, 2010

A few weeks ago, some of my colleagues and I were discussing the idiosyncrasies of various programming languages (as we often find ourselves doing—we’re kind of geeky that way), when one of us pointed out that the following code is completely valid C++0x syntax:


The “operator soup”1 above defines a C++ lambda expression (denoted by the square brackets) which declares no parameters (the first empty parentheses) or body (the empty curly braces) and is immediately invoked (the final parentheses). Conceptually, this is a nop—an empty lambda that is immediately invoked.

We found ourselves fascinated by this idea of a do-nothing lambda, and went ahead to define the same thing in our respective languages. Our first attempt was C#.

() => { }();

While the code above looks quite pretty, it’s not exactly legal. In C#, lambdas must always have an explicit delegate type, so an ugly type-cast is required in order to compile:

((Action)(() => { }))();

Sigh, so close, yet so dissatisfying!

The stronger notion of type inference in F# allows for much more succinctness.2

(fun () -> ())()

However, my favorite version is written in Visual Basic 10.

Call (Sub() Exit Sub)()

What it lacks in succinctness,3 it makes up for with human-readable clarity.


How do you write a do-nothing lambda in your language?


1One could also declare the square brackets with either an = or & operator inside to define how variables that are declared in the same scope as the lambda are captured within the lambda function’s closure. It’s amazing how much one can do without typing a single identifier character!


2Note that the F# example contains a subtle difference from the others in that it returns a value of type Unit. This implies that the entire F# expression could be passed as an argument to another function, but that is not true of the other examples.

3Though it’s the same size as the C# version when unnecessary whitespace characters are removed.

posted on Thursday, March 04, 2010 7:42:19 AM (Pacific Standard Time, UTC-08:00)  #    Comments [14]

kick it on
 Tuesday, March 17, 2009

I’m back again with another post in my Yet Another Project Euler Series. As a reminder, my approach to these problems is to try to find the most beautiful solution that I can using F#. While performance is an important, I’m looking for the most elegant solutions that I can find.

Project Euler problem ten is another dealing prime numbers.

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

As you can guess, there’s not too much to this problem. In fact, we’ll declare just one simple supporting function.

let lessThan y x = x < y

Using the above function and our existing prime number generator, our solution is short and simple.

  |> Seq.take_while (lessThan 2000000L)
  |> Seq.sum

I feel a little guilty that this post is so short, but that’s the benefit of spending two whole blog posts working out a prime number generator for problem seven.

posted on Tuesday, March 17, 2009 2:13:48 AM (Pacific Standard Time, UTC-08:00)  #    Comments [4]

kick it on
 Monday, March 09, 2009

Welcome back F# junkies! In this installment of YAPES1, we’re tackling Project Euler problem nine.

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

a2 + b2 = c2

For example, 32 + 42 = 9 + 16 = 25 = 52.

There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.

Like we’ve done before, we’ll break this problem down into steps:

  1. Generate a stream of Pythagorean triples.
  2. Find the Pythagorean triple whose sum is equal to 1000.
  3. Calculate the product of that triple.

Sound good?

The first order of business is to determine how to generate Pythagorean triples. It turns out that there are many ways to do this. However, to keep it simple, we will use Euclid’s classic formula:

Given a pair of positive integers m and n with m > n

a = 2mn, b = m2n2, c = m2 + n2

Truthfully, this formula doesn’t actually produce every possible Pythagorean triple. However, since the solution is within the set that it generates, that really isn’t a problem.

NeRd Note
To produce every Pythagorean triple, we would have to introduce an additional parameter, k, into the formula.
a = 2kmn, b = k(m2n2), c = k(m2 + n2)
This is left as an exercise for you, dear reader!

First, we’ll declare an F# function that calculates a Pythagorean triple using Euclid’s formula.

let getTriple m n =
  let a = 2*m*n
  let b = m*m - n*n
  let c = m*m + n*n

Using the above function, it’s easy to produce a stream of Pythagorean triples. Our strategy will be to start with the pair, m = 2 and n = 1. To generate the next pair, we’ll first check if n + 1 is less than m. If it is, we’ll use m and n + 1 as the next pair, otherwise we’ll use m + 1 and 1. Using Seq.unfold, we can use this algorithm to produce an infinite stream of Pythagorean triples:

let triples =
  Seq.unfold (fun (m,n) ->
                let res = getTriple m n
                let next = if n+1 < m then m,n+1 else m+1,1
                Some(res, next))

With our generator in place, we can easily solve the problem.

  |> Seq.find (fun (a,b,c) –> a+b+c = 1000)
  |> (fun (a,b,c) –> a*b*c)

While the above solution works well, we can abstract further to produce a more elegant solution. First, we’ll declare three functions to handle the three operations that we’re performing explicitly, sum, product and equals.

let sum (a,b,c) = a+b+c
let product (a,b,c) = a*b*c
let equals x y = x = y

Now, we can restate our solution using these functions with a bit of function composition to produce a truly beautiful solution.

  |> Seq.find (sum >> equals 1000)
  |> product

As we’ve seen once before, function composition is beautiful.

1Yet Another Project Euler Series

posted on Monday, March 09, 2009 7:05:47 AM (Pacific Standard Time, UTC-08:00)  #    Comments [1]

kick it on
 Saturday, March 07, 2009

Welcome coding ninjas!1 Continuing with Yet Another Project Euler Series (YAPES™), we come upon problem eight.

Find the greatest product of five consecutive digits in the 1000-digit number.


Being one of the earlier Project Euler problems, this is pretty trivial to solve. We’ll approach the problem by first breaking it into a set of simple steps:

  1. Transform the 1000-digit number into a list of digits.
  2. Transform the list of digits into a list of quintuplets—that is, a list containing tuples of each five consecutive elements.
  3. Transform the list of quintuplets into a list containing the product of each.
  4. Find the maximum element in the list.

Some or all of the steps above could be combined to produce a more optimal solution. However, the beauty of F#—and functional programming in general—is the ability to easily break a problem like this into a series of data transformations that run quickly enough for most situations. When a problem is broken down into simple operations, it is easier to optimize in other ways (e.g. parallelization).

The first step is to transform the 1000-digit number into a list of digits. To facilitate working with such a large number in code, we’ll represent it as a multi-line string. Like before, we’ll break the problem of converting a string into a list of digits into a set of simple steps:

  1. Transform the string into a list of chars.
  2. Because this was a multi-line string, some of the chars will be line breaks and whitespace. So, we’ll filter the list to include only the chars that represent digits.
  3. Transform the list of digit chars into a list containing the numerical value of each.

Let’s define a few library functions to to help with each step above.

module String =
  /// Takes a string and produces a list of chars.
  let toChars (s : string) =
    s.ToCharArray() |> Array.to_list

module Char =
  /// Determines whether a char represents a digit.
  let isDigit (c : char) =

  /// Converts a char representing a digit into its numerical value.
  let toNumber (c : char) =
    int c - int '0'

Armed with these, we can perform the 3 steps above in a declarative fashion.

let number =
   |> String.toChars
   |> List.filter Char.isDigit
   |> Char.toNumber

The next step is to transform the list of digits into a list of quintuplets. To achieve this, we’ll write a simple recursive function.

let rec toQuintuplets l =
  match l with
  | x1::(x2::x3::x4::x5::_ as t) -> (x1,x2,x3,x4,x5)::(toQuintuplets t)
  | _ -> []

Notice that the first pattern match above is slightly more complicated as we bind the list starting with the next element in the list to t, to make the recursion cleaner.

NeRd Note
The toQuintuplets function defined above will work well for this particular problem but will stack overflow if passed too large of a list because it is head-recursive. There are a couple of ways to make it tail-recursive and avoid blowing the stack, but the most elegant is to employ a continuation.
let toQuintuplets l =
  let rec loop l cont =
    match l with
    | x1::(x2::x3::x4::x5::_ as t) -> loop t (fun l –> cont ((x1,x2,x3,x4,x5)::l))
    | _ -> cont []

  loop l (fun x -> x)
Of course, that unnecessarily complicates this solution by turning the logic inside out!

The last function we’ll define is a small helper to produce the product of all of the values in a quintuplet.

let product (x1,x2,x3,x4,x5) = x1*x2*x3*x4*x5

All of the pieces are now in place, and the steps can be combined to solve Project Euler problem eight.

  |> toQuintuplets
  |> product
  |> List.max

It’s that simple!

1Or pirates.

posted on Saturday, March 07, 2009 1:09:11 PM (Pacific Standard Time, UTC-08:00)  #    Comments [2]

kick it on
 Tuesday, January 20, 2009

A few months ago, I was honored to record an episode of Deep Fried Bytes my good friend (and partner-in-crime) Chris Smith. We blabbed on about F#, functional programming, pink vodka. The usual stuff.

Check it out!

Episode 24: Chatting about F# with Chris Smith and Dustin Campbell

posted on Tuesday, January 20, 2009 12:01:22 AM (Pacific Standard Time, UTC-08:00)  #    Comments [0]

kick it on
 Monday, January 19, 2009

Last time, we took a brute force approach to solving Project Euler problem seven. Unfortunately, the resulting prime number generator turned out to be fairly ugly and not really efficient enough to handle the needs of future YAPES1 problems. This time, we’ll approach the problem using a tried-and-true algorithm that should give us the desired performance and produce a beautiful solution. I can already hear some of you rolling your eyes, because we’ll be looking at...

The Sieve of Eratosthenes

Amazingly, the Sieve of Eratosthenes is perhaps the oldest known algorithm for generating prime numbers, and yet it remains reasonably efficient by today’s standards. It’s true that there are faster methods available, but this should be fast enough. The basic algorithm is nothing earth-shattering—it’s first semester computer science stuff. However, we’ll add a twist to keep things interesting.

The Sieve of Eratosthenes works by marking composite numbers:

  1. Start with the natural numbers from 2 up to some maximum limit.
  2. Take the first unmarked number (2) and mark all multiples of that number. Note that 2 remains unmarked. Only its multiples (e.g. 4,6,8,…) are marked.
  3. Take the next unmarked number and mark all of its multiples.
  4. Repeat step 3 until there are no more numbers left to test.
  5. When finished, the unmarked numbers are the primes.

As described, this algorithm doesn’t quite work for our purposes. It is certainly easy to implement, but because of the starting requirement (a big list of numbers), it doesn’t lend itself well to generating a, potentially, infinite stream of primes. However, with a small modification, we can make it work.

The adaptation we’ll implement comes from from the excellent paper, The Genuine Sieve of Eratosthenes2, by Melissa E. O’Neill. The idea is to turn the algorithm inside out. Instead of keeping track of which numbers are prime, we’ll maintain a table of composite numbers along with their known factors. As we iterate the natural numbers, the table will be updated with new information about which numbers are known to be composite and what factors have been found.

Confused? Let’s walk through the algorithm, step by step.

Tracking Composites

We start with 2 as the first natural number and check to see if it exists in the composite table. Since the table is empty, 2 isn’t present, so we add a new list containing 2 to the table with the square of 2 (4) as the key. Finally, since 2 was not found in the composite table, we know it is prime.

Sieve Diagram 1 (after 2)

We take the next natural number, 3. Like before, 3 is not found in the composite table, so we add it to the table using its square (9) as the key and return 3 as prime.

Sieve Diagram 2 (after 3)

We take the next natural number, 4. This time is different—4 is found in the composite table, so we know it’s not prime. In this case, we take the list found in the table under 4 (the known factors), and for each factor, we add 4 and insert the result into the table. Thus, we insert 6 into the table along with its known factor, 2. (Interestingly, this algorithm doesn’t tell us that 3 is a factor of 6). Finally, we remove 4 from the table.

Sieve Diagram 3 (after 4)

Let's skip ahead to some more interesting cases.

After 9 has been processed, the table looks like so:

Sieve Diagram 4 (after 9)

The next natural number, 10, is found in the table, so we know that it’s composite and not prime. Again, we take the list of known factors, and for each factor, we add 10 and insert the result into the table. This time, the value (12) already exists in the table, so we add it to the list of known factors for that value. Lastly, we remove 10 from the table.

Sieve Diagram 5 (after 10)

The next natural number, 11, is not found in the table, so we insert its square and return it as prime.

Sieve Diagram 6 (after 11)

We find the next natural number, 12, in the table. However, because there is more than one known factor in the table, we add two new composites, 12+2=14 and 12+3=15, before finally removing 12.

Sieve Diagram 7 (after 12)

As you can see, this take on the classic algorithm allows us to determine which numbers are prime and composite by using a minimal amount of memory. Obviously, the table can grow large as we find larger primes, but the memory usage is quite reasonable relative to the traditional sieve where a large list of natural numbers would have to be generated before even the first prime is returned.

Show Me Some Code!

The F# code nearly writes itself.

let reinsert x table prime =
   let comp = x+prime
   match Map.tryfind comp table with
   | None        -> table |> Map.add comp [prime]
   | Some(facts) -> table |> Map.add comp (prime::facts)

let rec sieve x table =
  seq {
    match Map.tryfind x table with
    | None ->
        yield x
        yield! sieve (x+1L) (table |> Map.add (x*x) [x])
    | Some(factors) ->
        yield! sieve (x+1L) (factors |> List.fold_left (reinsert x) (table |> Map.remove x)) }

let primes =
  sieve 2L Map.empty

The meat of the algorithm is in the sieve function. Here, we try to locate x in the table. If it is not found, we yield x (because it’s prime) and recursively call sieve passing x+1 and a table with the square of x added to it. (Note that Map is an immutable data structure, so “mutating” functions like Map.add actually return a brand new Map.) If x is found in the table, we recursively call sieve passing x+1 and a table from which x has been removed and each known factor has been reinserted. The reinsert function performs the trivial work of reinserting a known factor into the table.

A couple of other interesting details about this code are worth pointing out:

  • sieve returns a sequence expression, denoted by the seq keyword and the curly braces. Sequence expressions are lazily evaluated, meaning that the next prime won't be calculated until requested. In addition, the sequence expression is recursive due to the use of the yield! keyword, which can be used to return another sequence expression as part of a sequence.
  • The call to List.fold_left might look a bit exotic because we are folding over the list of known factors to produce a new table with each factor reinserted.

Mutation Isn't All Bad

Now that we have a working prime number generator, let’s take a moment to optimize. Until now, we’ve been sticking with the immutable F# Map type, but we could employ a mutable data structure to improve performance. To replace the data structure in a way that preserves the beauty of the algorithm, we’ll define a set of APIs for Dictionary<TKey,TValue> that mimic the Map APIs:

module Dict =
  open System.Collections.Generic

  let empty() = new Dictionary<_,_>()

  let add k v (d : #IDictionary<'a,'b>) =
    d.[k] <- v; d

  let remove (k : 'a) (d : #IDictionary<'a,'b>) =
    d.Remove(k) |> ignore; d

  let tryfind k (d : #IDictionary<'a,'b>) =
    match d.TryGetValue(k) with
    | true, v  -> Some(v)
    | false, _ -> None

Now, it’s a simple matter of replacing references to Map with Dict, and our algorithm immediately benefits from the performance boost of using a mutable table.

let reinsert x table prime =
   let comp = x+prime
   match Dict.tryfind comp table with
   | None        -> table |> Dict.add comp [prime]
   | Some(facts) -> table |> Dict.add comp (prime::facts)

let rec sieve x table =
  seq {
    match Dict.tryfind x table with
    | None ->
        yield x
        yield! sieve (x+1L) (table |> Dict.add (x*x) [x])
    | Some(factors) ->
        yield! sieve (x+1L) (factors |> List.fold_left (reinsert x) (table |> Dict.remove x)) }

let primes =
  sieve 2L (Dict.empty())

With our prime number generator in hand, solving Project Euler problem seven is trivial:

primes |> Seq.nth 10000

At last, we’ve produced a prime number generator with a good balance of performance and beauty. If we’ve learned anything from this article or its predecessor, I hope it’s that finding an optimal solution often requires finding an appropriate algorithm.

Take that Chris!

1Yet Another Project Euler Series
2O'Neill's paper appears in The Journal of Functional Programming, Volume 19, Issue 01.

posted on Monday, January 19, 2009 11:44:09 PM (Pacific Standard Time, UTC-08:00)  #    Comments [6]

kick it on
 Monday, December 29, 2008

The F# library provides a variety of functions (based on the printf functions found in OCaml) that produce formatted text.

printf outputs formatted text to the console using the stdout stream.
printfn outputs formatted text suffixed with a new-line character to the console using the stdout stream.
eprintf outputs formatted text to the console using the stderr stream.
eprintfn outputs formatted text suffixed with a new-line character to the console using the stderr stream.
sprintf returns formatted text as a string.
bprintf appends formatted text to a System.Text.StringBuilder.
fprintf writes formatted text to a System.IO.TextWriter.
fprintfn writes formatted text suffixed with a new-line character to a System.IO.TextWriter.
twprintf writes formatted text to a System.IO.TextWriter.
twprintfn writes formatted text suffixed with a new-line character to a System.IO.TextWriter.

The functions above are especially powerful because the F# compiler will type-check the format arguments and give design-time errors.

Type-safe Format String Error with Tooltip

While this set of functions covers most of the cases where formatted text is needed, there is one glaring omission: debug output. If we want to pass formatted text to System.Diagnostics.Debug.Write, we have to do it using sprintf like so:

System.Diagnostics.Debug.Write(sprintf "The answer = %d" 42)

Obviously, that's not ideal. What we would really like is a function that behaves exactly like the other printf functions but writes debug output. Fortunately, extensibility has been built into the F# library, making it possible to create additional formatting functions that benefit from the same sweet type-checking. So, how do we go about doing that? The trick is to wrap our functions around a special F# library function, ksprintf.

ksprintf is similar to sprintf in that it formats text as a string. However, instead of returning that string to the caller, it passes the string into a continuation.

I haven't covered the broad topic of continuations yet because a) they can be pretty eye-crossing when presented plainly, and b) there are already fantastic treatments out there. The basic idea is to pass a lambda1 (the so-called continuation) into a computation that will be executed when the computation is finished. Really. That's it. This is a simple idea, but it can become complicated quickly. However, in the case of ksprintf it remains simple. We'll pass a lambda that calls Debug.Write with the final string after it has been formatted.

module Debug =
  open System.Diagnostics

  let writef fmt = Printf.ksprintf (fun s -> Debug.Write(s)) fmt

  let writefn fmt = Printf.ksprintf (fun s -> Debug.WriteLine(s)) fmt

In fact, the wrapper lambdas are redundant because Debug.Write and Debug.WriteLine have overloads that match the expected signature. We can simply pass the functions themselves and remove the wrappers:

module Debug =
  open System.Diagnostics

  let writef fmt = Printf.ksprintf Debug.Write fmt

  let writefn fmt = Printf.ksprintf Debug.WriteLine fmt

Just drop that code into an F# project, and you'll be writing debug output in a beautiful, concise F# style.

Debug.writef "The answer = %d" 42

You'll even get helpful design-time type errors:

Debug.writef Type-safe Format String Error with Tooltip

Now it's just a matter of convincing the F# team to add it to the libraries. ;-)

1Did It With .NET readers probably already know that "lambda" = "anonymous function".

posted on Monday, December 29, 2008 11:35:14 AM (Pacific Standard Time, UTC-08:00)  #    Comments [2]

kick it on
 Wednesday, December 17, 2008

It’s that time of year again. CodeMash time.

When I first moved to the Seattle area, I was concerned that I wouldn’t be able to come back to Ohio for this year’s CodeMash. Of all of the conferences that I’ve attended over the years, CodeMash has been among the most rewarding, and I really didn’t want to miss this one. Fortunately, the stars have aligned, and my family’s holiday vacation is bringing me back to the Midwest just in time to join in on all the fun.

This year’s speaker list is just insane. With names like Bill Wagner, Richard Campbell, Steve Smith, Mads Torgersen and David Laribee, I’m expecting to have a very full and satisfied brain. But CodeMash is about more than just the sessions; it’s also about the pure geek nirvana of hanging out with a group of people who are just as excited about technology as I am.

Given the list of heavyweights speaking this year, I feel pretty honored to be filling one of the slots. If you’re coming to CodeMash, check out my talk, “Multi-threading Mojo with F#.” It should be a blast.


posted on Wednesday, December 17, 2008 11:39:46 PM (Pacific Standard Time, UTC-08:00)  #    Comments [6]

kick it on
 Wednesday, September 17, 2008

Prime numbers.

If there’s one mathematical curiosity that appears more often than any other in the Project Euler problems, it’s prime numbers. To be fair, we've dealt with primes before, but problem seven is the first that requires a prime number generator as part of its solution.

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?

I must admit that I’ve been riffing on this problem for quite a while now. There are so many variations to prime number generation that I’ve had difficulty choosing one with the right balance of elegance and efficiency. Because I’ll be reusing my generator for future problems, I must be certain that it’s fast enough. However, as always my primary goal is to produce the most beautiful solution that I can.

Spoiler alert! I'm revealing the problem solution early.

primes |> Seq.nth 10000

Trivial, right? Of course, the challenge of this problem is in declaring the magic behind primes. We have a couple of options available to us, but since there’s a great deal that can be learned from using brute force to solve a problem, we’ll first try the…

The Naïve Approach

The most straightforward way to generate prime numbers is to simply test every number, starting from 2—the first prime—with some primality test. Perhaps something like the code below.

{ 2L..System.Int64.MaxValue } |> Seq.filter isPrime

For the primality test, we can test the candidate prime against every smaller number. If it is evenly divisible by any smaller number other than 1, it isn't prime.

let isPrime n =
  { 2L..n-1L } |> Seq.for_all (fun x -> n%x <> 0L)

Putting the pieces together gives us a real working solution.

let isPrime n =
  { 2L..n-1L } |> Seq.for_all (fun x -> n%x <> 0L)

let primes =
  { 2L..System.Int64.MaxValue } |> Seq.filter isPrime

primes |> Seq.nth 10000

Are we finished? Hardly! While simple, this prime number generator takes a whopping 30 seconds on my hefty-yet-quickly-obsoleting machine! That might fall within Project Euler's "one-minute rule," but we can certainly do better.

Optimizing Naïvely

The obvious optimization is to reduce the set of numbers that isPrime tests. Observe that1 the largest factor of a number (other than itself) is its square root. Armed with this knowledge, we can improve the primality test by testing just the natural numbers from 2 through the square root of n.

let isPrime n =
  let limit = int64 (sqrt (float n))
  { 2L..limit } |> Seq.for_all (fun x -> n%x <> 0L)

That's a huge improvement! Finding the 10001st prime now only takes about .25 seconds.

We can do better yet. If 2 is the only even prime, why are we bothering to test any other even numbers? We can save more time by testing only the odds.

let odds limit =
  Seq.unfold (fun n ->
    if n > limit then None
    else Some(n,n+2L)) 3L

let isPrime n =
  let limit = int64 (sqrt (float n))
  odds limit |> Seq.for_all (fun x -> n%x <> 0L)

let primes =
  seq { yield 2L
        yield! odds System.Int64.MaxValue |> Seq.filter isPrime }

That brings the solution down to approximately .2 seconds.

NeRd Note
Curious about the use of yield and yield! in the example above? The difference between these keywords is simple yet powerful. yield simply returns a single element of a sequence expression, much like the yield return of C# iterators. However, yield! returns another sequence expression as part of the sequence.2 This is an extraordinarily powerful feature that offers a lot of flexibility. In part 2, we'll use yield! to produce an elegant recursive sequence expression.

Before moving on, let's make one last optimization to our naïve algorithm. We can take advantage of the fact that every prime, after 2 and 3, is of the form 6k ± 1. By reducing the set of numbers used by our primality test to those of this form, we can eke out a tiny bit more speed.

let inline next k i =
  if i = -1L then (k,1L)
  else ((k+1L),-1L)

let candidates limit =
  Seq.unfold (fun (k,i) ->
    let v = 6L*k + i
    if (v > limit) then None
    else Some(v, (next k i))) (1L,-1L)

let isPrime n =
  let limit = int64 (sqrt (float n))
  candidates limit |> Seq.for_all (fun x -> n%x <> 0L)

let primes =
  seq { yield! [2L;3L]
        yield! candidates System.Int64.MaxValue |> Seq.filter isPrime }

Using the prime number generator above, our solution takes around .15 seconds. Not too shabby! To be fair, this problem deals with reasonably small prime numbers. Future Project Euler problems (like problem ten) will benefit from a more efficient algorithm. Next time we’ll take a look at another well-known algorithm for generating prime numbers.


1"Observe that"? Clearly, I've been reading too many academic papers lately.
2F#'s yield! is similar to the stream-flattening concept of . Perhaps this would be an useful extension to the C# language? Mads? What do you think?

posted on Wednesday, September 17, 2008 1:33:05 PM (Pacific Standard Time, UTC-08:00)  #    Comments [1]

kick it on
 Monday, September 01, 2008

NOTE: I have shamefully stolen the title of this post from the custom T-shirt sported by Amanda Laucher at Tech Ed Developer 2008. The cleverness is all hers.

I’m a bit late to the blog posting party, but the F# Team shipped the F# September 2008 CTP on Friday. Kudos to Don, Luke, Chris, Brian, Jomo and the gang! Note that this isn’t yet another research release1, but an honest-to-goodness preview of F# as a fully-supported .NET language. In addition to the CTP release, the F# Developer Center is now open for business!

The CTP is jam-packed with hotness including…

  • The new F# Project System. Brian has the details here, here, here, here, and here.
  • Sweet scripting support. Check out Jomo’s “Zero to Execute in Ten Seconds” for the nitty-gritty.
  • Units of Measure. That’s right—amidst all of the effort to pull the CTP together, the F# Team managed to include a ground-breaking new feature! Read the first part of Andrew Kennedy’s series on this killer language feature here.2

This is just a taste of what’s in the CTP. Read the detailed (and I do mean detailed) release notes for more info.

1YARR — pirate speak.
2I have a certain amount of affection for the Units of Measure language feature after seeing its power firsthand while we competed in this year’s ICFP Programming Contest.

posted on Monday, September 01, 2008 7:01:51 AM (Pacific Standard Time, UTC-08:00)  #    Comments [0]

kick it on
 Tuesday, May 06, 2008

Project Euler problem six is another easy one.

The sum of the squares of the first ten natural numbers is,

12 + 22 + ... + 102 = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + ... + 10)2 = 552 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

The solution to this problem boils down to a few folding operations and a map. The one-liner is below.

List.fold_left (+) 0 [1..100] * List.fold_left (+) 0 [1..100] - List.fold_left (+) 0 ( (fun x -> x * x) [1..100])

Pretty nasty, eh? Quite a bit of code duplication can be removed. Since they're identical, let's generalize all of the folds first by extracting them to a sum function.

let sum lst = List.fold_left (+) 0 lst

sum [1..100] * sum [1..100] - sum ( (fun x -> x * x) [1..100])

That already looks a lot better.

Next, we can generalize the multiplication operations. Each time multiplication occurs in the solution above, it's simply squaring a value. So, we can extract those operations into a square function.

let square x = x * x

square (sum [1..100]) - sum ( (fun x -> square x) [1..100])

We can simplify that even further. Because the anonymous function passed to just applies its argument to the square function, we can pass square directly.

square (sum [1..100]) - sum ( square [1..100])

Next, let's generalize the call to that produces a list of squares by moving it to a new function, squares.

let squares lst = square lst

square (sum [1..100]) - sum (squares [1..100])

At this point, we have a perfectly acceptable solution. It states the problem almost like natural English: "The square of the sum of 1 to 100 minus the sum of the squares of 1 to 100." So, why are there a few more inches left in this article? Well, I'd like to take this a step further.

Thinking more abstractly, what does our solution do? It computes the difference of two calculations that are based on the same list. We can extract this general process to a new function like so:

let difference f1 f2 lst = f1 lst - f2 lst

difference (fun l -> square (sum l)) (fun l -> sum (squares l)) [1..100]

It turns out that we can simplify these anonymous functions in the same way that we did with the square function earlier. However, because there are two functions involved in each calculation, we must compose the functions together. In F#, there are two operators used to perform function composition: the >> operator, which applies the functions from left to right, and the << operator, which applies the functions from right to left. Obviously, we need the latter.

difference (square << sum) (sum << squares) [1..100]

After using the forward pipe operator to move the list to the front, we're finished.

[1..100] |> difference (square << sum) (sum << squares)

"Take the numbers 1 to 100 and find the difference of the square of the sum and the sum of the squares."

Function composition is beautiful.

posted on Tuesday, May 06, 2008 3:21:26 AM (Pacific Standard Time, UTC-08:00)  #    Comments [3]

kick it on

A few days ago, I presented a solution for Project Euler problem four that I didn't really like. The challenge of problem four is to write a function that determines whether a number is a palindrome, that is, whether it reads the same backward as forward. When presented with that challenge, I took an approach that I feel is a bit of a cop-out: converting the number to a string, reversing the string and comparing the result. This felt somehow wrong because I'm not really solving the problem in a mathematical way. So, I'm declaring a mulligan. Below is a new function which properly performs the math necessary to reverse a base-10 number.

let reverse n =
  let rec loop x res =
    if x = 0 then res
    else loop (x/10) (res*10 + (x%10))

  loop n 0

let isPalindrome n =
  n = reverse n

Our original list comprehension below still works properly with the new isPalindrome function.

[ for x in 100..999
    for y in 100..999
      when isPalindrome(x*y) -> x*y ] |> toLargest

This solution is twice as fast as the original string-based solution. In addition, I'd argue that the tail-recursive loop is at least four times as beautiful. :-)

posted on Tuesday, May 06, 2008 3:21:13 AM (Pacific Standard Time, UTC-08:00)  #    Comments [0]

kick it on
 Monday, May 05, 2008

At first glance, Project Euler problem five looks like a walk in the park:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

Sounds easy! The most straightforward solution is to take the sequence of all natural numbers, filter those that are evenly divisible by 1 through 20, and pop off the first element of the sequence (the head). Something like the code below would do the trick.

{ 1L .. Int64.max_int }
  |> Seq.filter (fun n ->
       [1L .. 20L] |> List.for_all (fun d -> n % d = 0L))
  |> Seq.hd

Unfortunately, that solution, while direct, falls far outside of Project Euler's "one-minute rule." It eventually calculates the correct answer but takes as much as 10 minutes on my machine!

OK, let's take a step back. What exactly is the problem asking us to find? Stating it differently, "What is the least common multiple of all of the numbers from 1 to 20?"

The least common multiple (LCM) of two numbers is the smallest number that is evenly divisible by each. Still not familiar? Think about how fractions are added. The first step in adding fractions is to find the least common denominator, which is simply the LCM of the denominators. For example, given the fractions 1/8 and 1/12, we would find the LCM of 8 and 12. Then, the fractions would be rewritten with the LCM (24) as their denominators. Once this is done, we can easily add the fractions 3/24 and 2/24 to get the answer, 5/24.

So, how should we go about calculating the LCM of two numbers? It turns out that there are many well-known possibilities. One of the most popular methods involves finding the prime factors of both numbers. It goes something like this:

Suppose we wanted to find the least common multiple of 160 and 90. First, we would write out the prime factors of each:

160 = 25 * 51
90 = 21 * 32 * 51

The least common multiple can be computed by multiplying the highest power of each unique factor.

lcm(160,90) = 25 * 32 * 51 = 1440.

Many people have chosen this method when working through problem five, and I was tempted to take this road as well because it would allow us to reuse our primeFactors function from problem three. However, the code would be fairly complex.

let countItems lst =
  let incrCount m i =
    match Map.tryfind i m with
    | Some(c) -> Map.add i (c+1) m
    | None -> Map.add i 1 m

  lst |> List.fold_left incrCount Map.empty |> Map.to_list

let lcm x y =
  let rec updateMap m t =
    let i,c = t
    match Map.tryfind i m with
    | Some(v) when v < c -> Map.add i c m
    | None -> Map.add i c m
    | _ -> m

  let factors =
    [x; y]
    |> primeFactors
    |> countItems
    |> List.fold_left (List.fold_left updateMap) Map.empty

  Map.fold (fun i c res -> res * int64 (float i ** float c)) factors 1L

Personally, I feel a sense of accomplishment at writing all of those folds—particularly the double-fold near the end, that's really cool. :-) However, it's pretty far below my standard for code beauty. If you recall, I'm trying to present the most beautiful solution that I can. So, I'm rejecting this solution, even though it's efficient enough to meet Project Euler's requirements. Admittedly, there's a certain beauty in the list transformations, but there's a much better method.

The least common multiple of two numbers can be calculated quite simply using their greatest common divisor (GCD), or the largest number that divides evenly into both numbers. The GCD can be computed easily with the Euclidean algorithm. Here's how it works:

  1. Start with 2 natural numbers, x and y
  2. If y is equal to zero, the answer is x.
  3. If not, set x to the value of y, and y to the remainder of dividing x by y.
  4. Go back to step 2.

For the more visual among you, a flowchart of the Euclidean algorithm is pictured below.


Once we have the GCD, calculating the LCM is easy. Simply divide x by the GCD of x and y, and multiply the result by y. These two algorithms can be implemented quite beautifully in F#.

let rec gcd x y =
  if y = 0 then x
  else gcd y (x%y)

let lcm x y =
  if x = 0 or y = 0 then 0
  else (x / (gcd x y)) * y

However, the F# libraries already supply a function to calculate the GCD of two numbers. The greatest common denominator also goes by another name, highest common factor (HCF), and there is an HCF function in the Microsoft.FSharp.Math.BigInt module. It's a simple matter to rewrite lcm using BigInt.hcf.

open Microsoft.FSharp.Math

let lcm x y =
  if x = 0I or y = 0I then 0I
  else (x / (BigInt.hcf x y)) * y

With lcm in place, would you believe that our solution looks like this?

[1I..20I] |> List.reduce_left lcm

F# can produce truly beautiful code indeed!

posted on Monday, May 05, 2008 5:12:44 AM (Pacific Standard Time, UTC-08:00)  #    Comments [6]

kick it on
 Friday, May 02, 2008

Yet Another Project Euler Series (YAPES) continues with problem four:

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

The most straightforward way to determine if a number is palindromic is to convert it to a string and compare that string with its reverse. Sound easy? It is!

One minor snag is the lack of a library function in F# for reversing strings, but that's easily defined like so:

module String =
  let rev (s : string) = new string(s.ToCharArray() |> Array.rev)

With String.rev in place, writing an isPalindrome function is trivial.

let isPalindrome n =
  let text = Int32.to_string n
  text = String.rev text

Using a list comprehension, we can generate all of the palindromes that are products of 3-digit numbers. Once we have this list, producing the result is as simple as passing it to the toLargest function that we defined for Problem Three.

[ for x in 100..999
    for y in 100..999
      when isPalindrome (x*y) -> x*y ] |> toLargest

Short and sweet—my favorite!

posted on Friday, May 02, 2008 4:49:17 AM (Pacific Standard Time, UTC-08:00)  #    Comments [1]

kick it on
 Thursday, May 01, 2008

Project Euler problem three is first of many to deal with prime numbers.

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143?

Eventually, we'll need a prime number generator to solve some of the more advanced problems, but this problem can be solved efficiently without one. The number in question is small enough (just 12 digits) that the divide-and-conquer method that many of us learned in elementary school will suffice.

Consider how we might use this process to find the prime factors of 140.

140 Is 140 evenly divisible by 2? Yes! Remember 2 and divide 140 by 2.
2 * 70 Is 70 evenly divisible by 2? Yes! Remember 2 and divide 70 by 2.
2 * 2 * 35 Is 35 evenly divisible by 2? No, how about 3? No. 4? Nope. 5? Yes! Remember 5 and divide 35 by 5.
2 * 2 * 5 * 7 And we're done!

This method isn't rocket science, but it gets the job done. In fact, it's pretty fast for reasonably small numbers. After all, we're not trying to find the factors of RSA-200. :-)

The basic algorithm is pictured as a flowchart below.


The following F# function implements our algorithm.

let primeFactors n =
  let inline isFactor n d = n % d = 0L

  let rec nextFactor n d =
    let x = if d = 2L then 3L else d+2L
    if isFactor n x then x else nextFactor n x

  let rec findFactors n d acc =
    if isFactor n d then
      findFactors (n/d) d (d::acc)
    elif n > d then
      findFactors n (nextFactor n d) acc

  findFactors n 2L [] |> List.rev

To the uninitiated, that function might look pretty complex. In reality, it's extremely simple, but three other functions are nested inside of it. Let's look at each nested function in turn.

let inline isFactor n d = n % d = 0L

There's nothing tricky about isFactor. It simply abstracts the modulo operation that determines whether n is evenly divisible by d.

let rec nextFactor n d =
  let x = if d = 2L then 3L else d+2L
  if isFactor n x then x else nextFactor n x

nextFactor recursively determines the next value of d to be used in the algorithm. There is a small optimization here: nextFactor only produces odd numbers. Since 2 is the only even prime, why bother checking any other evens?

let rec findFactors n d acc =
  if isFactor n d then
    findFactors (n/d) d (d::acc)
  elif n > d then
    findFactors n (nextFactor n d) acc

The meat of the algorithm is handled by findFactors. Any factors found are cons'd up with the accumulator variable, acc. Note that both findFactors and nextFactor are written tail-recursively, so they can be optimized by the compiler to conserve stack space.

The real body of primeFactors kicks off the recursion:

findFactors n 2L [] |> List.rev.

The result of findFactors is passed to List.rev to return the prime factors in a more logical order (smallest to largest).

A simple test in the F# Interactive Environment shows that primeFactors works as expected.

> primeFactors 140L;;

val it : int64 list = [2L; 2L; 5L; 7L]

Almost done.

Project Euler Problem Three asks, "What is the largest prime factor of the number 600851475143?" That's just a matter of folding the list of prime factors with the max function (from the F# libraries) to get the answer.

primeFactors 600851475143L |> List.fold1_left max

We can generalize the folding logic above with a new function...

let toLargest l = List.fold1_left max l

...And now we can write the following solution.

primeFactors 600851475143L |> toLargest

That's just lovely.

NeRd Note
Eagle-eyed readers might have noticed that the problem could have been solved several inches ago. If primeFactors didn't reorder its results from smallest to largest, the solution to the problem would be in the head of the result list!
primeFactors 600851475143L |> List.hd
However, that solution has some very real consequences. First of all, primeFactors won't return its results in the most logical order, which limits its reusability. Secondly, the intent of the code isn't stated as clearly. And finally, it's a leaky abstraction because the solution relies upon intimate knowledge of how primeFactors returns its results. If primeFactors were changed later, the solution would be broken!
posted on Thursday, May 01, 2008 6:55:56 AM (Pacific Standard Time, UTC-08:00)  #    Comments [2]

kick it on
 Friday, April 25, 2008

Today, I'm tackling Project Euler problem two in F#:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

Like problem one, this is pretty trivial. It's a simple matter of filtering even numbers, taking only the numbers less than some value and folding to get the sum. However, a couple of supporting cast members need to be introduced.

First, I need a way to generate the Fibonacci sequence. There are several ways to calculate Fibonacci numbers (including a clever method that takes advantage of the relationship between Fibonacci numbers and the Golden Ratio). However, I'll heed the heavy hints of the Project Euler problem description above and go with the iterative approach.

My first stab at writing a Fibonacci sequence generator in F# is simply an imperative approach, similar to what I might write in C#, wrapped in an F# sequence expression.

let fibs =
  seq {
        let i = ref 1
        let j = ref 2
        while true do
          let x = !i
          yield x
          do i := !j
          do j := !j + x

In fact, that looks remarkably similar to how I might write a Fibonacci generator as a C# iterator.

static IEnumerable<int> Fibs
    int i = 1;
    int j = 2;
    while (true)
      int x = i;
      yield return x;
      i = j;
      j = j + x;

The F# and C# Fibonacci generators above are functionally equivalent. The obvious syntactic difference is that the F# version uses reference cells to support mutable variables. Because it uses reference cells, the F# version inherits a bit of operator baggage that might looks strange to C# developers. Most confusing is the unary ! operator, which is used to retrieve the value from a reference cell (i.e., i is a reference cell containing an int, and !i is the int contained within). This will likely look bizarre to many programmers used to C-style syntax where the unary ! operator is used to negate its operand.

NeRd Note
While the C# and F# Fibonacci sequence generators above look essentially the same, they're implemented very differently under the covers. The C# iterator compiles to a class implementing IEnumerable<int> that works like a little state machine. However, the F# sequence expression is compiled as a series of continuations.
let fibs =
  Seq.delay (fun () ->
    let i = ref 1
    let j = ref 2
      (fun () -> true)
      (Seq.delay (fun () ->
        let x = !i
          (Seq.singleton x)
          (Seq.delay (fun () ->
            i := !j
            j := !j + x
It's OK if your brain hurts.

I dislike the F# sequence expression approach above for one reason: it seems like a cop-out. It works fine, but it just feels wrong. There has to be a more declarative way to generate the Fibonacci sequence. Fortunately, there is! I can use the Seq.unfold function like so:1

let fibs =
  Seq.unfold (fun (i,j) -> Some(i,(j,i+j))) (1,2)

The generator function passed to Seq.unfold uses a tuple to represent both values needed to iterate the Fibonacci sequence. We can verify that this works properly using the F# Interative Environment.

> fibs |> Seq.take 10;;

val it : int list = [1; 2; 3; 5; 8; 13; 21; 34; 55; 89]

OK. Almost done. I just need a way to take values from the Fibonacci sequence that are less than or equal to four million, and then stop. Effectively, I need something like the LINQ TakeWhile query operator. If I had that, I could use it similarly to the following C#.

foreach (int n in Fibs.TakeWhile(n => n <= 4000000)

I looked through the F# libraries for a function like TakeWhile but couldn't find one. Either I missed it, or it just isn't there (Don?). Fortunately, this function is trivial to define in F# with a sequence expression. In fact, it's the perfect opportunity to use a sequence expression because the code must interact with an IEnumerator<int>, which has an inherently imperative programming model.

module Seq =
takeWhile f (ie : #seq<'a>) =
    seq { use e = ie.GetEnumerator()
          while e.MoveNext() && f e.Current do
            yield e.Current }

It took a little while to get here, but now I'm ready to solve Project Euler problem two. To restate, we're looking for the sum of the even-valued terms from the Fibonacci sequence that are less than or equal to four million. No problem!

  |> Seq.filter (fun n -> n % 2 = 0)
  |> Seq.takeWhile (fun n -> n <= 4000000)
  |> Seq.fold (+) 0

As stated last time, I want to present the most beautiful solution that I can. To me, that means the solution should be concise, and it should read like natural language. As before, we can achieve this by abstracting some of the logic into functions whose names better indicate the intent.

let isEven n = n % 2 = 0

let isLessThanOrEqualTo x = (fun n -> n <= x)

let sum s = Seq.fold (+) 0 s

With these functions defined, we can rewrite the solution like so:

  |> Seq.filter isEven
  |> Seq.takeWhile (isLessThanOrEqualTo 4000000)
  |> sum

The beauty of this code is that it simply states the original problem:

Find the sum of all the even-valued terms in the (Fibonacci) sequence which do not exceed four million.

F# takes care of the rest.

1For those curious about how Seq.unfold works, check out my Apples and Oranges post. For fun, try generating the Fibonacci sequence in C# using the Unfold function presented in that article.

posted on Friday, April 25, 2008 9:44:24 AM (Pacific Standard Time, UTC-08:00)  #    Comments [2]

kick it on
 Thursday, April 24, 2008

For the past several months, I've been using F# to solve at least two Project Euler problems each week. I find this is a great way to sharpen my math skills and my F# skills simultaneously. If you're looking for a way to flex your programming muscles, you really should check out Project Euler.

Last week at the MVP Summit, my friend, Bill Wagner, pressured me to suggested that I post some of my solutions. Now, there are already plenty of smart people posting F# solutions to the Project Euler problems. That's why I've resisted starting my own series: I'm not certain that I have anything new to say on the topic. However, Bill was very convincing (especially when he mentioned that I would be starting a series to a couple hundred C# MVPs).

So, here's the deal. I will try to present the most beautiful solution that I can. Naturally, beauty is in the eye of the beholder, so you might disagree with me. That's OK. Just make certain to let me know why you disagree so that I can grow as a developer. If anything, this about learning to be a better programmer.

Let's get started.

Problem One

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

Obviously, Project Euler starts with some easy problems and moves up to harder fare. The first problem is pretty trivial. It's even reminiscent of the famous FizzBuzz question.

In F#, a list of all multiples of 3 or 5 less than 1000 can be created using a list comprehension. Once we have the list, it can be summed by folding with the addition operator.

[ for x in 1 .. 999 when x % 3 = 0 or x % 5 = 0 -> x ]
  |> List.fold_left (+) 0

The power of F# (and functional programming in general) is its ability to express problems in a more declarative way. This lends the language to mathematical problems very naturally. Looking at the solution above, there are some obvious changes that could make it more succinct. First, the duplicated modulo operation can be abstracted away by declaring a new operator. (Did I mention that F# allows you to declare new operators?) Second, we can extract the folding logic to a new function that better describes its intent.

let inline (/:) x y = x % y = 0 // evenly-divisible by...

let sum list = List.fold_left (+) 0 list

With these defined, we can express the solution more cleanly.

[ for x in 1 .. 999 when x /: 3 or x /: 5 -> x ] |> sum

That's beautiful.

posted on Thursday, April 24, 2008 12:37:46 PM (Pacific Standard Time, UTC-08:00)  #    Comments [3]

kick it on
 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
 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;;


stdin(16,6): error: FS0001: This expression has type
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. is the function that F# provides for extracting a list's tail.

> let lastHalf = ( ( 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
 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;;
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

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


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;
      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:


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

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;
    case 1:
      result = 1;
      result = Fib(n - 1) + Fib(n - 2);
  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:


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.


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.


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

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


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

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

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
 Wednesday, January 23, 2008
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

posted on Wednesday, January 23, 2008 12:36:03 PM (Pacific Standard Time, UTC-08:00)  #    Comments [2]

kick it on
 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
 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
but is here used with type
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.

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

kick it on
 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

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

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, compiling for .NET Framework Version v2.0.50727

NOTE: See 'fsi --help' for flags
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: Visit the F# website at
NOTE: Bug reports to 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
 Monday, January 14, 2008
While at CodeMash, I had the opportunity to sit down with Scott Hanselman and record an episode for his renowned podcast, Hanselminutes. As a follower of the podcast, I was thoroughly flattered to be included among his guest list. The show turned out well, but the experience was definitely nerve-wracking. Here are some tips in case you ever end up in the hot seat across from Scott:
  1. Learn to hold and speak into a microphone. This is critical. During the recording, I kept drifting from the mic, which required editing in post-production.
  2. Be prepared to be disarmed by the interviewer's eloquence. Scott is a very well-spoken guy with a lot of experience. Don't be surprised when he pulls the perfect metaphor out of thin air.
  3. Be aware of your medium. When recording audio, be careful using words to explain a concept that might be better expressed with a visual diagram. Remember: it's a warning sign if you start "talking with your hands."

Scott and I talked about some of the features that make F# such an exciting language. We tried to keep it short on academia so that it would be appealing to any developer. The idea was to start small with some bite-sized concepts. Check it out!

Starting Small with F# with Dustin Campbell

posted on Monday, January 14, 2008 8:16:29 AM (Pacific Standard Time, UTC-08:00)  #    Comments [1]

kick it on
 Tuesday, November 13, 2007
While exploring F#, I've grown increasingly impressed by the libraries that ship with it. One of the main purposes of the libraries is to provide underlying support for the language itself. In addition, they contain important modules and classes necessary for functional programming (e.g. immutable List and Map types). However, the most practical aspect of these libraries to me is the rich set of APIs that facilitate using the .NET Framework in a more functional way. These APIs are often directly portable to C#. Let's look at a simple example.

The following C# code is typical of how we might create an array containing the natural numbers from 1 to 20:

int[] a = new int[20];
for (int x = 0; x < a.Length; x++)
  a[x] = x + 1;

There's nothing special about that code. It's representative of the sort of thing that we write all the time. However, it won't fly in the functional world because it's written in an imperative style. That is, the code specifies the exact steps that should be taken to create and initialize the array:

  1. Create a new int array of 20 elements.
  2. Initialize a new indexer variable, x, to 0.
  3. Check to see that x is less than the length of the array. If it isn't, STOP.
  4. Assign the value of the array element at index x to the result of x + 1.
  5. Increment x.
  6. GO BACK to step 3. Repeat as necessary.

In contrast, the F# libraries provide a special module, Array, for manipulating single-dimensional .NET arrays in a more functional style. (Array2 and Array3 are also available for manipulating two- and three-dimensional arrays respectively.) Using the Array module, the C# code above could be translated to F# like so:

let a = Array.init 20 (fun x -> x + 1)

Instead of a specific code recipe, this F# code says (in a more declarative fashion), "create an array of 20 elements, and use this function to initialize each element." An interesting feature of the F# version is that the type of the array is never declared. Because the compiler can infer that the result of the passed function (fun x -> x + 1) will be an int, "a" must be an int array.

To me, this code is beautiful. In addition, it is declarative instead of imperative; it describes what should be done but doesn't dictate exactly how it should be done. When I see such elegant code, I immediately start trying to figure out which of its aspects could be used to improve the code in my daily C# work. Here's how we might "borrow" the F# "Array.init" function in C#:

public static class ArrayEx
  public delegate T CreateItem<T>(int index);
  public static T[] Create<T>(int length, CreateItem<T> createItem)
    if (length < 0)
      throw new ArgumentOutOfRangeException("length");
    if (length == 0)
      return new T[0];
    T[] result = new T[length];
    if (createItem != null)
      for (int i = 0; i < length; i++)
        result[i] = createItem(i);
    return result;

With this function defined, we can rewrite our array creation sample declaratively using C# 3.0 syntax.

var a = ArrayEx.Create(20, x => x + 1);

Notice that this code takes advantage of the C# compiler's type inference in the same way that the F# sample does. Sweet!

Let's take a look at another example. Suppose we want to iterate through all of the elements in our int array and output each element's value to the console. We have a few of options available to us. First, there's the familiar for-loop approach:

for (int x = 0; x < a.Length; x++)

Second, there's the more declarative foreach-loop:

foreach (int val in a)

Finally, the underused "Array.ForEach" BCL method is also a possibility:

Array.ForEach(a, val => Console.WriteLine(val));

In addition, because "Console.WriteLine" has an overload which accepts a single int parameter, we can rewrite the previous code without a lambda expression:

Array.ForEach(a, Console.WriteLine);

Now, for the monkey wrench. Suppose we want to print the index of each element in the array along with the value. With this added requirement, the for-loop is our most attractive choice because the indexer variable is already built in. The other two options would require awkwardly creating an indexer variable and explicitly incrementing it. This additional code looks especially ugly with the "Array.ForEach" option.

int x = 0;
Array.ForEach(a, val => Console.WriteLine("{0}: {1}", x++, val));


How might we handle this in F#? Simple. F# provides an API designed to iterate an array with an index.

Array.iteri (fun x value -> printfn "%i: %i" x value) a

Like the BCL's "Array.ForEach" method, F#'s "Array.iteri" iterates through an array and applies the given function to each element. The difference is that the function to be applied includes an additional parameter representing the element's index in the array.

NeRd Note
Curious about why the parameter ordering of the F# "Array.iteri" API places the function to be applied before the array to be iterated? Isn't that backwards? Wouldn't it make more sense to move the array parameter to the first position? Nope. The parameter ordering is intentional.

Unless specified, F# functions are implicitly curried. Hence, parameters are usually ordered to take advantage of partial application. If the parameters of "Array.iteri" were reordered, we could not easily use partial application to build useful functions from it.
let print = Array.iteri (fun x value -> printfn "%i: %i" x value)

print a
Besides, if passing "a" as the last parameter is awkward, we can always pass it with the F# pipeline operator.
a |> Array.iteri (fun x value -> printfn "%i: %i" x value)
Make sense? OK. Take a deep breath...

Using F#'s "Array.iteri" as a model, we can define an equivalent function in C#.

public static class ArrayEx
  public delegate void IndexedAction<T>(int index, T item);
  public static void Iterate<T>(T[] array, IndexedAction<T> action)
    if (array == null)
      throw new ArgumentNullException("array");
    if (action == null)
      throw new ArgumentNullException("action");

    if (array.Length <= 0)

    int lower = array.GetLowerBound(0);
    int upper = array.GetUpperBound(0);

    for (int i = lower; i <= upper; i++)
      action(i, array[i]);

Now we can iterate our array and output the index and value of each element to the console with one line of code!

ArrayEx.Iterate(a, (x, i) => Console.WriteLine("{0}: {1}", x, i));

Since we're using C# 3.0, we can declare "ArrayEx.Iterate" as an extension method to make the client code more readable.

a.Iterate((x, i) => Console.WriteLine("{0}: {1}", x, i));

In conclusion, using F# as a source of inspiration, it's easy to create APIs that enable more declarative C# code to be written. Do you have a cool declarative API that you've written for C# or VB? If so, I'd love to hear about it. Feel free to post your creations in the comments or email me directly.

posted on Tuesday, November 13, 2007 8:17:23 PM (Pacific Standard Time, UTC-08:00)  #    Comments [18]

kick it on
 Thursday, November 08, 2007
Putting the Fun into Functional with F#

Scrambling to understand arcane-sounding functional programming terms like "closure" and "currying?" Intrigued by the recent community coverage of Microsoft's F# language, but don't know where to start? Look no further. This overview of functional programming is a wild ride through the five most important concepts using the elegant syntax of Microsoft F#. Note: no object-oriented programmers will be harmed during the session.

That's the session that I'll be presenting at the upcoming CodeMash conference. I'm really excited about this talk.

If you're planning on coming but haven't registered, the early bird discount will expire on November 15th.

See you there!

posted on Thursday, November 08, 2007 10:46:37 AM (Pacific Standard Time, UTC-08:00)  #    Comments [1]

kick it on
 Wednesday, October 31, 2007
In my recent post listing F# resources, I failed to mention the very best learning resource of all: the library source code. If you're having trouble figuring out how, say, Seq.fold works, take a look inside of ienumerable.fs to see how it's implemented. The libraries are filled with well-written code that can be used for learning and exploring this beautiful language.

posted on Wednesday, October 31, 2007 10:44:14 AM (Pacific Standard Time, UTC-08:00)  #    Comments [0]

kick it on
The following list is mostly for anyone looking for information on Microsoft's F# language and partly for myself, so I can find the links later.
  • The F# Home Page. This is the official home page for F# at Microsoft Research. Quite a bit of information can be found here, including download links for the F# distribution, the F# manual and the F# library reference.
  • hubFS. The forums at hubFS are a gold mine of information. This is where the F# authorities (like Don Syme himself!) answers questions.
  • F# Wiki. There are some great articles and tips here. Hopefully, this will expand as the interest around F# increases.
  • The F# Journal. This subscription-based online journal is maintained by well-known F# authority, Jon Harrop. The content is quite good, but unfortunately, the subscription is quite expensive. Currently, a six-month subscription is priced at £59. At today's exchange rate, that's approximately $122—an amazingly hefty price for an online journal. (For comparison, consider that an online subscription to Cambridge's Journal of Functional Programming only costs $135 per year for individuals.)
  • Don Syme's Blog. Don Syme is the creator and principal maintainer of F#. If you're learning F#, you must read his blog. It's a requirement. :-) Don's book, Expert F#, is available for pre-order and should be shipping sometime in Nov./Dec.
  • Robert Pickering's Blog. Robert Pickering is a heavyweight in the F# community. In addition, he is the author of the excellent Foundations of F#.
  • Jomo Fisher's Blog. Jomo is a member of the new F# team in Redmond. His blog contains many interesting articles that examine F# through the lens of C#.
  • Tomas Petricek's Blog. After spending some time in the hubFS forums, I've quickly grown to appreciate the expertise of fellow C# MVP, Tomas Petricek.

If I've forgotten any important resource links for F#, feel free to list them in the comments.

posted on Wednesday, October 31, 2007 8:18:07 AM (Pacific Standard Time, UTC-08:00)  #    Comments [1]

kick it on
 Friday, October 26, 2007
Lately, I've been spending some quality time with Microsoft's F# language. So far, I'm completely enamored with the brevity and clarity of the language. It just feels right to me.

I recently wrote up some articles on how one might use currying, partial application and function composition along with C# and delegates to produce the factorial function from two higher-order functions. The result of this labor is below.

static void Main()
  var reduce = HigherOrder.GetReduce<Int64>().Curry();
  var getProduct = reduce((x, y) => x * y)(1);

  var sequence = HigherOrder.GetSequence<Int64>().Curry();
  var naturalsFromOne = sequence(x => ++x)(1);

  var equals = HigherOrder.GetEquals<Int64>().Curry();

  var naturalsFromOneToX = HigherOrder.Compose(equals, naturalsFromOne);
  var factorial = HigherOrder.Compose(naturalsFromOneToX, getProduct);

  var factorialOf10 = factorial(10);

  Console.WriteLine("Factorial of 10 is {0:#,#}", factorialOf10);

That code is a truly magnificent beast. While it's academically interesting to torture delegates like this, it isn't all that fruitful when the language (i.e. C#, VB) doesn't really support these shenanigans. Try that in some production code and see how quickly you lose your development job.

As an exercise, here's how I might build factorial using the same techniques in F#:


let getProduct = Seq.fold ( * ) 1
let naturalsFromOneToX n = [1 .. n]
let factorial = naturalsFromOneToX >> getProduct

printf "Factorial of 10 is %i" (factorial 10)

The first thing I should point out is that no delegates are used in this sample. F# natively supports functions as values so it's unnecessary to create delegates for them (and no, it doesn't create delegates under the covers). Secondly, functions are automatically curried in F#. You can declare functions so that they aren't curried, but that's really only useful if you're writing code that should be callable from other .NET languages. And finally, F# provides an operator (>>) for function composition.

To be fair, I should point out that the above implementation is pretty naive. It's not necessary to use function composition. This will suffice:


let factorial n = Seq.fold ( * ) 1 [1 .. n]

printf "Factorial of 10 is %i" (factorial 10)

If compiled with fsc.exe, that code will print the following to the console:

Factorial of 10 is 3628800

That's great, but what if I try to calculate the factorial of 1000?

Factorial of 1000 is 0

Hmmm... what's going on here? Well, it turns out that the F# compiler inferred the type of "factorial" to be:

val factorial : int -> int

"int" maps to the standard .NET type, System.Int32, so this factorial function expects an Int32 and returns an Int32. However, Int32 isn't actually large enough to hold the factorial of 1000. This is a job for F#'s "bigint" type. "bigint" maps to the Microsoft.FSharp.Math.Types.BigInt type which can represent arbitrarily large integer values. With a few minor modifications, the factorial function can use "bigint," and the factorial of 1000 can be properly calculated.


let factorial n = Seq.fold ( * ) 1I [1I .. n]

printf "Factorial of 1000 is %A" (factorial 1000I)

Now, the F# compiler infers the type of "factorial" to be:

val factorial : bigint -> bigint

And what does that program print to the console?

Factorial of 1000 is 40238726007709377354370243392300398571937486421071463254379


One last point: writing factorial in F# is completely unnecessary. It already exists.


open Microsoft.FSharp.Math.BigInt

printf "Factorial of 1000 is %A" (factorial 1000I)
posted on Friday, October 26, 2007 12:02:36 PM (Pacific Standard Time, UTC-08:00)  #    Comments [3]

kick it on
 Tuesday, September 25, 2007
Jomo Fisher is a C# team member who works on LINQ to SQL. Recently, Jomo has been exploring F# by compiling bits of code and seeing what the F# compiler generates. So far, I've found this "Adventures in F#" series to be quite enjoyable, and I recommend it to any interested readers. Here is a list of the articles posted to date:
I should point out that this series is not an introduction to functional programming or F#. Instead, it is more technical in nature and asks the question, "How does the compiler do that?"
posted on Tuesday, September 25, 2007 7:54:10 AM (Pacific Standard Time, UTC-08:00)  #    Comments [0]

kick it on