Did it with .NET

Naming Anonymous Types with Generate from Usage

Dustin Campbell — Sat, 24 Oct 2009 18:01:40 GMT

Now that Visual Studio 2010 Beta 2 is finally out the door, I’ve had a bit more time to spend coding on some of my personal projects. Yesterday, I happened upon a cool trick while using the new Generate from Usage feature. It was so helpful to me that I thought others might benefit, so I’m sharing it here.

The Anonymous Type Problem

When you need to project some data from a LINQ expression, anonymous types can be enormously convenient.

Because anonymous types are… well… anonymous, they don’t have names that can be expressed in code. This is problematic if you want to expose an anonymous type as the return type of a function. I have run into this problem many times. When refactoring code, it’s easy to get into a situation like the one below.

So, how can you get around this problem? Well, there a few possibilities.

You could replace ??? with object and use reflection to get at the properties. (Yuck!)
You could make the function generic and add a parameter to “mumble” the anonymous type.¹ (Awkward!)
Assuming C# 4.0, you could replace ??? with dynamic.² (No compiler errors!)

Because none of these solutions is particularly savory, most of us are forced to create a new named type to replace the anonymous type. Thankfully, there are some fantastic third-party refactoring tools out there that can automate this tedious process, but if you don’t use one of these tools you’re stuck writing the code by hand.

Actually, no, that’s not quite true.

Generate from Usage to The Rescue!

In Visual Studio 2010, the new Generate from Usage feature makes the task of coding up new classes a snap! Just type a new name for the anonymous type in the editor, making the code look like a type constructor followed by an object initializer. Then, press Ctrl+. to expand the smart tag that immediately appears and choose the first suggestion to generate a new class.

Next, expand each smart tag in the object initializer to generate each property.

When you’re finished, you should have a brand new class containing each property, declared as auto-implemented properties. Cool!

For Visual Basic coders, Generate from Usage is even easier. Let’s start with the same LINQ expression in VB. (Notice the lack of the “_” line continuation characters. Hooray for VB10 implicit line continuation!)

Just like before, type the name of the new type that you wish to generate and press Ctrl+. to expand the smart tag. After choosing the first suggestion from the smart tag, you’re finished. The VB Generate Class feature will drill into the object initializer and generate all of the necessary properties at the same time that the class is generated.

Wrapping Up

Of course, this technique is not without flaws.

The resulting type is not immutable like the anonymous type that you’re replacing. To address this, you can easily modify the generated properties to be read-only.
The new type does not have the same structural equality semantics that anonymous types have. In practice, I’ve rarely run into an bug caused by anonymous type structural equality, but if this is a concern for you, use one of the excellent third-party tools that account for these differences.

¹See Wes Dyer's excellent article for an example of this clever trick.
²Check out Bill Wagner's post for details.

A Lover of Monkeys

Dustin Campbell — Fri, 26 Jun 2009 04:07:05 GMT

The other day, I caught a quick snapshot of Bethany playing with her favorite new toy:

A special thanks to my friend Joseph Hill for providing her favorite monkey!

CodeRush Xpress for C# and VB is Live!

Dustin Campbell — Fri, 15 May 2009 00:59:29 GMT

Last October, DevExpress released a massively powerful FREE tool specifically for C# developers called CodeRush Xpress. Today, in partnership with Microsoft, DevExpress has outdone themselves with a brand new version of CodeRush Xpress containing full support for both C# and Visual Basic. This release merges CodeRush Xpress with Refactor! for Visual Basic, creating one giant über-tool with an amazing features:

Duplicate Line
Highlight All References
Increase or Reduce Selection
Smart Clipboard Operations
Generate from Using (TDD)
Quick Navigation Window
Quick File Navigation
60+ Refactorings!

Get it while it’s hot! You can download your FREE copy of CodeRush Xpress for Visual Studio 2008 from http://devexpress.com/crx.

YAPES: Problem Ten

Dustin Campbell — Tue, 17 Mar 2009 10:13:48 GMT

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.

Lesser-Known VB: Customizing the Completion List

Dustin Campbell — Sat, 14 Mar 2009 20:23:10 GMT

In Visual Basic .NET, there are several cases in which the statement completion list will present the user with a list of values rather than the standard completion set. Most often, this occurs when assigning to a variable of one of the common System.Drawing types, Color, Brush or Pen.

