Friday, April 25, 2008

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

> fibs |> Seq.take 10;;

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

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

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

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

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

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

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

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

let isEven n = n % 2 = 0

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

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

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

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

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

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

F# takes care of the rest.

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

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

kick it on DotNetKicks.com
 Thursday, April 24, 2008

Jason Follas has done it again! He has trumped all of our feeble geeky efforts to firmly establish himself as the reigning "King Nerd." Over the years, Jason repeatedly has proven his worthiness. Here are a few highlights.

  • Built his own Donkey Kong machine. Not a MAME cabinet. A real, full-blown Donkey Kong machine. Sold at auction.
  • Played the 1984 Hitchhiker's Guide to the Galaxy text adventure game on SQL Server 2005 via SQLCLR.
  • Presented a public demo of the SQL Server 2005 XML Data Type by importing World of Warcraft guild data via web services.

Today, I began a modest blog post series of F# solutions to the Project Euler problems. Not to be outdone, Jason has started a similar series. However, Jason has far loftier, or rather, nerdier goals for his series. You see, Jason is solving the problems with LUA, the scripting language beneath World of Warcraft. In fact, he's using WoW as his test-bed.

Don't believe me? Check out the screenshot below.

WoWEuler

The man must be stopped before he goes too far.

posted on Thursday, April 24, 2008 7:17:59 PM (Pacific Standard Time, UTC-08:00)  #    Comments [1]

kick it on DotNetKicks.com

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

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

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

Let's get started.

Problem One

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

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

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

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

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

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

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

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

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

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

That's beautiful.

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

kick it on DotNetKicks.com
 Monday, April 14, 2008

seattle-skyline

This week I get to hang out with lots of smart people. Monday through Thursday is the Microsoft MVP Global Summit, and the ALT.NET Open Spaces, Seattle runs from Friday through Sunday.

One aspect of these events that I really like is the lack of name-dropping. It's just plain dangerous with so many "elites" walking about. I can imagine that the potential for an embarrassing faux pas is pretty high.

Fanboy Geek: "I was talking to Martin Fowler the other day and he said..."

Martin: "Hi, I'm Martin Fowler. Who the heck are you?"

posted on Monday, April 14, 2008 2:43:59 PM (Pacific Standard Time, UTC-08:00)  #    Comments [1]

kick it on DotNetKicks.com
 Wednesday, April 09, 2008

BlueMonster 

The rumors are all true. May 19, 2008 will be my first official day as an employee of Microsoft. Specifically, I will be joining the Visual Studio Team as a Program Manager.

This month marks five years since I joined the (then) fledgling CodeRush team at DevExpress as an outside contractor. (I later became a full employee in September of 2003.) The years seem to have passed quickly, yet we've accomplished an incredible amount with CodeRush and Refactor. It feels like just yesterday when Mark and I were doing our first proof of concept work for painting via managed code on the decidedly unmanaged Visual Studio editor. Yet today, we're shipping products with blazingly fast productivity boosts, more than 150 refactorings, and stunning next-generation UI. After five years, I still feel that CodeRush and Refactor are, hands down, the best Visual Studio productivity tools available.

I'm leaving quite a bit behind to join Microsoft. DevExpress is an amazing company to work for. If any readers are looking to work for a cutting-edge company at the top of its game, I recommend applying. At DevExpress, I've developed some strong friendships that are difficult to leave. Obviously, we'll keep in touch and see each other at conferences, but we won't be working together anymore. Ray, Julian, Kevin, Oliver, Courtney and Mehul will be greatly missed.

I'll especially miss working with the IDE Tools team (a few members of which are pictured below). Contrary to popular belief, Mark and I don't make up the entire IDE Tools team. In reality, it is staffed by some extraordinarily intelligent programmers—all of whom have been blessed with the ability to deal with Mark and myself.

IDE Team (partial)

One couldn't find a more talented group of people.

But scarecrow, I'll miss you most of all1.

garlic

Regardless of the garlic (viewable in the picture above) that you constantly hang over yourself to ward off vampires, the last five years have been the most enriching of my programming career. To say that "I've learned a lot" is a gross understatement. You truly are a visionary and an inspiring person to work for (with). From you, I've learned that presumed impossibility should never be a barrier to invention.

