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
 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
 Thursday, March 20, 2008

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


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

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

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


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

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

posted on Thursday, March 20, 2008 9:39:47 AM (Pacific Standard Time, UTC-08:00)  #    Comments [0]

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
 Thursday, February 21, 2008

Computer books

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

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

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

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

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

posted on Thursday, February 21, 2008 12:44:48 PM (Pacific Standard Time, UTC-08:00)  #    Comments [17]

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
 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
 Wednesday, October 31, 2007
My good friend, and fellow language lover, Jay Wren was recently interviewed for Code to Live. Jay has a very sharp mind and scary technical chops. He the sort of programmer who tosses around phrases like "Inversion of Control" in normal conversation. On Code to Live, he talks with Josh Holmes about the Boo programming language. Check out the interview here.

posted on Wednesday, October 31, 2007 11:27:12 AM (Pacific Standard Time, UTC-08:00)  #    Comments [0]

kick it on
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
 Wednesday, August 22, 2007
Last night, I had the pleasure of attending Jason Follas' "Exploit the XML Capabilities of SQL Server 2005" talk at the Northwest Ohio .NET Users Group (NWNUG). I have a good understanding of XML and the System.Xml namespace, but I have to admit that I'm a bit of a noob when it comes to SQL Server. It just isn't something that I encounter in my day-to-day work. However, Jason really connected some dots for me. If you have an opportunity to attend this talk, I recommend it.

posted on Wednesday, August 22, 2007 6:02:11 AM (Pacific Standard Time, UTC-08:00)  #    Comments [0]

kick it on
 Monday, August 20, 2007
..for the Day of .NET is coming.

Day of .NET is a FREE .NET-only conference that is held annually in the Spring. This year's "Nerdo de Mayo" was such a big success that a decision was made to hold the conference bi-annually. Another Day of .NET is scheduled for October 20th in Ann Arbor, Michigan. If you live in Northwest Ohio, Northeast Indiana, Southern Michigan, or Hattiesburg, Mississippi, you should plan on attending. The content is always of the highest quality.

If you are planning on being there, help spread the word in the blogosphere with a delightfully EV-IL badge.

Day of .Net October 20, 2007 - See You there!

posted on Monday, August 20, 2007 6:28:58 AM (Pacific Standard Time, UTC-08:00)  #    Comments [1]

kick it on
 Thursday, May 31, 2007
I'm getting this post up just in time to have at least one entry for the month of May. Work has simply been a whirlwind and my blogging duties have been put on hold until post-Tech Ed. I have several articles in a nearly-finished state that I hope to complete in June so stay tuned...

If you're like me, you struggle daily with running iTunes on Windows Vista. OK, most of you probably aren't like me. You are likely far wiser and realized long ago that this is a fruitless exercise. Being stubborn, I dutifully load up each morning iTunes and check to see if Apple has finally released the update that they've been sitting on for so long. Today, after months of frustration, I wasn't disappointed.

iTunes UApple released iTunes 7.2 without much fanfare. This update includes important compatibility fixes for Windows Vista (most notably the painting of the main window is faster) and Apple's new iTunes Plus format for higher-quality, DRM-free music and video. This is very exciting stuff but the feature that I find even most interesting was added a bit more quietly: iTunes U.

iTunes U provides access within iTunes to recorded lectures from several major universities (e.g. MIT, Stanford, UC Berkeley, etc.). Some universities have more offerings than others, but there are plenty of computer science and mathematics lectures available for the nerdiest among us. Need a refresher on algorithms? Try MIT's Introduction to Algorithms course. Looking for more general lectures on programming? Download UC Berkeley's Structure and Interpretation of Computer Programs.

Of course, the best feature of iTunes U is that it's free!

Truthfully, the content that iTunes U offers is not new. MIT, for example, has offered course downloads for several years. However, making the resources available from iTunes greatly extends their reach and gives me one more way to put my iPod to good use.

posted on Thursday, May 31, 2007 9:15:13 AM (Pacific Standard Time, UTC-08:00)  #    Comments [0]

kick it on