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.
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.
Page rendered at Sunday, May 19, 2013 4:57:56 AM (Pacific Standard Time, UTC-08:00)
If feel a bit behind and need to catch up on WPF, this is the book.
Great book on F# containing from Beginner to Advanced. It even has chapters on more arcane features of the language, such as Computation Expressions and Quotations.
Because this book provides source code in Standard ML, it's a fantastic
resource for learning F#. One bit of warning: this book does not teach classic
data structures. While structures such as binomial heaps and red-black trees
are presented, it is assumed that the reader already knows and understands
The opinions expressed herein are my own personal opinions and do not represent
my employer's view in any way.