As much as I love DevExpress, it's time for a change. The company is in a really healthy place, and my leaving should cause minimal ripples. I think that I have a lot to offer in the IDE space at Microsoft, and it's a good time to move on.

In addition to leaving my current job, I will be moving to Seattle. For the next several months, my family and I will be going through the stresses of relocation. Is anyone interested in purchasing a charming two story, brick, four bedroom home in Toledo, Ohio?

1Hillary Flammond, Top Secret!

posted on Wednesday, April 09, 2008 8:19:47 AM (Pacific Standard Time, UTC-08:00)  #    Comments [16]

kick it on DotNetKicks.com
 Friday, April 04, 2008

Isn't She Hot? 

I have a terrible, secret shame: my writing skills are lousy.

For me, perhaps the most difficult aspect of blogging is the writing process. Sometimes I feel inspired, but more often, I struggle. No matter how profound my level of inspiration is, bugs always seem to work themselves into my writing. Missing words, grammar slip-ups, poor phrasing—you name it. I feel as if I've been cursed.

My frustration is probably due to my dislike of writing in school. Back then, it simply didn't interest me. I was too busy learning to code against the Zilog Z80, and playing Trade Wars on my local BBS. I suppose it didn't help that, for many years, the vast majority of my reading consisted of either technical books or comic books.

When I began blogging in August of 2006, my writing was... unpolished. I composed my posts with the same grace that elephants construct model airplanes. Sadly, I couldn't recognize my own weakness.

For awhile, my blog stayed pretty low on the radar. I wrote a few technical articles, but in February of 2007, I really hit my (first) stride writing articles about functional programming concepts using C# 2.0. I rolled into March, picking up steam until my writing and I reached an impasse.

On March 23, 2007, I posted an article that earned me a few negative emails. None of the emails criticized my content (which is still pretty cool). Instead, they (gently) pointed out typos, poorly-constructed sentences, and unclear tidbits.

Feeling frustrated and inept, I asked my trophy wife—who graduated with a minor in English Education—to take a look at my article. Graciously, she corrected my grammar, and I promptly re-posted it. So, everything was OK now, right? Wrong. The wind in my blogging sails had died down. My dear trophy wife continued to help me with blog posts, but my desire to blog had waned. Eventually, my output shrank to just a trickle.

Finally, on August 1, 2007, I was bit by the blogging bug for a second time. But this time was different. This time, I was playing it smart. I "employed" my trophy wife as a full-time editor. Since then, she has poured over every blog post with me.

My trophy wife is an especially good editor. In addition to navigating through my grammatical mine fields, she works hard to actually understand the concepts that I'm trying communicate. The process results in better-written articles that are more easily understood.

Since I got my second wind, blogging has been a joy. It's much more fun to have someone to bounce ideas off of ([ed.] Never end a sentence with a preposition, silly). But most importantly, it's provided a way to bring my trophy wife into my world.

posted on Friday, April 04, 2008 11:55:18 AM (Pacific Standard Time, UTC-08:00)  #    Comments [6]

kick it on DotNetKicks.com
 Thursday, April 03, 2008

 WeigtingApplesAndOranges

This recent blog post caused quite a stir on the F# mailing list. The post presents two solutions for Project Euler Problem 14: one in C# and the other in F#. The C# version clearly is hand-optimized for speed (and is indeed very fast), but the F# solution isn't. Instead, the F# code appears to be written with elegance and brevity in mind. Robert Pickering presented a challenge to create a faster F# solution, and the F# mailing list (which had been dormant for a couple of weeks) literally exploded with ideas.

Before we go too far afield, below are the instructions for Project Euler Problem 14.

The following iterative sequence is defined for the set of positive integers:

nn/2 (n is even)
n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

As you can see, the problem boils down to generating one million sequences and counting the number of terms in each to find the longest. It's not rocket science, but there are many ways to optimize the solution. However, I'm not interested in creating the most optimal F# code to compete with the C# version. That's already been done by many of the gurus. Instead, I'd like to know if we can write C# code that more closely matches the algorithm used by the F# solution. Let's see how C# matches up when playing F#'s game.

Below is the F# solution that's caused so much debate.

#light

