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

[<RequiredModuleAccess>]
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
    | _ -> ()

Enjoy!

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

kick it on DotNetKicks.com
 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 DotNetKicks.com
 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.

primes
  |> 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 DotNetKicks.com
 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
  a,b,c

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))
             (2,1)

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

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

triples
  |> 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 DotNetKicks.com
 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.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

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) =
    System.Char.IsDigit(c)

  /// 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 =
  "73167176531330624919225119674426574742355349194934
   96983520312774506326239578318016984801869478851843
   85861560789112949495459501737958331952853208805511
   12540698747158523863050715693290963295227443043557
   66896648950445244523161731856403098711121722383113
   62229893423380308135336276614282806444486645238749
   30358907296290491560440772390713810515859307960866
   70172427121883998797908792274921901699720888093776
   65727333001053367881220235421809751254540594752243
   52584907711670556013604839586446706324415722155397
   53697817977846174064955149290862569321978468622482
   83972241375657056057490261407972968652414535100474
   82166370484403199890008895243450658541227588666881
   16427171479924442928230863465674813919123162824586
   17866458359124566529476545682848912883142607690042
   24219022671055626321111109370544217506941658960408
   07198403850962455444362981230987879927244284909188
   84580156166097919133875499200524063689912560717606
   05886116467109405077541002256983155200055935729725
   71636269561882670428252483600823257530420752963450"
   |> String.toChars
   |> List.filter Char.isDigit
   |> List.map 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.

number
  |> toQuintuplets
  |> List.map 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 DotNetKicks.com
 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 DotNetKicks.com
 Friday, March 14, 2008

Recently, I was refactoring some trivial F# code, and the results were so elegant that I felt it would be instructive to share them. My tale begins simply with a list of lists...

> let lists = [[1;2];[5;6;7];[9;10];[3;4];[8]];;

val lists : int list list

Now, suppose we wanted to sort lists by the lengths of the inner lists. How might we do that? Easy! The F# libraries include a List.sort function which does the trick.

val sort: ('a -> 'a -> int) -> 'a list -> 'a list

List.sort takes two arguments. The first argument is a function used to compare elements from the list, and the second argument is the list to be sorted. Obviously, most of the work is in defining the first argument. This comparison function returns a negative value if the first element is less than the second, a positive value if the second element is less than the first, or zero if the two elements are, in fact, equal. With that in mind, we could sort lists using List.sort and List.length like so:

> List.sort (fun x y -> if (List.length x) < (List.length y) then -1
-                       elif (List.length x) > (List.length y) then 1
-                       else 0) lists;;

val it : int list list = [[8]; [1; 2]; [9; 10]; [3; 4]; [5; 6; 7]]

OK. It worked, but that's an awful lot of code. Typing all of that into the F# Interactive Environment is fraught with peril ([ed.] the author spelled "length" as "lentgh" at least twice).

Thankfully, F# provides a function, compare, which can be used to calculate a generic comparison of two arguments.

val inline compare: 'a -> 'a -> int

compare can do most of the heavy lifting and greatly decreases the amount of code we have to write.

> List.sort (fun x y -> compare (List.length x) (List.length y)) lists;;

val it : int list list = [[8]; [1; 2]; [9; 10]; [3; 4]; [5; 6; 7]]

That's much better!

NeRd Note
Did you know that the .NET Framework also provides an API for generic comparison? For types that implement IComparable or IComparable<T>, System.Collections.Generic.Comparer<T>.Compare() can handle the dirty work!
int CompareGuids(Guid x, Guid y)
{
  return Comparer<Guid>.Default.Compare(x, y);
}

Our sort is looking pretty good, but we can do better. Let's take a closer look at the comparison function we're passing to List.sort.

(fun x y -> compare (List.length x) (List.length y))

What exactly are we doing here? Essentially, we're inserting a function application for each argument before calling compare. It sure would be nice to have a function that generalizes this for us. Perhaps something like this:

