2
\$\begingroup\$

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,

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.

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)?

\$\endgroup\$
  • \$\begingroup\$ For those downvoting this question: Please provide an explanation so I don't repeat the mistake twice. \$\endgroup\$ – thadeuszlay Jan 5 '18 at 11:29
3
\$\begingroup\$

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);
})();
\$\endgroup\$
  • \$\begingroup\$ So, you would say using JS-generators is consistent with FP? \$\endgroup\$ – thadeuszlay Jan 3 '18 at 9:41
  • \$\begingroup\$ @thadeuszlay since I don't know JS generators, I can't say whether they're suitable, I'm talking about the general concept of generators. Also, this is JS. JS doesn't have recursive types, where we could easily traverse a list. We're using Array.prototype.map, which isn't implemented in FP style. However, a proper generator (still talking about generic generators) will be: side-effect free, immutable (map returns a new generator, reduce a single value), and support higher-order functions. Array.new is close, but you're looking for something with the same interface, without actual memory. \$\endgroup\$ – Zeta Jan 3 '18 at 11:42
3
\$\begingroup\$

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: enter image description here

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?

\$\endgroup\$
  • \$\begingroup\$ acc is a common name of the accumulator in functional programming languages. \$\endgroup\$ – Zeta Jan 3 '18 at 7:34
  • 1
    \$\begingroup\$ @Zeta I heard that a lot, yet bugs are coming from such "common names"/"abbreviations". I don't see any harm in making the name more descriptive. \$\endgroup\$ – Igor Soloydenko Jan 3 '18 at 7:36
  • \$\begingroup\$ Functional programming languages tend to be strongly and statically typed, therefore using the wrong name by accident usually results in a type error---which of course doesn't hold for pure JS. \$\endgroup\$ – Zeta Jan 3 '18 at 7:43
  • \$\begingroup\$ @Zeta This question is specifically in the context of ES6, which will not slap a developer for such bug anyway. Moreover, the type for acc[umulator] and acc[ount] might accidentally match, which will make it impossible to catch the issue. I am not willing to argue about that because I've had this conversation like hundred times and I believe that a few more keystrokes (actually, F2 or Ctrl+R, Ctrl+R in an editor) make code better without relying on cryptic "known" names. I prefer to spend my brain cycle on actual code rather than details including in-memory abbreviation expansion. \$\endgroup\$ – Igor Soloydenko Jan 3 '18 at 7:47
  • \$\begingroup\$ @Zeta If you strongly disagree with my naming proposal(s), feel free to down vote. This is what the voting system is made for. I just don't see how fully-specified names are harmful. (To extend on that topic. I recently had an argument about names like i and j which I find pure evil nonsense. My opponent was trying to make the point those names are well-known in the industry. Nevertheless, the names are cryptic and brain-cycles consuming in my opinion. That argument ended without an agreement. This is exactly why I highlighted that my review is subjective.) \$\endgroup\$ – Igor Soloydenko Jan 3 '18 at 7:51
1
\$\begingroup\$

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);
})();

\$\endgroup\$
  • \$\begingroup\$ Keep in mind that x ** 2 needs to get optimized by the interpreter to x * x, whereas the latter is already in "optimal" form. \$\endgroup\$ – Zeta Jan 3 '18 at 6:41
  • \$\begingroup\$ I have updated my explanation, taking that fact into consideration \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ Jan 3 '18 at 17:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.