let seqLength n =
  n |> Seq.unfold
    (fun x -> match x with
             
| x when x = 0L      -> None
              | x when x = 1L      -> Some(1L, 0L)
              | x when x % 2L = 0L -> Some(x, x / 2L)
              | _                  -> Some(x, 3L*x + 1L))
    |> Seq.length

[for i in 1L..1000000L -> (i, seqLength i)]
  |> List.fold1_left(fun (ai,al) (i,l) -> if l > al then (i,l) else (ai,al))
  |> (fun (x,y) -> x ) |> print_any

If you've been following my F# articles, the code above shouldn't contain anything new. Pattern matching, tuples, option types, list comprehensions, functions and the forward pipe operator should all be reasonably familiar. The only item that truly requires explanation is the Seq.unfold function.

In F#, seq<'a> is an alias for the .NET interface, IEnumerable<T>, which is implemented by every collection in the Base Class Library and is the centerpiece of LINQ to Objects. In fact, in the F# libraries, seq<'a> is defined very simply as...

type seq<'a> = IEnumerable<'a>

See? Simple.

Seq.unfold is a library function that creates a seq<'a>, given a generator function. The resulting seq<'a> is lazily evaluated. That is, when a value in the seq<'a> is requested, the generator function is called to calculate it. In practice, it's similar to a C# iterator. The signature of Seq.unfold looks like so:

