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
 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
 Wednesday, September 17, 2008

Prime numbers.

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

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

What is the 10001st prime number?

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

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

primes |> Seq.nth 10000

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

The Naïve Approach

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

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

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

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

Putting the pieces together gives us a real working solution.

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

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

primes |> Seq.nth 10000

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

Optimizing Naïvely

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

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

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

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

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

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

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

That brings the solution down to approximately .2 seconds.

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

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

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

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

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

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

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

 

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

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

kick it on DotNetKicks.com
 Tuesday, May 06, 2008

Project Euler problem six is another easy one.

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

12 + 22 + ... + 102 = 385

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

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

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

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

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

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

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

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

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

That already looks a lot better.

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

let square x = x * x

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

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

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

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

let squares lst = List.map square lst

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

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

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

let difference f1 f2 lst = f1 lst - f2 lst

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

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

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

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

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

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

Function composition is beautiful.

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

kick it on DotNetKicks.com

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

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

  loop n 0

let isPalindrome n =
  n = reverse n

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

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

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

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

kick it on DotNetKicks.com
 Monday, May 05, 2008

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

EuclideanAlgorithm

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

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

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

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

open Microsoft.FSharp.Math

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

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

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

F# can produce truly beautiful code indeed!

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

kick it on DotNetKicks.com
 Friday, May 02, 2008

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

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

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

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

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

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

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

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

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

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

Short and sweet—my favorite!

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

kick it on DotNetKicks.com
 Thursday, May 01, 2008

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

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

What is the largest prime factor of the number 600851475143?

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

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

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

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

The basic algorithm is pictured as a flowchart below.

PrimeFactorization

The following F# function implements our algorithm.

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

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

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

  findFactors n 2L [] |> List.rev

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

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

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

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

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

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

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

The real body of primeFactors kicks off the recursion:

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

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

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

> primeFactors 140L;;

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

Almost done.

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

primeFactors 600851475143L |> List.fold1_left max

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

let toLargest l = List.fold1_left max l

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

primeFactors 600851475143L |> toLargest

That's just lovely.

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

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

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
 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
 Monday, December 31, 2007

Mug

Hello again, X-mas celebrants! I have just one last verse in my carol to make all of your Visual Studio 2008 experiences bright. Don't let your hearts be saddened because my song is drawing to a close. After today, a new year filled with its own code blessings will be upon us.

My last offering is a simple one—a stocking stuffer, really. It's one last refactoring targeted at Visual Basic developers.

And so, it is with a heavy heart that I begin the last verse of the "Twelve Days of Refactor! X-mas..."

"On the twelfth day of X-mas my true love (DevExpress) gave to me..."

Extract XML Literal to Resource

In my opinion, the most compelling new feature of Visual Basic 9 is XML Literals. We've already seen how Refactor! Pro can be used to manipulate XML Literals to great effect, saving literally hundreds of keystrokes. However, sometimes we don't want to dynamically build XML. Sometimes we simply want to consume a chunk of raw XML.

Module TwelveDaysOfXmas
  Sub Main()
    Dim lBook = <book isbn="12252007">
                 <title>Refactoring: The True Meaning of X-mas</title>
                 <price>$0.00</price>
                 <author>
                   <first-name>Dustin</first-name>
                   <last-name>Campbell</last-name>
                 </author>
               </book>
  End Sub
End Module

If we're not adding embedded expressions to the above XML literal, it really belongs in a resource file. However, moving that XML to a resource is a terrible inconvenience. Thankfully, Refactor! Pro provides the Extract XML Literal to Resource refactoring. When applied to the code above, Extract XML Literal to Resource produces the following:

Module TwelveDaysOfXmas
  Sub Main()
    Dim lBook = XElement.Parse(My.Resources.XMLFile)
  End Sub
End Module

When compared to the acrobatics we've already seen Refactor! Pro perform on XML Literals, this refactoring might seem like a very small thing. It may be simple, but it's incredibly helpful when you need it. The first time that you attempt to move an XML Literal to a resource for translation purposes or any other reason, you'll be thankful that you have Extract XML Literal to Resource to do the job for you.

Check Out This Screencast to See Everything that Extract XML Literal to Resource Handles for You!

And so ends my song. We've taken a merry sleigh ride through many of the new language features available in Visual Studio 2008, and we've seen how Refactor! Pro can help you leverage those features today. It's been my distinct pleasure to be your guide on this journey.

Before I take my leave, I have one small piece of advice. If you've been waiting impatiently for the other tool to support for Visual Studio 2008, remember that Refactor! Pro has been there since the very first beta. No matter what that tool vendor may try to tell you, Visual Studio 2008 was not a surprise. Everyone had more than a year to prepare. The only ones taken by surprise were those who weren't paying attention.

And with that, I wish you a continued happy holiday season and hope Refactor! Pro can make your new year bright!

Happy New Year!

posted on Monday, December 31, 2007 10:57:09 AM (Pacific Standard Time, UTC-08:00)  #    Comments [5]

kick it on DotNetKicks.com
 Sunday, December 30, 2007

Mug

Greetings friends! I bring tidings of comfort and joy! That is, you can rest comfortably and joyously, knowing that you don't have to wait for refactorings that leverage the new language features of Visual Studio 2008. These refactorings are available today.

I'm very excited about today's verse. As promised yesterday, I'm back to share some more refactoring possibilities for Visual Basic XML Literals. By the end of the verse, you should have a sense of how powerful these refactorings truly are. If you're a Visual Basic developer, you definitely won't want to miss this!

"On the eleventh day of X-mas my true love (DevExpress) gave to me..."

More Refactoring in XML Literals

Yesterday, we saw how our bread-and-butter refactorings can be used on the inner text of XML tags to create new embedded expressions. This is extremely helpful when trying to make the contents of an XML literal more dynamic. Today, we'll take things a step further to see how we can use Refactor! Pro to manipulate the XML tags themselves.

Module TwelveDaysOfXmas
  Sub Main()
    Dim aPrice As Decimal = 0
    Dim lBook = <book isbn="12252007">
                 <title>Refactoring: The True Meaning of X-mas</title>
                 <price><%= aPrice.ToString("C") %></price>
                 <author>
                   <first-name>Dustin</first-name>
                   <last-name>Campbell</last-name>
                 </author>
               </book>
  End Sub
End Module

Consider the code above. Since Refactor! Pro works on XML tags, we can select the entire <price> tag and apply Extract Method to get the following:

Module TwelveDaysOfXmas
  Private Function GetPrice(ByVal aPrice As Decimal) As XElement
    Return <price><%= aPrice.ToString("C") %></price>
  End Function

  Sub Main()
    Dim aPrice As Decimal = 0
    Dim lBook = <book isbn="12252007">
                 <title>Refactoring: The True Meaning of X-mas</title>
                 <%= GetPrice(aPrice) %>
                 <author>
                   <first-name>Dustin</first-name>
                   <last-name>Campbell</last-name>
                 </author>
               </book>
  End Sub
End Module

A potential complication is the use of aPrice in the embedded expression. Fortunately, Extract Method intelligently analyzes this and declares it as a parameter of the new method.

View Screencast to See Extract Method in Action!

Refactor! Pro's ability to manipulate XML tags makes it easy to dynamically build XML. In fact it can save minutes of menial coding labor.

Take another look at the first code example above. Go ahead. I'll wait.

Now, imagine how much effort it would take to transform that code into this:

Module TwelveDaysOfXmas
  Private Function GetTitle(ByVal aTitle As String) As XElement
    Return <title><%= aTitle %></title>
  End Function

  Private Function GetPrice(ByVal aPrice As Decimal) As XElement
    Return <price><%= aPrice.ToString("C") %></price>
  End Function

  Private Function GetAuthor(ByVal aFirstName As String, _
                             ByVal aLastName As String) As XElement
    Return <author>
             <first-name><%= aFirstName %></last-name>
             <last-name><%= aLastName %></last-name>
           </author>
  End Function

  Private Function GetBook(ByVal aPrice As Decimal, _
                           ByVal aIsbn As String, _
                           ByVal aTitle As String, _
                           ByVal aFirstName As String, _
                           ByVal aLastName As String) As XElement
    Return <book isbn=<%= aIsbn %>>
             <%= GetTitle(aTitle) %>
             <%= GetPrice(aPrice) %>
             <%= GetAuthor(aFirstName, aLastName) %>
           </book>
  End Function

  Sub Main()
    Dim lBook = GetBook(0D, _
                  "12252007", _
                  "Refactoring: The True Meaning of X-mas", _
                  "Dustin", _
                  "Campbell")
  End Sub
