Project Euler 6: Sum square difference in Functional Programming (FP)

Question

I wanted to practice functional programming (fp) without using any library but using vanilla JS only. So I took a problem from Project Euler:

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.

My solution in FP:

/*jshint esversion: 6*/
(function () {
  'use strict';

  const range = f => num => Array.from(new Array(num), f);
  const quadRange = range((_, i) => (i + 1) * (i + 1));
  const simpRange = range((_, i) => i + 1);
  const sum = (acc, val) => acc + val;
  const sumOfQuads = quadRange(100)
    .reduce(sum);
  const quadsOfSum = simpRange(100)
    .reduce(sum) * simpRange(100)
    .reduce(sum);
  console.log("solution ", quadsOfSum - sumOfQuads);
})();

Is there a better way to write it in FP (without any libraries and with vanilla JS only)?

Answer 1

Your code uses magic numbers and recalculates the same values over. So let's fix that first:

/*jshint esversion: 6*/
(function () {
  'use strict';

  const limit = 100; // 1
  const range = f => num => Array.from(new Array(num), f);
  const quadRange = range((_, i) => (i + 1) * (i + 1));
  const simpRange = range((_, i) => i + 1);
  const sum = (acc, val) => acc + val;
  const sumOfQuads = quadRange(limit)
    .reduce(sum);
  const simpleSum = simpRange(limit) // 2
    .reduce(sum);
  const quadsOfSum = simpleSum * simpleSum;
  console.log("solution ", quadsOfSum - sumOfQuads);
})();

We now have an easy changeable limit. Also, we do not create and reduce the array twice when calculating the square of the sum of the numbers.

However, that's really slow. Let's crank up the limit to 1000 and we see that the FP variant is 80% slower than a simple imperative one. That's because we create the array. A generator is much more suitable for this task. You could implement a range that has the same interface as an array, but doesn't actually compute anything until you reduce. It's reduce implementation will contain a single loop, but that's fine. We have to compromise at some point, since JS isn't a functional programming language. It has several FP features, like higher order functions, but it's still missing.

Languages like F# and Haskell on the other hand will get rid of the intermediate array/list in

(sum [1..limit])^2 - sum (map (^2) [1..limit])

That being said, we don't need the array to begin with, since there are closed formulas for both $$\sum_{i=1}^n i$$ and $$\sum_{i=1}^n i^2.$$

/*jshint esversion: 6*/
(function () {
  'use strict';

  const sumNumbersUpTo = n => 0; // exercise
  const sumNumbersSquaredUpTo = n => 0; // exercise

  const limit = 100;
  const sumOfQuads = sumNumbersSquaredUpTo(limit);
  const simpleSum = sumNumbersUpTo(limit);
  const quadsOfSum = simpleSum * simpleSum;
  console.log("solution ", quadsOfSum - sumOfQuads);
})();

Answer 2

DISCLAIMER: I don't think this is actually an "answer" answer. Please consider it as a side note, because your code generally looks good to me. I also admit, this answer is highly subjective compared to other my answers.. My purpose here is to provide a point of view rather than persuade that something needs to be fixed in the original code.

[Non-functional] alternative

In a real-life scenario, if num input was huge, you might not be able to create a range array via new Array(num).

Number.MAX_VALUE
// ---> 1.7976931348623157e+308

new Array(Number.MAX_VALUE)
// VM234:1 Uncaught RangeError: Invalid array length
//    at <anonymous>:1:1

Chrome:

Instead of that you could rewrite your range function as a generator function (at a "cost" of it not being an arrow function anymore):

function* range(num) { for (let counter = 1; counter <= num; counter++) yield counter; }

Unfortunately, this is also less functional on its own (notice that the code uses a let variable...). Worse than that, you can only

• either manually iterate over it via IterableIterator<> interface (requires a variable);
• or use for (let _ of range(Integer.MAX_VALUE) { ... } which isn't looking functional;
• or try materialize it into an array via spread operator [...range(Integer.MAX_VALUE)] (which will not work, for the same exact reason I'm mentioning the generator function).

I wish there was a commonly known first-class concept of a Range in JavaScript...

Naming Things

The only thing that pokes my eyes is variable naming. IMHO, you can do better than acc, val, or i. For example, the following is more readable, since real words are being used and the function is more explanatory.

const range = mapFunction =>
  rangeLength =>
    Array.from(new Array(rangeLength), mapFunction);

and

const summer = (subTotal, currentNumber) => subTotal + currentNumber;

summer is better than sum because a) sum as a word denotes the result of summation rather than something that encapsulates the summation logic; b) reads better in the usage. In fact, you can even write const sum = someArray.reduce(summer), or if you prefer better consumer readability over function name -- const sum = someArray.reduce(withSummer).

I know, these are tiny details, but for the reader they make a difference. Once mentioned it in another answer already -- I've witnessed a situation where in an inline function a developer interpreted acc as account. Silly? Yeah, but who cares when one needs to work on Friday evening to fix a bug?

Answer 3

Squaring numbers

Initially I considered suggesting the use of Math.pow() for the squaring of numbers but that might be considered using a library. I then found the exponentiation operator (i.e. **). Bearing in mind that it isn't supported in IE, MS Edge, or Chrome/FF prior to versions 52, it can greatly simplify the squaring of numbers.

Edit: Zeta pointed out that the exponentiation operation might not be optimized. A better approach would be to store the value of calculating the sum of the numbers in the range (calling the function once) and then squaring that resulting value.

limit number

For consistency, I would declare a constant for the limit - e.g. const limit = 100; and use that when calling quadRange and simpRange.

Sample

The example below takes the good advice of Igor and renames some variables like acc, sum,i, etc. Also, note that it only calls simpRange() (and the subsequent sum reduction) once.

(function () {
  'use strict';
  const limit = 100;
  const range = f => num => Array.from(new Array(num), f);
  const quadRange = range((_, index) => (index + 1) ** 2);
  const simpRange = range((_, index) => index + 1);
  const summer = (total, currentValue) => total + currentValue;
  const sumOfQuads = quadRange(limit)
    .reduce(summer);
  const sumOfNumbersInRange = simpRange(limit)
    .reduce(summer);
  const quadsOfSum = sumOfNumbersInRange * sumOfNumbersInRange ;
  console.log("quadsOfSum - sumOfQuads (",quadsOfSum, " - ",sumOfQuads,")  =", quadsOfSum - sumOfQuads);
})();