Project Euler problem six is another easy one.

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

1^{2}+ 2^{2}+ ... + 10^{2}= 385

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

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

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.

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.

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

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:

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.

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 Friday, November 21, 2014 6:32:02 PM (Pacific Standard Time, UTC-08:00)

{12 Days of Refactor!} {Articles} {C#} {CodeRush} {Community} {Debugging} {Extending Visual Studio} {F#} {Feeble Attempts At Humor} {Functional Programming} {Geek Life} {History} {IntelliSense} {It's all about me} {Learning} {LINQ} {Microsoft} {Music} {Power Tools} {Project Euler} {Quality Code} {Rants} {Refactor!} {Speaking} {The Bleeding Edge} {Tips & Tricks} {Visual Basic} {Visual Studio} {Why I Love F#} {XML Literals} {Z-Machine} |

WPF 4 Unleashed

Adam Nathan

If feel a bit behind and need to catch up on WPF, this is **the** book.

Programming F#

Chris Smith

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.

Purely Functional Data Structures

Chris Okasaki

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

World War Z: An Oral History of the Zombie War

Max Brooks

That's right. This isn't a programming book. It's a

*diversion*. Reading programming books all of the time is hazardous to your happiness and well-being. Take the time to enjoy something else. You'll thank me later.

**Disclaimer**

The opinions expressed herein are my own personal opinions and do not represent
my employer's view in any way.

This work is licensed under a Creative Commons Attribution 3.0 United States License.

© Copyright 2014 Dustin Campbell

Sign In