End Module

That's pretty insane, isn't it? Well, with Refactor! Pro, this is a snap. In fact, most of the effort is spent typing the names of new variables and methods. The refactorings themselves take only seconds to apply.

Don't Believe Me? Check Out This Screencast!

One point I've saved until now is that Refactor! Pro is the very first tool to offer refactorings for Visual Basic XML Literals. That's just one more compelling reason that Refactor! Pro should be a part of your Visual Studio 2008 installation this holiday season.

Happy Holidays!

posted on Sunday, December 30, 2007 3:58:57 PM (Pacific Standard Time, UTC-08:00)  #    Comments [4]

kick it on DotNetKicks.com
 Saturday, December 29, 2007

Mug

I'm afraid that I have an apology to make. I feel that I've given my Visual Basic friends a raw deal because the verses of my carol thus far have been primarily about C#. Oh sure, the verses usually end with a paragraph or two mentioning how a particular refactoring works in VB, but I haven't devoted a whole verse exclusively to a Visual Basic 9 feature. Until now. Today's verse is dedicated specifically to the coolest new feature of Visual Basic 9: XML Literals.

So, sit back and relax. It's time for a little Visual Basic X-mas cheer!

"On the tenth day of X-mas my true love (DevExpress) gave to me..."

Refactoring in XML Literals

A couple of months ago, I wrote about how we were adding first-class refactoring support for Visual Basic XML Literals. If you're unfamiliar with XML Literals, they allow developers to embed XML directly into their code like so:

Module TwelveDaysOfXmas
  Sub Main()
    Dim lBook = <book isbn="12252007">
                 <title>Refactoring: The True Meaning of X-mas</title>
                 <price><%= 0D.ToString("C") %></price>
                 <author>
                   <first-name>Dustin</first-name>
                   <last-name>Campbell</last-name>
                 </author>
               </book>
  End Sub
End Module

It's the VB Compiler's job to transform the above XML Literal into instances of XElements, XAttributes and XNames from the System.Xml.Linq namespace.

Module TwelveDaysOfXmas
  Sub Main()
    Dim lBook = New XElement("book", _
                    New XAttribute("isbn", "12252007"), _
                    New XElement("title", "Refactoring: The True Meaning of X-mas"), _
                    New XElement("price", 0D.ToString("C")), _
                    New XElement("author", _
                        New XElement("first-name", "Dustin"), _
                        New XElement("last-name", "Campbell")))
  End Sub
End Module

The real power of XML Literals is the ability to embed expressions directly into the XML. In the first code example above, the <price> tag contains an embedded expression.

<price><%= 0D.ToString("C") %></price>

Embedded expressions open the door to dynamic XML generation. Very, very cool.

The only real problem that I have with XML Literals is that embedded expressions are such a pain to write. Not only does the expression itself have to be written, but the delimiters contain no less than five symbols. Granted, VB's IntelliSense fills in the last two after I've typed the first three, but that's still three characters to type with the shift key held down. That's pretty painful. It would be great if a refactoring tool existed that handled this work for us. Oh wait. I work on a refactoring tool that does that very thing. That's right, Refactor! Pro works on XML Literals!

Check out the preview hint for Introduce Local when the contents of the <title> tag are selected:

Introduce Local on Xml Literal Preview Hint

And here's the code after Introduce Local is applied:

Introduce Local on Xml Literal

Visual Basic developers everywhere can rejoice. You no longer have to type <%= again because the bread-and-butter refactorings work in XML Literals!

View Screencast of XML Literal Refactoring in Action!

Tomorrow: more refactorings for XML Literals. You won't want to miss it!

posted on Saturday, December 29, 2007 10:40:08 AM (Pacific Standard Time, UTC-08:00)  #    Comments [0]

kick it on DotNetKicks.com
 Friday, December 28, 2007

Cookies

Welcome back for more X-mas refactoring fun! There are just four more verses in my carol, but I'll make them count. Refactor! Pro can bless your Visual Studio 2008 installation in many more ways, so I'll have to pick the very best.

"On the ninth day of X-mas my true love (DevExpress) gave to me..."

Expand Lambda Expression

In my sixth verse, I described a feature of Refactor! Pro that enables developers to leverage the dreaded lambda expressions. That refactoring (Compress to Lambda Expression) provides a way to transform an anonymous method into a lambda expression. Today we're looking at lambda expressions from the opposite perspective—transforming a lambda expression into an anonymous method. Expand Lambda Expression is the refactoring that performs this conversion. Given the lambda expression in the code below...

using System;

namespace TwelveDaysOfXmas
{
  class Program
  {
    static void Main()
    {
      var numbers = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

      var numberText = Array.ConvertAll<int, string>(numbers, n => n.ToString("x8"));

      foreach (var text in numberText)
        Console.WriteLine(text);
    }
  }
}

Expand Lambda Expression will produce this:

using System;

namespace TwelveDaysOfXmas
{
  class Program
  {
    static void Main()
    {
      var numbers = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

      var numberText = Array.ConvertAll<int, string>(numbers, delegate(int n)
                                                              {
                                                                return n.ToString("x8");
                                                              });

      foreach (var text in numberText)
        Console.WriteLine(text);
    }
  }
}

I'm sure that some of you are scratching your heads. "Why in the world would I want to do that? Aren't lambda expressions better?" Well, yes. However, transforming a lambda expression into an anonymous method makes other refactorings available. For example, after expanding our lambda expression, we might want to use Name Anonymous Method to make the anonymous method a member of the current type. That way, we're promoting code reuse. Check out the preview hint for Name Anonymous Method below.

Name Anonymous Method Preview Hint

Once Name Anonymous Method is applied, we can give the new method a good name and we're done!

using System;

namespace TwelveDaysOfXmas
{
  class Program
  {
    private static string GetHexText(int n)
    {
      return n.ToString("x8");
    }
    static void Main()
    {
      var numbers = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

      var numberText = Array.ConvertAll<int, string>(numbers, GetHexText);

      foreach (var text in numberText)
        Console.WriteLine(text);
    }
  }
}

View Screencast of Expand Lambda Expression and Name Anonymous Method in Action!

I must say, it gladdens my heart to know that there is a tool available right now that allows me to refactor the latest and greatest language features of Visual Studio 2008. In fact, we've raised the bar by releasing a major update to Refactor! Pro. That's right, Refactor! Pro 3.0 is now available and ships with 150 refactorings for C#, Visual Basic, C++, ASP .NET, XAML, and even JavaScript. The future is looking very bright indeed!

posted on Friday, December 28, 2007 12:53:10 PM (Pacific Standard Time, UTC-08:00)  #    Comments [0]

kick it on DotNetKicks.com
 Thursday, December 27, 2007

Bells

JustinKohnen: @dcampbell: um... Christmas is over dude ;)

That was posted on Twitter today when I announced that I was working on this very blog entry. Well, I've got news for Mr. Justin "X-mas-Hater" Kohnen. X-mas isn't over until the fat... uhhh... lady sings. (Hmmm... that worked out much better in my head.)

While X-mas day has come and gone, the holiday season continues. I have enough verses left in my song to ensure that our merry-making runs all the way 'til the new year.

"On the eighth day of X-mas my true love (DevExpress) gave to me..."

Bread-and-Butter Refactorings in Query Expressions

Since LINQ is such a big part of what C# 3.0 and Visual Basic 9 are all about, I thought that showing two more examples of refactorings that can be used in query expressions would be useful. The refactorings we'll look at do not target query expressions specifically. Instead, these are pre-existing, bread-and-butter refactorings that have been updated to support query expressions properly.

What's a "bread-and-butter refactoring" you ask? It's one of those refactorings that you can't live without—a part of your everyday arsenal. It's important to know that these crucial refactorings work with the latest and greatest language features.

OK, let's get started!

public static int SumOfEvenSquares(int count)
{
  return (from number in Enumerable.Range(1, count)
          where (number % 2) == 0
          select number * number).Sum();
}

There are a number of refactorings that we could apply to the LINQ code above. First, let's use Introduce Local to generate a new local variable assigned to the query expression. This is easy enough to do. Just select the query expression, press the Refactor key (CTRL+` by default), choose Introduce Local, and press ENTER. Below is a screenshot of the preview hint for Introduce Local.

Introduce Local Preview Hint

The More You Know
If you are unfamiliar with Refactor! Pro's preview hints, they are sort of like windows into the future. A preview hint shows what a refactoring will do before you apply it. This feature provides the advantage you need to refactor your code with confidence.