val unfold : generator: ('b -> ('a * 'b) option) -> 'b -> seq<'a>

The generator function is usually the part that trips people up. When called, the generator is passed a bit of state. This state is initialized by the second argument passed to Seq.unfold. To confuse matters further, the generator returns an option type containing a tuple. This option+tuple result represents three pieces of information:

  1. The option type indicates whether or not the sequence should continue. I.e., returning None signals the end of the sequence.
  2. The first part of the tuple is the current item in the sequence.
  3. The second part of the tuple is the bit of state that will be passed to the generator the next time it's called.

Note that the state and the result aren't required to be of the same type. This means that you can use Seq.unfold to generate some fairly flexible sequences. For example, we could produce the counting numbers as a sequence of strings.

1 |> Seq.unfold (fun i -> Some(i.ToString("#,#"), i + 1))

The above code produces an infinite sequence. That's OK because the sequence is lazy. However, we could introduce starting and stopping values by declaring a function and modifying the generator.

let count (start : int) stop =
  start |> Seq.unfold (fun i -> if i > stop then None
                                else Some(i.ToString("#,#"), i + 1))

That function can be called like so (using the F# Interactive Environment):

> count 1000 1003;;

val it : seq = seq ["1,000"; "1,001"; "1,002"; "1,003"]

Now that we have a better understanding of how Seq.unfold works, consider the generator function from the F# solution shown earlier.

(fun x -> match x with
          | x when x = 0L      -> None
          | x when x = 1L      -> Some(1L, 0L)
          | x when x % 2L = 0L -> Some(x, x / 2L)
          | _                  -> Some(x, 3L*x + 1L))

This very elegantly represents the rules of the sequence as defined by Project Euler.

nn/2 (n is even)
n → 3n + 1 (n is odd)

To create a C# solution that maps to the F# solution, we'll need to define an Unfold function. To do that, we need to create Options and Tuples. Below are the interfaces of the Option and Tuple types we'll use in C#.

public sealed class Option<T>
{
  public bool IsNone { get; }
  public bool IsSome { get; }
  public T Value { get; }

  public static Option<T> None { get; }
  public static Option<T> Some(T value) { }
}

public static class Option
{
  public static Option<T> Some<T>(T value) { }
}

public sealed class Tuple<T1, T2>
{
  public T1 Fst { get; }
  public T2 Snd { get; }
}

public static class Tuple
{
  public static Tuple<T1, T2> New<T1, T2>(T1 fst, T2 snd) { }
}

I don't want to derail our discussion by delving too deeply into them. If you're interested, you can download the source and explore them at your leisure. For our purposes, you can trust that they work as expected. One point of interest is the additional Option.Some<T>() and Tuple.New<T1, T2>() helper methods. These are in place to allow us to remove some code-clutter by taking advantage of the C# compiler's type inference for generic type parameters.

Defining Unfold as a C# iterator is fairly straightforward—that is, once you get past the scary nested generic type of the generator parameter.

public static IEnumerable<TResult> Unfold<T, TResult>(
  Func<T, Option<Tuple<TResult, T>>> generator, T start)
{
  var next = start;

  while (true)
  {
    var res = generator(next);
    if (res.IsNone)
      yield break;

    yield return res.Value.Fst;

    next = res.Value.Snd;
  }
}

Using Unfold, we can write C# code that determines the length of one of the Project Euler sequences, given a starting value.

public static long SeqLength(long start)
{
  return Unfold(x =>
    {
      if (x == 0L)
        return Option<Tuple<long, long>>.None;
      else if (x == 1L)
        return Option.Some(Tuple.New(1L, 0L));
      else if ((x % 2L) == 0L)
        return Option.Some(Tuple.New(x, x / 2L));
      else
        return Option.Some(Tuple.New(x, (3L * x) + 1L));
    }, start).Count();
}

That code is remarkably similar to the original F# code (restated below).

let seqLength n =
  n |> Seq.unfold
    (fun x -> match x with
             
| x when x = 0L      -> None
              | x when x = 1L      -> Some(1L, 0L)
              | x when x % 2L = 0L -> Some(x, x / 2L)
              | _                  -> Some(x, 3L*x + 1L))
    |> Seq.length

OK. The bulk of the work is complete. The rest of the solution can be coded with a query expression.

public static long GetLongestSequence()
{
  return (from i in Enumerable.Range(1, 1000000)
          select new { Start = i, Length = SeqLength(i) })
          .Aggregate((x, y) => y.Length > x.Length ? y : x)
          .Start;
}

Again, the symmetry between the C# query expression above and the original F# code below is striking.

[for i in 1L..1000000L -> (i, seqLength i)]
  |> List.fold1_left(fun (ai,al) (i,l) -> if l > al then (i,l) else (ai,al))
  |> (fun (x,y) -> x ) |> print_any

Where do we stand in terms of performance? Well, the C# code that we just wrote takes about 16 seconds to find the correct answer on my machine, but the F# solution comes in at around 12 seconds. The C# solution from the original blog post executes in about .047 seconds on my machine, but Robert Pickering's final F# solution takes .064 seconds. Is there a clear winner? In my opinion, no, not really.

So, what have we learned? When one takes the time to implement the same algorithm in each language, F# and C# really have a similar performance profile. However, the F# compiler definitely is tuned for elegance and beauty.

Instead of comparing apples to oranges, try comparing apples to apples and oranges to oranges. A performance comparison between two algorithms written in two different languages is interesting on some level, but it isn't really a fair comparison.

Download the source code for this article

posted on Thursday, April 03, 2008 4:40:31 AM (Pacific Standard Time, UTC-08:00)  #    Comments [3]

kick it on DotNetKicks.com
 Tuesday, April 01, 2008

Today is April Fool's Day—the day when many of us celebrate just how gullible we really are. Celebrants enjoy the day by spoofing co-workers and engaging in fun hoaxes and practical jokes.

Over the years, I've personally been the target of many an April Fool's prank. Considering today's date, I'm not sure what to make of the following email that I received this morning. Am I the target of yet another joke?

Congratulations! We are pleased to present you with the 2008 Microsoft® MVP Award! The MVP Award is our way to say thank you for promoting the spirit of community and improving people’s lives and the industry’s success every day. We appreciate your extraordinary efforts in Visual C# technical communities during the past year.

I suppose it's possible that Microsoft has a thoroughly sick sense of humor, and this is just an elaborate hoax. On the other hand, it could be that Microsoft has absolutely no sense of humor and doesn't realize that today isn't the most optimal day to be sending out congratulatory emails.

I feel that I have to give this email two responses:

  1. If this is real, I am completely humbled to be a recipient of the MVP Award this year. Blogging, speaking and educating are activities that I find very rewarding, and it's flattering to be recognized for them.
  2. If this is just an elaborate joke, I'm thoroughly disgusted and saddened by the juvenile attempt at humor. People have feelings, ya' know!

How hard is it to send these emails on March 31st or April 2nd? :-) That would clear up a lot of confusion.

P.S. I know it's real. Thanks Microsoft! I am truly honored. No joke.

posted on Tuesday, April 01, 2008 7:44:09 AM (Pacific Standard Time, UTC-08:00)  #    Comments [10]

kick it on DotNetKicks.com