let inline compareWith f x y = compare (f x) (f y)

I can already sense the snickers. Some of you are thinking, "How could that possibly work? There aren't any types! How would F#'s statically-typed compiler handle that?"

The answer to my hecklers is yet another reason why I love F#: automatic generalization. If necessary, F# will attempt to insert generic type parameters into a function as part of its type inference. This allows very sophisticated code to be written with breathtaking succinctness. The following code shows automatic generalization in action.

> let inline compareWith f x y = compare (f x) (f y);;

val inline compareWith : ('a -> 'b) -> 'a -> 'a -> int

As you can see, F# allows us to define the essence of a function without the noise of type annotations. It looks very similar to code written in dynamically-typed languages, but has all of the benefits of static-typing.

Armed with our new compareWith function (any chance of getting that into the libraries Don?), we can sort lists using List.length like so:

> List.sort (fun x y -> compareWith List.length x y) lists;;

val it : int list list = [[8]; [1; 2]; [9; 10]; [3; 4]; [5; 6; 7]]

But wait! There's more!

I intentionally inserted what I consider to be a sophomoric blunder in that last bit of code. Try to find it. Notice that both of the parameters of our anonymous comparison function are passed, in order, as the last two arguments of compareWith. That's a big clue. Here's another. Consider the signatures of List.sort and comparewith. I'll highlight the interesting bits.

val sort: ('a -> 'a -> int) -> 'a list -> 'a list

val inline compareWith : ('a -> 'b) -> 'a -> 'a -> int

Do you see it? compareWith returns a function whose signature matches the signature of the comparison function expected by List.sort. In essence, the anonymous function is an extra "function layer" that really isn't necessary. Instead, we could write this1:

> List.sort (compareWith List.length) lists;;

val it : int list list = [[8]; [1; 2]; [9; 10]; [3; 4]; [5; 6; 7]]