After naming the new local variable, our refactored code looks like so:

public static int SumOfEvenSquares(int count)
{
  IEnumerable<int> evenSquares = from number in Enumerable.Range(1, count)
                                 where (number % 2) == 0
                                 select number * number;
  return evenSquares.Sum();
}

View Screencast of Introduce Local in Action!

I would be remiss if I didn't mention that there is another way to use Introduce Local. In addition to pressing the Refactor key, it is also possible to apply the refactoring using cut-and-paste. 99% of the time, when cutting an expression to the clipboard and pasting it within the same method on an empty line above the cut location, the user's intention is to create a local variable assigned to that expression. Refactor! Pro takes advantage of this knowledge to anticipate the user's intent and automatically apply Introduce Local.

View Screencast of Introduce Local Using Cut-And-Paste!

One of the red flags that some have raised against query expressions is their potential to cause code duplication. For example, the expressions in the where and select clauses from the sample code above really should be extracted to new methods. That way, we promote code reuse. If not, we are doomed to write the same tiny, bite-sized expressions over and over. Fortunately, Refactor! Pro's Extract Method refactoring works perfectly on these expressions. With Extract Method, we can easily turn the code above into:

private static IEnumerable<int> GetNaturals(int count)
{
  return Enumerable.Range(1, count);
}
private static bool IsEven(int number)
{
  return (number % 2) == 0;
}
private static int Square(int number)
{
  return number * number;
}
public static int SumOfEvenSquares(int count)
{
  IEnumerable<int> evenSquares = from number in GetNaturals(count)
                                 where IsEven(number)
                                 select Square(number);
  return evenSquares.Sum();
}

Believe it or not, using Refactor! Pro, I'm able to produce that code in just 42 keystrokes—including 23 keystrokes for the method names and 12 for navigation and selection. That means that only seven keystrokes are actually needed to apply three Extract Method refactorings!

Curious? View the Screencast of Extract Method in Action!

Finally, I must mention that Extract Method can be used with cut-and-paste just like Introduce Local. That's right, you can cut code to the clipboard and paste it on an empty line outside of a method. Extract Method will take over. Again, Refactor! Pro is working hard to anticipate your intentions.

View the Screencast of Extract Method Using Cut-And-Paste!

And thus ends the eighth verse of my song. Today we've looked at how two bread-and-butter refactorings, Introduce Local and Extract Method, can be used within LINQ expressions. The coolest thing is that all of the screencasts were recorded using Visual Studio 2008. They aren't mock ups of future features. These refactorings work with query expressions this very minute!

My Visual Basic friends might be a little worried because I didn't show these refactorings working in Visual Basic. Well, rest assured, the refactorings work fine. In fact, they work using the same keystrokes!

Now, that's what I call an X-mas present.

posted on Thursday, December 27, 2007 3:38:20 PM (Pacific Standard Time, UTC-08:00)  #    Comments [1]

kick it on DotNetKicks.com
 Wednesday, December 26, 2007

Presents

Season's greetings! We're halfway through my X-mas carol describing how Refactor! Pro can be used to leverage the new features of Visual Studio 2008. Today, I'm sharing a little more Refactor! Pro love by demonstrating a refactoring that literally can save minutes of menial coding. That's right, minutes. Interested? OK, just let me clear my voice...

"On the seventh day of X-mas my true love (DevExpress) gave to me..."

Create Backing Store

A couple of days ago, I showed how Refactor! Pro can transform properties into C# 3.0 Auto-Implemented Properties. However, sometimes the opposite is needed. We need a way to convert from an auto-implemented property to a standard property and field. Consider the following code:

using System;
using System.Drawing;

namespace TwelveDaysOfXmas
{
  class Present
  {
    public Color Color1 { get; set; }
    public Color Color2 { get; set; }
  }
}

Suppose that we want to add logic to both the Color1 and Color2 properties to ensure that they can't be set to the same value. Now, imagine how much effort that would take. An awful lot of keystrokes are needed to get to the code below.

using System;
using System.Drawing;

namespace TwelveDaysOfXmas
{
  class Present
  {
    private Color m_Color1;
    public Color Color1
    {
      get { return m_Color1; }
      set
      {
        if (m_Color2 == value)
          return;
        m_Color1 = value;
      }
    }
    private Color m_Color2;
    public Color Color2
    {
      get { return m_Color2; }
      set
      {
        if (m_Color1 == value)
          return;
        m_Color2 = value;
      }
    }
  }
}

Fortunately, Refactor! Pro provides a refactoring, called Create Backing Store, which converts an auto-implemented property into a standard property with a field backing store. In other words, it transforms this...

public Color Color1 { get; set; }

...into this.

private Color m_Color1;
public Color Color1
{
  get
  {
    return m_Color1;
  }
  set
  {
    m_Color1 = value;
  }
}

That's pretty close to what we want. With the help of two other refactorings, Introduce Setter Guard Clause and Collapse Accessor, we can continue to manipulate the property to get the code below.

private Color m_Color1;
public Color Color1
{
  get { return m_Color1; }
  set
  {
    if (m_Color1 == value)
      return;
    m_Color1 = value;
  }
}

Now we just have to make a minor edit to the guard clause and we're done.

View Screencast of These Refactorings in Action!

And that concludes my verse for today. Remember that the features I'm showing you are available for download this very second. So, if you're tired of waiting for <whisper>the other tool</whisper> to get its act together, Refactor! Pro can have you running laps through Visual Studio 2008 in no time.

posted on Wednesday, December 26, 2007 12:52:42 PM (Pacific Standard Time, UTC-08:00)  #    Comments [0]

kick it on DotNetKicks.com
 Tuesday, December 25, 2007

Presents

Merry X-mas friends! It is indeed X-mas day, and I have returned with a special gift for you. Today, I'm doing my part to bring peace on earth and goodwill toward developers by showing one way that Refactor! Pro can simplify the dreaded lambda expressions. I'll achieve this by showing three refactorings which can be used together to transform some very C-ish code into modern C# 3.0 code.

And now, it's time to continue my anthem.

There's a hush. All is quiet. Then, in the silence, a still, small voice is heard. It grows louder and louder until...

"On the sixth day of X-mas my true love (DevExpress) gave to me..."

Compress to Lambda Expression

I'm not exactly sure why, but every time that I mention "lambda expressions" to developers, their faces show confusion and terror. My guess is that this reaction is caused by one of three things:

  1. A fear of Greek letters (i.e. "lambda")
  2. A fear of all things pointy (i.e. the => operator that lambda expressions bristle with.)
  3. A fear of all things functional (i.e. passing functions around like candy.)

It's for these reasons that I'll demonstrate a couple of other refactorings first. We'll work our way up to lambda expressions. Let's start with something more familiar.

using System;
using System.Collections.Generic;

namespace TwelveDaysOfXmas
{
  class CompressToLambdaExpression
  {
    public static int SumList(List<int> list)
    {
      int sum = 0;
      for(int i = 0; i < list.Count; i++)
        sum += list[i];
      return sum;
    }
  }
}

The code above is an example of the sort of imperative code that we write all of the time. What do I mean by "imperative?" Well, it's like writing a recipe for the computer—describing, in excruciating detail, the steps to solve a problem. There's nothing terribly wrong with that. After all, it's how our computer processors work. They execute a list of instructions—one at a time. However, there is another way that this code can be written.

On the other side of the coin from imperative code is declarative code. Declarative code describes what should be done instead of specifically how it should be done. Writing code declaratively has many potential benefits over the imperative style.

  1. It can be easier to read.
  2. It can be easier for the compiler/runtime to optimize.
  3. It can promote code reuse.

We can write the above code a bit more declaratively by using a foreach loop.

using System;
using System.Collections.Generic;

namespace TwelveDaysOfXmas
{
  class CompressToLambdaExpression
  {
    public static int SumList(List<int> list)
    {
      int sum = 0;
      foreach (int number in list)
        sum += number;
      return sum;
    }
  }
}

That's better! To save keystrokes, Refactor! Pro provides a For to ForEach refactoring that easily performs this conversion. Here's how the preview hint for this refactoring looks:

For to ForEach Preview Hint

Another declarative possibility is to call the List<T>.ForEach method instead using of a foreach loop. In that case, we would pass an anonymous delegate to the method as the body of the loop like so:

using System;
using System.Collections.Generic;

namespace TwelveDaysOfXmas
{
  class CompressToLambdaExpression
  {
    public static int SumList(List<int> list)
    {
      int sum = 0;
      list.ForEach(delegate(int number)
      {
        sum += number;
      });
      return sum;
    }
  }
}}