At first glance, the screenshot above might seem as if the Visual Basic IDE has hard-coded a set of values into IntelliSense, but that’s not the case. In fact, this is caused by a seldom-used feature of XML Documentation that is supported by Visual Basic .NET, but isn’t currently supported by C#¹. By cracking open the the XML Documentation file for System.Drawing.dll (located at C:\Windows\Microsoft.NET\Framework\v2.0.50727\en\System.Drawing.xml on my machine), we’ll see a curious XML tag on the System.Drawing.Color definition.

<member name="T:System.Drawing.Color">

  <summary>Represents
an ARGB (alpha, red, green, blue) color.</summary>

  <filterpriority>1</filterpriority>

  <completionlist cref="T:System.Drawing.Color" />

</member>

The highlighted completionlist tag above is used by Visual Basic to populate the completion list with the public shared² fields and properties from the specified class or module. In this particular case, the XML documentation causes Visual Basic to populate the completion list with the public shared properties of System.Drawing.Color.

Don’t believe me? Just comment out the System.Drawing.Color completionlist tag above, save and restart Visual Studio to see how this influences the statement completion list.

Many of you are probably thinking, “so, is this just a nifty implementation detail, or is something I can actually use?” The answer is, yes, this something you can use today to customize Visual Basic’s statement completion. The code below demonstrates how the completionlist tag can be used.