This an excellent example of the benefits of currying and partial application (and yet another reason why I love F#). If you need to brush up, I've written about these topics in the past here, here and here.

There is one final bit of refactoring that I'd like to do. Notice how lists appears at the very end of the argument list for List.sort. We can make the code more readable by moving lists ahead of List.sort and using the forward pipe operator (|>) like so:

> lists |> List.sort (compareWith List.length);;

val it : int list list = [[8]; [1; 2]; [9; 10]; [3; 4]; [5; 6; 7]]

Now the code reads like an English sentence:

"Take lists and sort it, comparing with List.length."

It's a tiny jump to see that other functions could be easily used to sort lists. For example, we might sort using the head of each inner list (assuming that none of the inner lists is the empty list).

> lists |> List.sort (compareWith List.hd);;

val it : int list list = [[1; 2]; [3; 4]; [5; 6; 7]; [8]; [9; 10]]

Or, we could sort lists by the sum of each inner list (using List.fold_left with the + operator to perform the sum).

> lists |> List.sort (compareWith (List.fold_left (+) 0));;

val it : int list list = [[1; 2]; [3; 4]; [8]; [5; 6; 7]; [9; 10]]

The possibilities are endless!

Next time, we'll take a closer look at the wickedly clever forward pipe operator to see how its very existence hangs upon currying.

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

posted on Friday, March 14, 2008 10:18:34 AM (Pacific Standard Time, UTC-08:00)  #    Comments [1]

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

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

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

Simple list (recursive structure)

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

Simple list

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

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

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

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

> 1::2::3;;

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

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

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

> [1;2;3];;

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

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

> [1..3];;

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

In addition, powerful list comprehensions are available.

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

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

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

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

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

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

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

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

You see? Trivial.

OK, let's define a couple of lists.

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

val first : int list

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

val second : int list

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

Simple lists (before append)

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

> let combined = first @ second;;

val combined : int list

> combined;;

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

So, what do our lists look like now?

(Downshiftng to the imperative world...)

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

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

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

Simple lists (after append)

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

No problem.

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

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

val lastHalf : int list

> lastHalf;;

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

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

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

val it : bool = true

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

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

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

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

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

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

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

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

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

> let someValue = Some(42);;

val someValue : int option

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

> let noValue = None;;

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

val noValue : int option

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

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

val isFortyTwo : int option -> bool

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

> isFortyTwo someValue;;

val it : bool = true

> isFortyTwo noValue;;

val it : bool = false

> isFortyTwo (Some(41));;

val it : bool = false

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

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

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

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

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

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

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

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

val printStream : #Stream -> unit

And here's the above printStream function in action:

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

val bytes : byte array

> let memStream = new MemoryStream(bytes);;

val memStream : MemoryStream

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

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

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

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

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

kick it on DotNetKicks.com
 Tuesday, February 19, 2008
Greetings fellow F#-philes! Today we're looking at another reason that I am completely infatuated with the F# language—pattern matching.

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

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

#light

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

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

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

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

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

#light

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

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

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

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

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

Patterns can:

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

Let's examine each of these in turn.

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

#light

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

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

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

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

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

A code sample is worth a thousand words.

#light

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

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

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

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

#light

open System.Collections.Generic

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

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

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

Next up: the option type. See you then!

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

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

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

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

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

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

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

fun arg -> body

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

> fun x -> x + 1;;

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

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

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

x => x + 1;

Or this VB 9.0 lambda expression:

Function(x) x + 1

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

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

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

> fun x -> x + 1.0;;

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

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

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

> let pair = 37, 5;;

val pair = int * int

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

Simply put, let binds a value to a name.

let name = value

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

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

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

val inc : int -> int

And, we can call inc like so:

> inc 41;;

val it : int = 42

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

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

val add : int -> int -> int

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

> add 37 5;;

val it : int = 42

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

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

> let inc = add 1;;

val inc : (int -> int)

> inc 41;;

val it : int = 42

Cool!

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

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

val add : int -> int -> int

> add 29 13;;

val it : int = 42

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

> let add x y = x + y;;

val add : int -> int -> int

> add 23 19;;

val it : int = 42

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

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

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

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

kick it on DotNetKicks.com
 Tuesday, January 29, 2008
As promised, today I'm demonstrating a compelling way in which F# uses tuples to make .NET programming more elegant.

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

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

val d : Dictionary<int,string>

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

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

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

> d.[1];;

val it : string = "My"

> d.[3];;

val it : string = "Dictionary"

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

> d.[4];;

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

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

bool TryGetValue(TKey key, out TValue value)

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

using System;
using System.Collections.Generic;

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

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

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

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

> let mutable v = "";;

val mutable v : string

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

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

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

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

val it : bool = true

> v;;

val it : string = "My"

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

Declaring a variable as a reference cell is trivial:

> let v = ref "";;

val v : string ref

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

> d.TryGetValue(2, v);;

val it : bool = true

> !v;;

val it : string = "F#"

That's much better.

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

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

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

val res : bool * string

> res;;

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

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

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

val res : bool
val v : string

> res;;

val it : bool = true

> v;;

val it : string = "F#"

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

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

val res : bool
val v : string

> res;;

val it : bool = false

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

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

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

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

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

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

Here is the tuple that we began with last time:

> let pair = 37, 5;;

val pair = int * int

> pair;;

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

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

> fst pair;;

val it : int = 37

> snd pair;;

val it : int = 5

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

> let x = fst pair;;

val x : int

> let y = snd pair;;

val y : int

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

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

> let triple = 2, 11, 29;;

val triple : int * int * int

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

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

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

> fst triple;;

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

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

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

> let x, y, z = triple;;

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

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

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

> let x, _, z = triple;;

val x : int
val z : int

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

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

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

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

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

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

> let pair = 37, 5;;

val pair = int * int

> pair;;

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

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

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

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

val triple : int * string * float

Tuples can be compared for equality.

> pair = (29, 13);;

val it : bool = false

> pair = (37, 5);;

val it : bool = true

> pair = (19, 23);;

val it : bool = false

And other comparisons are also legal.

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

val it : bool = true

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

val it : bool = true

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

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

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

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

In addition, tuples of different lengths cannot be compared.

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

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

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

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

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

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

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

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

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

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

F# Rules! 128 0x80 12.80

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

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

F# Rules! 128 0x80 12.80

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

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

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

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

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

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

Type-safe Format String Error

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

Type-safe Format String Error with Tooltip

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

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

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

The Interactive Environment

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

There are two ways to load this environment:

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

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

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

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

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

>

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

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

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

val myForm : Form

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

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

Hello, World! Form

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

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

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

Hello, World! Form (colored)

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

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

kick it on DotNetKicks.com
 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 DotNetKicks.com
 Tuesday, January 01, 2008
It's a new year! Time to return to my passion: torturing programming languages and making them cry like little children.

This article has bit of everything: Scheme, C# and VB lambda expressions, closures, lambda calculus... the works. By the end, you'll either be enlightened or stark, raving mad.

Happy New Year!

posted on Tuesday, January 01, 2008 1:33:25 PM (Pacific Standard Time, UTC-08:00)  #    Comments [3]

kick it on DotNetKicks.com
 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++)
  Console.WriteLine(a[x]);

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