In a declarative fashion, the above code states, "loop through the entire list, and execute this function (delegate) for each item in the list." A powerful feature of the anonymous delegate is that it references a variable (sum) outside of the delegate body, producing a closure. (For more information on closures, check out this article.)

Of course, Refactor! Pro provides a refactoring that renders this transformation trivial: Introduce ForEach Action. The screenshot below shows the preview hint for this refactoring.

Introduce ForEach Action Preview Hint

Now, some of you might be saying, "Whoa! That anonymous delegate sure is an ugly little spud1." You're right, it is. Enter the lambda expression.

I don't want to present an entire history of lambda expressions here, but you should understand that they pre-date computers entirely. So, if you've been wondering where these crazy new things came from, know that they really aren't crazy "new" things. Lambda expressions have been around since the 1930s.

A C# lambda expression is really just an anonymous delegate on steroids. It retains all of the functionality of an anonymous delegate but adds conciseness, better type inference and even pseudo-meta-programming via expression trees.

Using a lambda expression is straight-forward, if a little funky:

using System;
using System.Collections.Generic;

namespace TwelveDaysOfXmas
{
  class CompressToLambdaExpression
  {
    public static int SumList(List<int> list)
    {
      int sum = 0;
      list.ForEach(number => sum += number);
      return sum;
    }
  }
}

If this is the first time that you've seen a lambda expression in the wild, compare it with the anonymous delegate that we used before. The parameters are declared to the left of the => operator, and the body is declared to the right. The compiler works out the types of the parameters so there's no need to specify them.

Of course, my X-mas present for you today is another refactoring: Compress to Lambda Expression. This refactoring (available now) converts anonymous delegates into lambda expressions, saving dozens of keystrokes and head scratches. Again, here is the preview hint to show what this refactoring does:

Compress to Lambda Expression Preview Hint

View Screencast of These Refactorings in Action!

As always, I'm demonstrating features of Refactor! Pro that can be used to leverage the new features in Visual Studio 2008 right now. In fact, all of the refactorings above have been shipping for several months. In other words, these aren't in some super-secret beta. They have been released.

As another refactoring goodie has been successfully unwrapped, it's time to take my leave of you. Until tomorrow, have a warm and happy X-mas!

1Ray Stanz, Ghostbusters.

posted on Tuesday, December 25, 2007 9:31:26 AM (Pacific Standard Time, UTC-08:00)  #    Comments [2]

kick it on DotNetKicks.com
 Monday, December 24, 2007

Nutcracker

'Twas the night before X-mas, when all through the house,
Not a creature was stirring, not even a mouse;
The stockings were hung by the chimney with care,
In hopes that DevExpress soon would be there;
The children were nestled all snug in their beds,
While visions of
Refactor! Pro danced in their heads.

Ho, ho, ho! I'm back to stuff your stockings with another feature of Refactor! Pro that lets you leverage Visual Studio 2008 on this fine X-mas Eve.

But wait! Who's that knocking at your front door? Why it's a group of carolers, here to sing a noël for us. Shhh! They're about to begin.

"On the fifth day of X-mas my true love (DevExpress) gave to me..."

Convert to Auto-Implemented Property

One of the tastiest syntactic sugar cookies that has been added to C# 3.0 is Auto-Implemented Properties. This feature allows C# developers to define properties far more concisely than before. Here's how we used to define properties in C# 2.0:

using System;
using System.Drawing;

namespace TwelveDaysOfXmas
{
  class Present
  {
    private Color m_Color;
    private bool m_HasBow;

    public Present(Color color, bool hasBow)
    {
      m_Color = color;
      m_HasBow = hasBow;
    }

    public Color Color
    {
      get { return m_Color; }
    }
    public bool HasBow
    {
      get { return m_HasBow; }
      set { m_HasBow = value; }
    }
  }
}

Whew! That's a lot of effort! Thanks to auto-implemented properties, we can now define our properties like so:

using System;
using System.Drawing;

namespace TwelveDaysOfXmas
{
  class Present
  {
    public Present(Color color, bool hasBow)
    {
      Color = color;
      HasBow = hasBow;
    }

    public Color Color { get; private set; }
    public bool HasBow { get; set; }
  }
}

Convert to Auto-Implemented Property is a refactoring that can be used to change the first example into the second example. Check out the preview hint below to see everything that this refactoring will do for you.

Convert to Auto-Implemented Property Preview Hint

  1. It removes the field that serves as the backing store for the property.
  2. It converts all field references into references to the property.
  3. It replaces the property with an auto-implemented version. I should point out that the refactoring intelligently generates an auto-implemented property with a private setter because the property is read-only (write-only properties are handled similarly).
  4. There is also a Convert to Auto-Implemented Property (convert all) refactoring which will transform all of the properties in the current type.

That's all there is to it! This refactoring does exactly what you expect it to do, and using it will save you dozens of keystrokes.

Unfortunately, our Visual Basic friends aren't feeling the love. You see, auto-implemented properties is a C# 3.0-only feature that did not make it into Visual Basic 9. However, it would be shameful to leave any developer out in the cold. At the request of the Visual Basic team, we've added a new feature that provides the illusion of auto-implemented properties in Visual Basic.

VB Property Collapse 1

The above screenshot shows what the code looks like as it is being edited. As you can see, no changes have been made yet. However, once the editor caret leaves the property, the field and property automatically collapse onto one line:

VB Property Collapse 2

View Screencast of VB Property Collapse in Action!

That sleight-of-hand helps VB code appear more concise. I hope this will help our Visual Basic friends feel a warm glow this holiday season.

And with that, I must bid you farewell. Until next time...

He spoke not a word, but went straight to his work,
And filled all the stockings; then turned with a jerk,
And laying his finger aside of his nose,
And giving a nod, up the chimney he rose.
He sprang to his sleigh, to his team gave a whistle,
And away they all flew, like the down of a thistle:
But I heard him exclaim, as he drove out of sight—
Merry X-mas to all, and to all a good night.

posted on Monday, December 24, 2007 7:39:36 AM (Pacific Standard Time, UTC-08:00)  #    Comments [0]

kick it on DotNetKicks.com
 Sunday, December 23, 2007

Santa Cat

Feliz Navidad my mistletoe aficionados! I've just finished warming up my voice and am ready to continue my aria of Refactor! Pro support for Visual Studio 2008. Ready or not, here we go!

And a one, and a two, and a one, two, three, four!

"On the fourth day of X-mas my true love (DevExpress) gave to me..."

Rename Works In Query Expressions

Today, instead of examining a brand new feature, we'll see how a pre-existing refactoring handles the new features of C# 3.0 and Visual Basic 9. Adding support for new language features involves much more than simply creating a handful of new refactorings—all existing refactorings must be updated as well. With Refactor! Pro, you can be confident that we've done our homework and provided support for Visual Studio 2008 across the entire product.

Of all the refactorings available to me, I use Rename the most frequently. This is due to the fact that I use Refactor! Pro to shape my code while I write it. Often, while coding a solution, I find that a variable's meaning is no longer consistent with its name. When this happens, Rename allows me to change the variable's name efficiently and accurately. In fact, I've used Rename so often that I've grown to trust it implicitly.

Rename doesn't let me down when I'm working with a C# 3.0 query expression. With the editor caret positioned on the identifier of the from clause, I can press the Refactor key (CTRL+` on my machine), and Rename kicks in, highlighting the active identifier and all its references.

Rename in C# Query Expression (start)

At this point, I can just type the new variable name. All references are updated in real time.

Rename in C# Query Expression (end)

View Screencast of Rename in Action!

Rename also works perfectly in an equivalent Visual Basic query expression (using fancy Aggregate syntax). Again, it's as easy as pressing the Refactor Key...

Rename in VB Query Expression (start)

...and typing the new variable name.

Rename in VB Query Expression (end)

Neat!

The moral of today's verse is that Refactor! Pro offers deep support for Visual Studio 2008 in every refactoring. You can rest assured that all refactorings just work as expected. And most importantly, they are working this very minute. Not tomorrow. Not sometime in January. Now.

Have a Merry X-mas!

posted on Sunday, December 23, 2007 12:22:04 PM (Pacific Standard Time, UTC-08:00)  #    Comments [0]

kick it on DotNetKicks.com
 Saturday, December 22, 2007

Nutcracker

