Project Euler problem six is another easy one.

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

1² + 2² + ... + 10² = 385

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

(1 + 2 + ... + 10)² = 55² = 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.

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.

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.

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.

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

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:

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.

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

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

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.

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

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.

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.

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:

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.

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:

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

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

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.

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

F# can produce truly beautiful code indeed!

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:

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

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.

Short and sweet—my favorite!

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

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

What is the largest prime factor of the number 600851475143?

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

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

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

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

The basic algorithm is pictured as a flowchart below.

The following F# function implements our algorithm.

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.

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

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?

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:

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.

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.

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

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

That's just lovely.

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.

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

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.

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

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.

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

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.

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!

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.

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

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.

¹For 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.

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.

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.

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

That's beautiful.

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

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

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

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

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

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

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

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

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

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

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

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

That's much better!

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

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

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

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

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

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

But wait! There's more!

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

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

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

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

Now the code reads like an English sentence:

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

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

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

The possibilities are endless!

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

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

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

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

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

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

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

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

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

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

In addition, powerful list comprehensions are available.

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

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

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

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

You see? Trivial.

OK, let's define a couple of lists.

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

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

So, what do our lists look like now?

(Downshiftng to the imperative world...)

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

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

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

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

No problem.

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

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

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

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

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