foreach (int val in a)
  Console.WriteLine(val);

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

Nasty.

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

    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 DotNetKicks.com
 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 DotNetKicks.com
 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 DotNetKicks.com
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 DotNetKicks.com
 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#:

#light

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:

#light

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.

#light

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
99104299385123986290205920442084869694048004799886101971960586316668729948085589
01323829669944590997424504087073759918823627727188732519779505950995276120874975
46249704360141827809464649629105639388743788648733711918104582578364784997701247
66328898359557354325131853239584630755574091142624174743493475534286465766116677
97396668820291207379143853719588249808126867838374559731746136085379534524221586
59320192809087829730843139284440328123155861103697680135730421616874760967587134
83120254785893207671691324484262361314125087802080002616831510273418279777047846
35868170164365024153691398281264810213092761244896359928705114964975419909342221
56683257208082133318611681155361583654698404670897560290095053761647584772842188
96796462449451607653534081989013854424879849599533191017233555566021394503997362
80750137837615307127761926849034352625200015888535147331611702103968175921510907
78801939317811419454525722386554146106289218796022383897147608850627686296714667
46975629112340824392081601537808898939645182632436716167621791689097799119037540
31274622289988005195444414282012187361745992642956581746628302955570299024324153
18161721046583203678690611726015878352075151628422554026517048330422614397428693
30616908979684825901254583271682264580665267699586526822728070757813918581788896
52208164348344825993266043367660176999612831860788386150279465955131156552036093
98818061213855860030143569452722420634463179746059468257310379008402443243846565
72450144028218852524709351906209290231364932734975655139587205596542287497740114
13346962715422845862377387538230483865688976461927383814900140767310446640259899
49022222176590433990188601856652648506179970235619389701786004081188972991831102
11712298459016419210688843871218556461249607987229085192968193723886426148396573
82291123125024186649353143970137428531926649875337218940694281434118520158014123
34482801505139969429015348307764456909907315243327828826986460278986432113908350
62170950025973898635542771967428222487575867657523442202075736305694988250879689
28162753848863396909959826280956121450994871701244516461260379029309120889086942
02851064018215439945715680594187274899809425474217358240106367740459574178516082
92301353580818400969963725242305608559037006242712434169090041536901059339838357
77939410970027753472000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000I

Awesome.

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

#light

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 DotNetKicks.com
 Tuesday, October 23, 2007
In the seventh article of my series on functional programming ideas using C#, I build on the ideas of currying and partial application. In addition, I cover a new concept: function composition.
posted on Tuesday, October 23, 2007 6:43:45 AM (Pacific Standard Time, UTC-08:00)  #    Comments [1]