''' <completionlist
cref="CommonOperations"/>

Public Class Operation

     Private ReadOnly _execute As Func(Of
Integer, Integer, Integer)

     Public Sub New(ByVal execute As Func(Of
Integer, Integer, Integer))

         _execute = execute

     End Sub

     Public Function Execute(ByVal arg1 As
Integer, ByVal arg2 As
Integer) As Integer

         Return _execute(arg1, arg2)

     End Function

End Class

Public NotInheritable Class CommonOperations

     Public Shared ReadOnly Add
= New Operation(Function(x,
y) x + y)

     Public Shared ReadOnly Subtract
= New Operation(Function(x,
y) x - y)

     Public Shared ReadOnly Multiply
= New Operation(Function(x,
y) x * y)

     Public Shared ReadOnly Divide
= New Operation(Function(x,
y) x / y)

End Class

Visual Basic will automatically pick up the completionlist tag in the code above and use it to populate the completion list like so.

While a bit limited, it’s pretty easy to customize the statement completion list experience for Visual Basic to make certain types of APIs more discoverable. It’s as simple as a single XML tag.

¹Kevin Pilch-Bisson (C# IDE Developer Lead and swell guy) has a clever idea for supporting the completionlist tag in the C# statement completion list while staying true to the C# IntelliSense model.
²The VB "Shared" keyword = static in C#.

YAPES: Problem Nine

Dustin Campbell — Mon, 09 Mar 2009 15:05:47 GMT

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

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

a ² + b² = c²

For example, 3² + 4² = 9 + 16 = 25 = 5².

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:

Generate a stream of Pythagorean triples.
Find the Pythagorean triple whose sum is equal to 1000.
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 = m² – n², c = m² + n²

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.

N e R d Note

To produce every Pythagorean triple, we would have to introduce an additional parameter, k, into the formula.

a = 2kmn, b = k(m² – n²), c = k(m² + n²)

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.

¹Yet Another Project Euler Series

YAPES: Problem Eight

Dustin Campbell — Sat, 07 Mar 2009 21:09:11 GMT

Welcome coding ninjas!¹ 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:

Transform the 1000-digit number into a list of digits.
Transform the list of digits into a list of quintuplets—that is, a list containing tuples of each five consecutive elements.
Transform the list of quintuplets into a list containing the product of each.
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:

Transform the string into a list of chars.
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.
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.

N e R d 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!

¹Or pirates.

Modifying VB XML Literals at Debug-Time

Dustin Campbell — Sat, 14 Feb 2009 20:07:24 GMT

As a Program Manager at Microsoft, I wear several different hats. First and foremost, I am the Visual Basic IDE Program Manager, whose job is to keep the powerful engine that is the VB IDE Team running smoothly. However, another hat I wear is that of the Debugger Experience PM, whose job is to ensure that C#, Visual Basic and, yes, F# programmers have a great debug-time experience. From the language perspective, this often comes down to making the right tweaks in the debugger expression evaluators.

So, what are these debugger expression evaluators? The expression evaluators (affectionately known as the EEs) are magic machinery that deal with language-specific details on behalf of the core debugging engine that lives inside Visual Studio. In general, the EEs are responsible for the following:¹

Displaying values in datatips, and the locals, autos and watch windows (i.e. the variable windows)
Executing code that has been typed into a watch, the Immediate Window, a breakpoint condition, etc. and passing the result back to the debugger
Processing edited values at debug-time

Notice that all three of the items above must be tailored to the language that the user is developing in. For example, it doesn’t make sense to display the C#-style hexadecimal value, 0x2a, to Visual Basic users. VB users expect to see the value rendered in the Visual Basic style for hexadecimal numbers, &H2A. Thus, to keep the experiences consistent, C# and VB both provide their own debugger expression evaluators.²

Recently, I was playing with a bit of Visual Basic code using an XML literal.

Module Module1

  Sub Main()

    Dim contacts = <contacts>

                     <contact name="Bob"/>

                     <contact name="Sally"/>

                   </contacts>

        Console.WriteLine(contacts)

    End Sub

End Module

If you’ve never seen a VB XML literal before, know that they are beautiful and powerful language constructs.³ Essentially, the code above is equivalent to the following C# code.

var contacts
= new XElement("contacts",

                 new XElement("contact", new XAttribute("name", "Bob")),

                 new XElement("contact", new XAttribute("name", "Sally")));

Console.WriteLine(contacts);

If I set a breakpoint in the VB code above on Console.WriteLine(contacts) and press F5 to start debugging, I can see in the Locals window that my XML literal has effectively produced the same tree of XElement and XAttribute objects that the C# code explicitly declares above.

Now, suppose that I’ve made a mistake when declaring the XML literal (e.g. “Bob” should be “Harry”), but I don’t want to stop debugging, fix the code, and F5 to start again. I have a couple of options available to me for modifying values at debug-time.

I can use Edit and Continue. This feature allows me to change my code at debug-time and move the instruction pointer in order to execute the modified code. However, this might not always be convenient.
I can edit the value directly in one of the variable windows, the datatip, or the Immediate Window.

Choosing option two above, I’ll fix my mistake by editing the XML value directly in the Locals Window.

Upon pressing ENTER, I’m presented with the following error dialog.

What the heck does that mean? Well, this is the message that would be displayed by the Visual Basic compiler for a string value with inner quotes that are not escaped.⁴

Attempt number two: I’ll edit the value again and be careful to escape the quotes.

This time, when I press ENTER, I get yet another error message.

Grrr. Now I’m getting irritated!

Fortunately, the error message above gives me the clue I need to make this work. The problem is that I’m producing a string value, and I should be producing an XML value. What do I need to do differently? I need to remove the quotes that are enclosing the whole XML value.

Last try.

Success!

This time, I’m rewarded with a red display color for the value, indicating that the value has changed. If I expand some of the inner nodes, I can see that the tree of XElement and XAttribute objects has indeed been rebuilt.

That’s a pretty nifty trick that you can use right now in Visual Studio 2008. However, when I put on my Debugger PM hat, I consider how to improve this experience for Visual Studio 2010. Easy! We’ve removed the enclosing double-quotes from XElement values in the Visual Basic Expression Evaluator.

Sometimes achieving the best experience is just a simple tweak away.

¹This is not an exhaustive list.
²F# currently uses the C# EE, but eventually F# will provide its own. Feel free to ping Luke and Tim to help make this happen.
³For a good example of how powerful XML literals are, see Dmitry Robsman's ASP .NET MVC Engine Using VB.NET XML Literals.
⁴Displaying this string without escaping the quotes strikes me as a bug. :-)

Dustin and Chris, Deep Fried

Dustin Campbell — Tue, 20 Jan 2009 08:01:22 GMT

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

Check it out!

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

YAPES: Problem Seven, Part 2

Dustin Campbell — Tue, 20 Jan 2009 07:44:09 GMT

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 YAPES¹ 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:

Start with the natural numbers from 2 up to some maximum limit.
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.
Take the next unmarked number and mark all of its multiples.
Repeat step 3 until there are no more numbers left to test.
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 Eratosthenes², 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.

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.

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.

Let's skip ahead to some more interesting cases.

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

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.

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

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.

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!

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

Printf and Formatting Debug Output in F#

Dustin Campbell — Mon, 29 Dec 2008 19:35:14 GMT

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

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

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

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

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

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

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

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


          module Debug
=

  open System.Diagnostics

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

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

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


          module Debug
=

  open System.Diagnostics

  let writef fmt = Printf.ksprintf Debug.Write
fmt

  let writefn fmt = Printf.ksprintf Debug.WriteLine
fmt

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

Debug.writef "The
answer = %d" 42

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

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

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