Welcome back my 'nog-froth mustachioed friends! I've returned with another helping of Refactor! Pro goodness for Visual Studio 2008. One scrooge commented that the last present was a little weak, so I've decided to give a bigger gift this time. However, I will be saving some of my bestest presents for the very end.

So, sit back, relax and take out your ear plugs as I serenade you with my third verse.

"On the third day of X-mas my true love (DevExpress) gave to me..."

Name Anonymous Type

Of all the new features in C# 3.0 and Visual Basic 9, Anonymous Types is one of the most convenient. This feature allows the user to create new objects "on the fly," without providing type definitions for them. For example:

var person = new { Name = "St. Nick", Age = "Really Old" };
Console.WriteLine(person.Name);

When the C# compiler encounters the code above, it generates a new type with two string properties: Name and Age.

This powerful new feature is not without limitations. Because anonymous types have no accessible type name (they're anonymous - duh!), they can only be referenced by variables that are implicitly-typed. This becomes very frustrating when using anonymous types in other natural ways.

public static ??? CreatePerson()
{
  return new { Name = "St. Nick", Age = "Really Old" };
}

What should I fill in for ??? in the code above? One possibility is to use object. However, if I do that, how do I access the properties from client code? Reflection? An awkward casting helper?

Recently, this very problem was hashed out on the MSDN forums. The general consensus was, when you want to expose an anonymous type in an API (e.g. return an anonymous type from a method), swap it out for a defined type. However, defining a new type that matches an anonymous type is cumbersome. Thankfully, Refactor! Pro can step in and do this work for you. When the Name Anonymous Type refactoring is applied to the anonymous type above, the following class is generated:

[DebuggerDisplay("\\{ Name = {Name}, Age = {Age} \\}")]
public sealed class Person: IEquatable<Person>
{
  private readonly string m_Name;
  private readonly string m_Age;

  public Person(string name, string age)
  {
    m_Name = name;
    m_Age = age;
  }

  public override bool Equals(object obj)
  {
    if (obj is Person)
      return Equals((Person)obj);
    return false;
  }
  public bool Equals(Person obj)
  {
    if (!EqualityComparer<string>.Default.Equals(m_Name, obj.m_Name))
      return false;
    if (!EqualityComparer<string>.Default.Equals(m_Age, obj.m_Age))
      return false;
    return true;
  }
  public override int GetHashCode()
  {
    int hash = 0;
    hash ^= EqualityComparer<string>.Default.GetHashCode(m_Name);
    hash ^= EqualityComparer<string>.Default.GetHashCode(m_Age);
    return hash;
  }
  public override string ToString()
  {
    return String.Format("{{ Name = {0}, Age = {1} }}", m_Name, m_Age);
  }

  public string Name
  {
    get
    {
      return m_Name;
    }
  }
  public string Age
  {
    get
    {
      return m_Age;
    }
  }
}

View Screencast of Name Anonymous Type in Action!

You might be thinking, "Wow! That's a lot of code! Is all of that really necessary?" The answer is, yes, all of that code is necessary to produce a type definition that is equivalent to the subtle features of an anonymous type. In C#, anonymous types are immutable so we must generate read-only fields and properties. In addition, the equality and identity of anonymous types are explicitly defined so they can be compared with one another. In other words, C# anonymous types have value-type semantics. The following code sample might clarify this:

var person1 = new
{
  Name = "Dustin Campbell",
  Age = "32"
};

var person2 = new
{
  Name = "Dustin Campbell",
  Age = "32"
};

var person3 = new
{
  Name = "Dustin's Trophy Wife",
  Age = "Undisclosed (but probably really, really young)"
};

Console.WriteLine(person1.Equals(person2));
Console.WriteLine(person2.Equals(person3));

Because of the value-type characteristics of anonymous types, the above code outputs the following to the console.

True
False

Of course, if Name Anonymous Type is applied, the same output is produced.

Traditionally, the Visual Basic team likes to make life hard for us, and anonymous types are no exception. Contrary to C#, the Visual Basic compiler generates mutable anonymous types. In addition, Visual Basic allows for partially-mutable anonymous types when the Key keyword is applied. (This is further proof that C# and Visual Basic have very different agendas and destinies.) Fortunately, Name Anonymous Type is intelligent enough to handle these differences.

Dim person = New With {.Name = "St. Nick", .Age = "Really Old"}

When applied to the above code, Name Anonymous Type generates a new Person class like so:

<DebuggerDisplay("\{ Name = {Name}, Age = {Age} \}")> _
Public NotInheritable Class Person
  Private m_Name As String
  Private m_Age As String

  Public Sub New(ByVal name As String, ByVal age As String)
    m_Name = name
    m_Age = age
  End Sub

  Public Overrides Function ToString() As String
    Return String.Format("{{ Name = {0}, Age = {1} }}", m_Name, m_Age)
  End Function

  Public Property Name() As String
    Get
      Return m_Name
    End Get
    Set(ByVal value As String)
      m_Name = value
    End Set
  End Property
  Public Property Age() As String
    Get
      Return m_Age
    End Get
    Set(ByVal value As String)
      m_Age = value
    End Set
  End Property
End Class

To be consistent with the reference-type semantics of Visual Basic anonymous types, Name Anonymous Type produces a mutable class. Gone are the overrides to Equals() and GetHashCode(). In addition, the properties are read-write. It's this sort of language independence that makes Refactor! Pro a choice tool for Visual Studio 2008 development.

And that wraps up another verse in my holiday sing-a-long! Remember that the features I am showing can be used right now. There's no need to wait for some forthcoming beta. You can use them today. Until next time...

posted on Saturday, December 22, 2007 8:35:00 AM (Pacific Standard Time, UTC-08:00)  #    Comments [1]

kick it on DotNetKicks.com
 Friday, December 21, 2007

Fireplace

Season's greetings! Welcome back for another dose of Yuletide cheer! Yesterday, I sang to you about one way in which Refactor! Pro can be used to leverage the new features of C# 3.0 and Visual Basic 9 right now. Today, I'm back with another verse to warm your hearts this holiday season.

So, strike up the band! Rouse the drunken carolers! It's time to go a wassailing once more.

"On the second day of X-mas my true love (DevExpress) gave to me..."

Make Explicit

Like its sister refactoring, Make Explicit enables developers to manipulate implicitly-typed local variables. However, it performs the opposite operation as Make Implicit. It converts implicitly-typed local variables to explicit ones. In other words, Make Explicit will transform the following code:

var number = 42ul;

Like so:

ulong number = 42ul;

Make Explicit must do a great deal of work to determine the type of the expression that an implicitly-typed local variable is assigned to. Consider the following code (which I found lurking in some corner of the 'net):

using System;
using System.Linq;
using System.ServiceProcess;

namespace TwelveDaysOfXmas
{
  class MakeExplicit
  {
    static void DisplayServices()
    {
      var services = from service in ServiceController.GetServices()
                     where service.Status == ServiceControllerStatus.Running
                     orderby service.ServiceName ascending
                     select service;

      foreach (ServiceController aService in services)
      {
        Console.WriteLine(aService.ServiceName);
      }

      Console.ReadLine();
    }
  }
}

In order to determine the type of services, Make Explicit must have a full understanding of LINQ. First, it must transform the query expression into the appropriate extension methods and lambda expressions like so:

var services = ServiceController.GetServices()
                 .Where(service => service.Status == ServiceControllerStatus.Running)
                 .OrderBy(service => service.ServiceName)

Next, Make Explicit must be able to resolve the extension methods and infer the types of the lambda expressions. Once this is done, the type of the expression can finally be determined. That's an awful lot of work, but it's required to ensure that the type is inferred accurately. Fortunately, Make Explicit executes all of this with blazing speed and infers the correct type:

IOrderedEnumerable<ServiceController> services = from service in ServiceController.GetServices()
                                                 where service.Status == ServiceControllerStatus.Running
                                                 orderby service.ServiceName ascending
                                                 select service;

View Screencast of Make Explicit in Action! (#1)

If you have any doubt that Make Explicit is really doing this much work behind the scenes, try commenting out the orderby clause. Make Explicit will infer the correct type even after the query expression has changed:

IEnumerable<ServiceController> services = from service in ServiceController.GetServices()
                                          where service.Status == ServiceControllerStatus.Running
                                          //orderby service.ServiceName ascending
                                          select service;

View Screencast of Make Explicit in Action! (#2)

Finally, I should mention that Make Explicit works just as handily with Visual Basic.

Dim services = From service In ServiceController.GetServices() _
               Where service.Status = ServiceControllerStatus.Running _
               Order By service.ServiceName Ascending

In the above code, Make Explicit properly infers the type of services as IOrderedEnumerable<ServiceController>. Awesome.

One last closing thought: some of you might be thinking right now, "Why would I want to do this? Aren't implicitly-typed local variables better?" There are a few scenarios in which Make Explicit is useful:

  1. Specifying the type name sometimes makes code easier to read.
  2. It simplifies porting code backwards (e.g. to compile in an earlier version of Visual Studio).
  3. It can be helpful for learning and understanding code.

For these reasons, Make Explicit takes its rightful place among the refactorings that support Visual Studio 2008.

"And a partridge in a pear tree..."

And so concludes today's verse. It's time to settle back with a warm mug of spiked eggnog and kick up your feet. Join me tomorrow as we take a peek at another way in which Refactor! Pro brings the X-mas love.

posted on Friday, December 21, 2007 10:44:12 AM (Pacific Standard Time, UTC-08:00)  #    Comments [3]

kick it on DotNetKicks.com
 Thursday, December 20, 2007

Fireplace

Gentle readers, in the spirit of X-mas, I'd like to sing you a carol. This jolly tune (based on a popular old English carol) enumerates ways that Refactor! Pro can warm your installation of Visual Studio 2008 this holiday season. In contrast to some of our... ahem... <whisper>competition</whisper>, the features I'll be showing can be used today. In fact, most of these features have been shipping since Visual Studio 2008 was still a wee child known by its code name, Orcas.

But, hey, enough of my yammering! Stoke the fire and put on a kettle! Let the merry-making begin!

"On the first day of X-mas my true love (DevExpress) gave to me..."

Make Implicit

Visual Studio 2008 introduced a welcome addition to both the C# and Visual Basic languages: implicitly-typed local variables. While this feature is necessary to properly support another feature, anonymous types, it can also be used to enhance the readability of client code—especially when generic types are being used. Consider the following code:

private static Dictionary<string, Guid> BuildIdTable()
{
  Dictionary<string, Guid> map = new Dictionary<string, Guid>();

  // Fill map with entries...

  return map;
}

That sort of code can be a bit frustrating. Dictionary<TKey, TValue> is extremely powerful, but can be awkward to use. The developer is forced to fully declare the type name (which is often quite long) on both the left and right sides of the local variable declaration. Thankfully, an implicitly-typed local variable can alleviate this problem:

private static Dictionary<string, Guid> BuildIdTable()
{
  var map = new Dictionary<string, Guid>();

  // Fill map with entries...

  return map;
}

Now for the really good news: Refactor! Pro provides Make Implicit, a refactoring which easily converts explicitly-declared local variables to implicit ones. Check out the preview hint for Make Implicit:

View Screencast of Make Implicit in Action!

Of course, like most of our refactorings, Make Implicit works in Visual Basic as well.

Some critics might be thinking, "What's the point? It just deletes text and inserts a keyword! I could write a macro to do that!" Well, before those skeptics get too comfortable with their new macro, consider what Make Implicit must do with code like the following:

ulong number = 42;

If Make Implicit were simply to swap ulong for var, there would be a serious problem. Instead of ulong, the type of number would be inferred as int, changing the meaning of the code. To fix this problem, a minor adjustment is made to prevent shooting the code in its proverbial foot.

var number = 42ul;

So, throw your macro away! Let Make Implicit handle the edge cases intelligently.

Ho, ho, ho! That's quite a gift under the tree! Come back tomorrow when I continue my jaunty tune and look at another Visual Studio 2008-specific refactoring that is available to you today: Make Explicit.

posted on Thursday, December 20, 2007 10:31:39 AM (Pacific Standard Time, UTC-08:00)  #    Comments [0]

kick it on DotNetKicks.com
 Friday, November 23, 2007
Visual Studio 2008's multi-targeting support for compiling projects to different versions of the .NET Framework is very powerful. Multi-targeting is a compelling feature because it enables users to continue working on solutions that target .NET Framework 2.0 and 3.0 while upgrading to the latest and greatest IDE. What isn't obvious is that all projects, regardless of target, are compiled with the C# 3.0 compiler. That means users can employ many of the new C# 3.0 language features in legacy projects. The only language features that can't be used are those that require library support from .NET Framework 3.5, in essence, LINQ, Expression Trees and Extension Methods. Implicitly-typed local variables, lambda expressions, auto-implemented properties, object and collection initializers, and anonymous types are all fair game. It's sort of like having C# 3.0-lite or C# 2.5.

Interestingly, it has recently been discovered that even Extension Methods can be used in projects targeting .NET Framework 2.0 and 3.0. All that must be done to enable this support is to create a new System.Runtime.CompilerServices.ExtensionAttribute.

using System;

namespace System.Runtime.CompilerServices
{
  public class ExtensionAttribute: Attribute
  {
  }
}

This trick does have flaws. There are potential scoping issues that occur when an assembly containing a custom System.Runtime.CompilerServices.ExtensionAttribute is referenced by a project that targets .NET Framework 3.5. A compiler warning is generated stating that "the predefined type 'System.Runtime.CompilerServices.ExtensionAttribute' is defined in multiple assemblies in the global alias." However, this is only a minor irritation. In my tests, Extension Methods still worked properly despite the warning.

The ability to use C# 3.0 features in .NET Framework 2.0 or 3.0 projects is very powerful. It helps users get comfortable with the new syntax without having to upgrade projects to .NET Framework 3.5. Viva la C# 2.5!

posted on Friday, November 23, 2007 7:29:08 AM (Pacific Standard Time, UTC-08:00)  #    Comments [5]

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

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

kick it on 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
 Friday, September 28, 2007

Recently, I presented an example of how closures can cause headaches when used in the context of LINQ expressions:

static class Program
{
  static void Main()
  {
    var filter = String.Empty;
 
    var query = from m in typeof(String).GetMethods()
                orderby m.Name
                where m.Name != filter
                select m.Name;
 
    foreach (var item in query)
    {
      Console.WriteLine(item);
      filter = item;
    }
  }
}

I want to state clearly that the example above is academic and not representative of how anybody should be writing LINQ code. This was implied by the intentionally-alarmist title of my post ("LINQ Closures May Be Hazardous to Your Health!"), but some readers missed the point. Let's take a closer look at what, exactly, is wrong with this LINQ code and how it should be properly written.

First of all, the example code exhibits several nasty smells:

  1. It isn't portable. There's no guarantee that other LINQ providers will actually support closures.
  2. It isn't maintainable. The code is an obvious maintenance headache—especially if it will be handled by more than one person.
  3. It isn't declarative. LINQ syntax is designed to be declarative, but this code mixes in imperative logic.
  4. It isn't flexible. The closure voodoo inhibits potential optimizations that might occur with future technologies like Parallel LINQ.

In addition to the negative consequences listed above, the closure exploited in the sample is completely unnecessary! Closures can sometimes be powerful, but this isn't really the place to exploit them. In fact, writing code like that betrays a lack of knowledge of LINQ's standard query operators. LINQ already provides an easy way to ensure that duplicate values are removed from a query expression: the Distinct operator.

Distinct is one of several query operators designed to perform set operations on queries (the other operators are Except, Intersect and Union). Using Distinct in place of the closure solves all of the afore-mentioned problems and, as a bonus, makes the code more concise.

static void Main()
{
  var query = (from m in typeof(String).GetMethods()
              orderby m.Name
              select m.Name).Distinct();
 
  foreach (var item in query)
    Console.WriteLine(item);
}

Not surprisingly, Visual Basic takes this a step further by adding a new "Distinct" keyword.

Sub Main()
  Dim query = From m In GetType(String).GetMethods() _
              Order By m.Name _
              Select m.Name _
              Distinct
 
  For Each item In query
    Console.WriteLine(item)
  Next
End Sub

However, this new keyword only gives me a mild case of VB Envy. I really like the fact that Distinct is syntax highlighted, but I much prefer how the parentheses better delineate the query expression in the C# version.

I hope this clears up any confusion that my other post might have caused. LINQ syntax is designed to be simply and declarative. Don't let your code get too fancy, and you'll reap the benefits of LINQ.

posted on Friday, September 28, 2007 9:47:20 AM (Pacific Standard Time, UTC-08:00)  #    Comments [0]

kick it on DotNetKicks.com
 Tuesday, September 25, 2007
UPDATE (Sep. 28, 2007): This article is really academic in nature on the topic of closures and how they fit into LINQ query expressions. It contains a highly-contrived example that is not representative of quality LINQ code. For more information, take a look at this post.

To me, one of the most interesting aspects of LINQ query expressions is that they produce lexical closures (for a detailed look at closures in C#, see my article on the topic). To illustrate this point, consider the following code:

static void Main()
{
  var filter = "Compare";
 
  var query = from m in typeof(String).GetMethods()
              where m.Name.Contains(filter)
              select new { m.Name, ParameterCount = m.GetParameters().Length };
 
  foreach (var item in query)
    Console.WriteLine(item);
 
  Console.WriteLine();
  Console.WriteLine("--- press any key to continue ---");
  Console.ReadKey();
}

This query retrieves all of the public methods on System.String whose names contain the text represented by the "filter" variable (in this case "Compare"). When compiled and run, the output is what you might guess:

{ Name = Compare, ParameterCount = 2 }
{ Name = Compare, ParameterCount = 3 }
{ Name = Compare, ParameterCount = 3 }
{ Name = Compare, ParameterCount = 4 }
{ Name = Compare, ParameterCount = 5 }
{ Name = Compare, ParameterCount = 6 }
{ Name = Compare, ParameterCount = 7 }
{ Name = Compare, ParameterCount = 6 }
{ Name = CompareTo, ParameterCount = 1 }
{ Name = CompareTo, ParameterCount = 1 }
{ Name = CompareOrdinal, ParameterCount = 2 }
{ Name = CompareOrdinal, ParameterCount = 5 }

--- press any key to continue ---

That behavior should be perfectly natural to any C# developer. Here's where things get a little tricky:

var filter = "Compare";

var query = from m in typeof(String).GetMethods()
            where m.Name.Contains(filter)
            select new { m.Name, ParameterCount = m.GetParameters().Length };

filter = "IndexOf";

foreach (var item in query)
  Console.WriteLine(item);

Can you guess what that code will output to the console?

Your answer to that question depends on your understanding of what closures are and how they work. A closure is produced when a variable whose scope extends beyond the current lexical block is bound to that block. That's a bit of a mouthful, isn't it? Allow me to clarify what I mean with a simple example.

delegate void Action();
 
static void Main()
{
  int x = 0;
 
  Action a = delegate { Console.WriteLine(x); };
 
  x = 1;
 
  a();
}

In the code above, an anonymous delegate ("a") references a variable ("x") that is declared outside of the anonymous delegate's body. This implies a lexical closure, and the variable "x" is bound to the method body of "a." The important point is that "a" is bound to the variable "x" and not its value. In other words, the value that "a" writes to the console depends upon the value of "x" at the time of its execution. Because 1 is assigned to "x" immediately before "a" is executed, 1 is output to the console.

Precisely the same thing happens in our query expression. A closure is produced for the lambda expression of the "where" clause because it references the "filter" variable, which is declared outside of the query expression. The closure binds to the variable "filter"—not its value. So, changing the value of "filter" after the query expression is defined will change the results returned by the query. In fact, if you run that code, you'll get this:

{ Name = IndexOf, ParameterCount = 3 }
{ Name = IndexOfAny, ParameterCount = 3 }
{ Name = LastIndexOf, ParameterCount = 3 }
{ Name = LastIndexOfAny, ParameterCount = 3 }
{ Name = IndexOf, ParameterCount = 1 }
{ Name = IndexOf, ParameterCount = 2 }
{ Name = IndexOfAny, ParameterCount = 1 }
{ Name = IndexOfAny, ParameterCount = 2 }
{ Name = IndexOf, ParameterCount = 1 }
{ Name = IndexOf, ParameterCount = 2 }
{ Name = IndexOf, ParameterCount = 3 }
{ Name = IndexOf, ParameterCount = 2 }
{ Name = IndexOf, ParameterCount = 3 }
{ Name = IndexOf, ParameterCount = 4 }
{ Name = LastIndexOf, ParameterCount = 1 }
{ Name = LastIndexOf, ParameterCount = 2 }
{ Name = LastIndexOfAny, ParameterCount = 1 }
{ Name = LastIndexOfAny, ParameterCount = 2 }
{ Name = LastIndexOf, ParameterCount = 1 }
{ Name = LastIndexOf, ParameterCount = 2 }
{ Name = LastIndexOf, ParameterCount = 3 }
{ Name = LastIndexOf, ParameterCount = 2 }
{ Name = LastIndexOf, ParameterCount = 3 }
{ Name = LastIndexOf, ParameterCount = 4 }

--- press any key to continue ---

Let's try to exploit this closure in a more practical way.

var filter = String.Empty;

var query = from m in typeof(String).GetMethods()
            where m.Name != filter
            select m.Name;

foreach (var item in query)
{
  Console.WriteLine(item);
  filter = item;
}

This slightly different query expression returns the names of all of the public methods on System.String that don't match the value of the variable "filter." By modifying "filter" in each iteration of the foreach loop, we are effectively filtering out all duplicate method names. This works as advertised, but there's one potential bug: it is assumed that all overloads of a method are grouped together. If there are overloads of, say, String.CompareTo that aren't adjacent in the source array, the filtering won't work properly. What we really need to do is sort the array using the "orderby" query operator.

var query = from m in typeof(String).GetMethods()
            where m.Name != filter
            orderby m.Name
            select m.Name;

WHOOPS! That doesn't work. When we execute that query, all of the method names are output to the console, including duplicates. Our modifications to the "filter" variable in the foreach loop are completely ignored. Why is that?

The reason is that "orderby" forces the entire query to be evaluated when the first element is requested. This behavior is unavoidable and breaks the normal delayed evaluation of a query expression. However, we can still make the closure work properly by ensuring that the sort happens before filtering.

var query = from m in typeof(String).GetMethods()
            orderby m.Name
            where m.Name != filter
            select m.Name;

Now we get the output that we want:

Clone
Compare
CompareOrdinal
CompareTo
Concat
Contains
Copy
CopyTo
EndsWith
Equals
Format
get_Chars
get_Length
GetEnumerator
GetHashCode
GetType
GetTypeCode
IndexOf
IndexOfAny
Insert
Intern
IsInterned
IsNormalized
IsNullOrEmpty
Join
LastIndexOf
LastIndexOfAny
Normalize
op_Equality
op_Inequality
PadLeft
PadRight
Remove
Replace
Split
StartsWith
Substring
ToCharArray
ToLower
ToLowerInvariant
ToString
ToUpper
ToUpperInvariant
Trim
TrimEnd
TrimStart

--- press any key to continue ---

The moral here is to be careful. Exploiting closures in query expressions can be powerful but tricky to get right.

posted on Tuesday, September 25, 2007 6:53:23 AM (Pacific Standard Time, UTC-08:00)  #    Comments [1]

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, September 19, 2007
There's been some interest recently in the new XML literal feature coming to Visual Basic 9. If you're not familiar with this feature, the idea is that you can embed XML directly into VB code like this:
Sub Main()
  Dim publicationdate = Date.Today
  Dim isbn = 42
  Dim price = 0.99D
  Dim firstName = "Dustin"
  Dim lastName = "Campbell"

  Dim book = <book publicationdate=<%= publicationdate %> ISBN=<%= isbn %>>
               <title>F#: For The Excessively Nerdy</title>
               <price><%= price %></price>
               <author>
                 <first-name><%= firstName %></first-name>
                 <last-name><%= lastName %></last-name>
               </author>
             </book>
End Sub

That compiles to something similar to this:

Public Sub Main()
  Dim publicationdate As Date = Date.Today
  Dim isbn As Integer = 42
  Dim price As Decimal = 0.99
  Dim firstName As String = "Dustin"
  Dim lastName As String = "Campbell"
 
  Dim book = New XElement("book", _
                          New XAttribute("publicationdate", publicationdate), _
                          New XAttribute("ISBN", isbn), _
                          New XElement("title", "F#: For The Excessively Nerdy"), _
                          New XElement("price", price), _
                          New XElement("author", _
                                       New XElement("first-name", firstName), _
                                       New XElement("last-name", lastName)))
End Sub

To me, this is a great example of what syntactic sugar should be all about: making tasks easier for developers. The VB team has gone to great pains to expose the new APIs in System.Xml.Linq in the most intuitive way possible. As a C# guy, I'm shamefully filled with deep feelings of VB envy.

Since I spend most of my time working on a wholly remarkable refactoring tool, you might be wondering what sort of refactoring support we have in store for these snazzy new XML literals. How about Extract Method?

Here's the preview hint that is displayed for Extract Method when the XML literal is selected:

Extract Method on XML Literal

And here's the successfully refactored code after applying Extract Method:

Private Function GetBook(ByVal publicationdate As Date, ByVal isbn As Integer, _
                         ByVal price As Decimal, ByVal firstName As String, _
                         ByVal lastName As String) As XElement
 
  Return <book publicationdate=<%= publicationdate %> ISBN=<%= isbn %>>
           <title>F#: For The Excessively Nerdy</title>
           <price><%= price %></price>
           <author>
             <first-name><%= firstName %></first-name>
             <last-name><%= lastName %></last-name>
           </author>
         </book>
End Function
 
Sub Main()
  Dim publicationdate = Date.Today
  Dim isbn = 42
  Dim price = 0.99D
  Dim firstName = "Dustin"
  Dim lastName = "Campbell"
 
  Dim book = GetBook(publicationdate, isbn, price, firstName, lastName)
End Sub

Notice the pieces that Refactor! must have to be in place to get this right:

  • The refactoring must be smart enough to understand how the XML literal is transformed into XElements, XAttributes and XNames under the hood.
  • The refactoring must identify any dependant variables that are referenced within the embedded expressions of the XML literal.
  • The refactoring must infer the types of the dependant variables in order to declare the parameters of the new method.

We still have some work to do before Visual Studio 2008 reaches the RTM stage, but it looks like things are shaping up nicely.

posted on Wednesday, September 19, 2007 6:21:21 AM (Pacific Standard Time, UTC-08:00)  #    Comments [0]

kick it on DotNetKicks.com
 Friday, August 17, 2007
Several weeks ago, I posted this bit of code that shows how we might use a C# 3.0 query expression to calculate the sum of the squares of an array of integers.
static void Main()
{
  var numbers = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };

  var
sum = (from n in numbers
             where (n % 2) == 0
             select n * n).Sum();

  Console
.WriteLine("Sum: {0}", sum);
}

Translating this sample into Visual Basic 9.0 produces almost identical code.

Sub Main()
  Dim numbers() = New Integer() {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}

  Dim
total = (From n In numbers _
               Where (n Mod 2) = 0 _
               Select n * n).Sum()

  Console.WriteLine("Sum: {0}", total)
End Sub

However, this translation is a bit naive because Visual Basic 9.0 actually provides syntax for more of the standard query operators than C# 3.0 does. While we have to call the "Sum" query operator explicitly in C#, Visual Basic allows us to use it directly in the query.

Sub Main()
  Dim numbers() = New Integer() {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}

  Dim
total = Aggregate n In numbers _
              Where (n Mod 2) = 0 _
              Select n * n _
              Into Sum()

  Console.WriteLine("Sum: {0}", total)
End Sub

In fact, Visual Basic even allows us to create our own aggregate functions and use them directly in query expressions.

<Extension()> _
Function Product(ByVal source As IEnumerable(Of Integer)) As Integer
  Dim
result = 1
  For Each n In source
    result *= n
  Next
  Return
result
End Function

Sub
Main()
  Dim numbers() = New Integer() {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}

  Dim total = Aggregate n In numbers _
              Where (n Mod 2) = 0 _
              Select n _
              Into Product()

  Console.WriteLine("Sum: {0}", total)
End Sub

Here we get the product of the even numbers in the array. (I removed the expression to square each even number because it produced an OverflowException.)

I should point out that there is a behavioral difference that the Visual Basic "Aggregate" keyword introduces. A standard "From" query expression is delay evaluated. That is, the results aren't actually evaluated until they are accessed through, say, a "For Each" loop. However, an "Aggregate" query expression forces the results to be evaluated immediately. In contrast, C# 3.0 query expressions always produce results that are delay evaluated.1

1A bold statement that will be completely recanted if any reader can find an example that proves otherwise.2
2Please, prove me wrong. Seriously. I'm interested in this stuff.3
3This footnote motif is clearly ripped off from Raymond Chen.

posted on Friday, August 17, 2007 7:46:31 AM (Pacific Standard Time, UTC-08:00)  #    Comments [2]

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
 Friday, March 23, 2007
One of the greatest frustration of working with delegates and events is that they can potentially cause memory leaks if they aren't unhooked. In this article, we will solve this problem in a variety of ways to get the best performance, memory use and syntax.
posted on Friday, March 23, 2007 10:12:02 AM (Pacific Standard Time, UTC-08:00)  #    Comments [14]

kick it on DotNetKicks.com
 Monday, March 19, 2007
Delegates rock. But there's a dark side to them that can cause non-obvious bugs. Read on if you dare!
posted on Monday, March 19, 2007 12:00:13 PM (Pacific Standard Time, UTC-08:00)  #    Comments [1]

kick it on DotNetKicks.com
 Thursday, February 22, 2007
C# 3.0 Lambda expressions have distinct advantages over C# 2.0 anonymous methods. This article takes a look at how using lambda expressions can improve the compiler's type inference for generic methods.
posted on Thursday, February 22, 2007 6:10:30 AM (Pacific Standard Time, UTC-08:00)  #    Comments [2]

kick it on DotNetKicks.com
 Monday, February 19, 2007
At first, the syntax of C# 3.0 lambda expressions can be a bit intimidating. This article unravels the syntax to show that they are really anonymous methods on steroids.
posted on Monday, February 19, 2007 9:50:11 AM (Pacific Standard Time, UTC-08:00)  #    Comments [1]

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
 Friday, January 12, 2007
If you were wondering why the posts have slowed to a trickle here, it's because we were gearing for this grand new release.
posted on Friday, January 12, 2007 6:08:36 AM (Pacific Standard Time, UTC-08:00)  #    Comments [2]

kick it on DotNetKicks.com
 Saturday, November 25, 2006
posted on Saturday, November 25, 2006 7:12:43 AM (Pacific Standard Time, UTC-08:00)  #    Comments [1]

kick it on DotNetKicks.com
 Monday, November 20, 2006
This article looks at the potential performance issues of String.Format() when used with StringBuilder.
posted on Monday, November 20, 2006 9:26:03 AM (Pacific Standard Time, UTC-08:00)  #    Comments [6]

kick it on DotNetKicks.com
 Tuesday, October 24, 2006
Exploring some of the cool things you can do with extension methods in C# 3.0.
posted on Tuesday, October 24, 2006 10:13:49 AM (Pacific Standard Time, UTC-08:00)  #    Comments [6]

kick it on DotNetKicks.com
 Thursday, October 05, 2006
Today I was iterating a List<int> using a foreach loop and feeling a bit smug in knowing how much more performance-conscious I was being than if I'd tried doing the same thing with an ArrayList filled with ints. Thanks to the wonder of generics, the C# compiler neatly avoids numerous boxing operations by using a System.Collections.Generic.IEnumerator<int> instance instead of the older System.Collections.Generic.IEnumerator. Then I got to thinking: "is this really the fastest way?" Upon investigation, it turns that, no, it isn't the fastest way.
posted on Thursday, October 05, 2006 7:07:51 AM (Pacific Standard Time, UTC-08:00)  #    Comments [0]

kick it on DotNetKicks.com
 Wednesday, August 30, 2006
To me, enums in the .NET Framework 2.0 don’t feel like a polished feature. Writing serious code with them is a descent into typecasting madness filled with the maniacal laughter of bitwise ands and ors. Maybe the problem is that they are considered "good enough" or simply "not interesting enough" to improve. I mean, what’s more exciting to a compiler writer: enumerations or generics and lambda expressions? It’s possible that enums haven’t been improved simply because of time constraints or resources. But, in my humble opinion, it’s high time they deserved some love. In this article, I offer up my list of potential improvements for .NET enums. When possible, I present workarounds to implement the improvements with the current or next version of the .NET framework.
posted on Wednesday, August 30, 2006 10:49:47 AM (Pacific Standard Time, UTC-08:00)  #    Comments [1]

kick it on DotNetKicks.com
Responding to a user's comments about a warning raised by Microsoft's Code Analysis tool in Visual Studio Team System.
posted on Wednesday, August 30, 2006 4:17:27 AM (Pacific Standard Time, UTC-08:00)  #    Comments [5]

kick it on DotNetKicks.com
 Tuesday, August 29, 2006
After this evening's Northwest Ohio .NET User Group meeting, Jason Follas and I met up at Tony Packo's for a bit of post-meeting hangtime. In our conversation, Jason admitted his frustration at not being able to write code like this using C# generics...
posted on Tuesday, August 29, 2006 6:26:02 PM (Pacific Standard Time, UTC-08:00)  #    Comments [3]

kick it on DotNetKicks.com