kick it on DotNetKicks.com
 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 DotNetKicks.com
 Thursday, September 20, 2007
This is the sixth article in my series on functional programming ideas using C#. As promised, we're digging into partial application to explore more practical applications of currying.
posted on Thursday, September 20, 2007 7:43:07 AM (Pacific Standard Time, UTC-08:00)  #    Comments [0]

kick it on DotNetKicks.com
 Wednesday, August 15, 2007
It's time to get back to functional programming with C# 2.0. This time, I look at how the technique of "currying" fits into the picture.
posted on Wednesday, August 15, 2007 11:35:46 AM (Pacific Standard Time, UTC-08:00)  #    Comments [7]

kick it on DotNetKicks.com
 Wednesday, June 27, 2007
This time, I briefly look at how to use methods available to C# 3.0 that are equivalent to Filter, Map and Reduce.
posted on Wednesday, June 27, 2007 11:54:58 AM (Pacific Standard Time, UTC-08:00)  #    Comments [6]

kick it on DotNetKicks.com
 Thursday, June 21, 2007
After a long break, it's time to return to my informal series of articles on functional programming concepts using only C# 2.0. This time, I'm looking at the idea of higher-order functions and how to implement Map, Filter and Reduce.
posted on Thursday, June 21, 2007 8:37:03 AM (Pacific Standard Time, UTC-08:00)  #    Comments [4]

kick it on DotNetKicks.com
 Tuesday, March 20, 2007
John Backus, inventor of FORTRAN, has passed away at 82. Among other things, Backus was also the inventor of the BNF (Backus-Naur form) commonly used to express context-free grammars. A revolutionary thinker has passed from our midst.

The New York Times has an obituary here.

posted on Tuesday, March 20, 2007 4:12:13 AM (Pacific Standard Time, UTC-08:00)  #    Comments [0]

kick it on DotNetKicks.com
 Tuesday, February 13, 2007
Are you confused by all of the talk about functional programming going on in the world of C# these days? If so, maybe it's time to play a little catch up.

There are a lot of resources available that you can go to but the most valuable that I've found are the video lectures by Hal Abelson and Gerald Jay Sussman from MIT's Structure and Interpretation of Computer Programs course. These lectures were given in 1986 and may look a bit dated (I saw one guy in the class that looks like "Rusty" from "National Lampoon's Vacation") but the content is fantastic.

You can download the video lectures here.
posted on Tuesday, February 13, 2007 10:37:27 AM (Pacific Standard Time, UTC-08:00)  #    Comments [0]

kick it on DotNetKicks.com
 Monday, February 12, 2007
Continuing my series on functional programming ideas, this article looks at the functional programming technique of "automatic memoization" and shows how it can be used to great effect in C# 2.0.
posted on Monday, February 12, 2007 8:28:24 AM (Pacific Standard Time, UTC-08:00)  #    Comments [1]

kick it on DotNetKicks.com
 Friday, February 09, 2007
Closures are an important concept to understand as they underpin many functional programming techniques. This article peeks under the hood to see how closures are implemented in C# and discusses some ways in which they are extremely useful for producing robust code.
posted on Friday, February 09, 2007 10:47:06 AM (Pacific Standard Time, UTC-08:00)  #    Comments [1]

kick it on DotNetKicks.com
 Thursday, February 08, 2007
After a bit of hiatus, I am long overdue to get some code up on this blog. To give myself some direction, this is the start of an informal series that will attempt to shed some light on the functional programming ideas that have been sneaking into the C# world. In this article, I tinker with the classic Fibonacci number sequence and how to calculate them with lightning fast, thread-safe code using closures in C# 2.0.
posted on Thursday, February 08, 2007 11:51:48 AM (Pacific Standard Time, UTC-08:00)  #    Comments [3]

kick it on DotNetKicks.com