Project Euler 5: Smallest multiple in Functional Programming (fp)

Question

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

/*jshint esversion: 6*/
(function () {
  'use strict';
  const leastCommonMultiple = (n, multiple, max) => n === max ?
    multiple :
    leastCommonMultiple(n + 1, multiple * (n + 1) / greatestCommonDivisor(
      multiple, (n + 1)), max);

  const greatestCommonDivisor = (a, b) => 0 === b ? a : greatestCommonDivisor(
    b, a % b);

  console.log("Solution: ", leastCommonMultiple(1, 1, 20));
})();

Is there a way to write leastCommonMultiple with less parameters and still be consistent with fp? Any other improvement suggestions are welcomed as well!

Answer 1

Well, this is Code Review, so let's be picky. First, remember that superLongVariableNamesThatTakeSeveralMinutesToWrite are for IDE-assisted object-oriented enterprise programming in Java where a recursive call is so unusual you'd record it as a Very Special Day in your diary.

Functional programmers don't have time for that nonsense, so start by writing:

const gcd = (a,b) => 0 === b ? a : gcd(b, a % b)

When it comes to writing lcm, a functional programmer probably wouldn't write a version that calculates the (1) least common multiple of (2) several values produced by (3) iterating over integers because that's three different concepts, and functional programmers' heads are so crammed with greek letters and category theory that they can only concentrate on one thing at a time. So, we'll have to be content with an lcm function that operates on only two numbers:

const lcm = (a,b) => a * b / gcd(a,b)

Second, no self-respecting functional programmer would be caught dead without a fold function (AKA reduce), whether she needed it or not, so let's be sure to write one now and worry about finding a way to use it later:

const reduce = (f,xs) => 1 === length(xs) ? xs[0] 
      : f(xs[0], reduce(f,xs.slice(1)))

A couple tests ensure it's working:

> reduce((x,y) => x+y, [1,2,3,4,5])
15
> reduce((x,y) => x*y, [1])
1
> reduce((x,y) => x*y, [])
RangeError: Maximum call stack size exceeded
   at reduce (repl:1:72)
   at reduce (repl:1:60)
   ...

Oh, well, close enough. we'll leave unit testing to some junior programmer (or an intern, who would probaly be clever enough to realize that Array.reduce is already vanilla JS).

Third, since we agree that explicit iteration is for imperative programming chumps, we'll write a tail recursive function for generating arrays of integer ranges:

const seq = (m,n) => m > n ? [] : [i].concat(step(m+1,n))

and a few tests:

> seq(5,10)
[5,6,7,8,9,10]
> seq(1,20)
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]
> seq(1,1000000)
RangeError: Maximum call stack size exceeded
>

Oh, yeah, we forgot to make it tail recursive... Again, we really need to hire that junior programmer.

ANYWAY, armed with this selection of functions:

const gcd = (a,b) => 0 === b ? a : gcd(b, a % b)
const lcm = (a,b) => a * b / gcd(a,b)
const seq = (m,n) => m > n ? [] : [m].concat(seq(m+1,n))
const reduce = (f,xs) => 1 === xs.length ? xs[0]
      : f(xs[0], reduce(f,xs.slice(1)))

the program really writes itself:

> console.log(reduce(lcm, seq(1, 20))
232792560
>

And seriously, while I was writing this up a little tongue-in-cheek, this is really how functional programming is supposed to work.

Instead of writing a function leastCommonMultiple with a long name that tries to do multiple things:

• count up from 1 to max
• maintain an accumulator of results
• calculate pairwise LCMs using the greatestCommonDivsor helper

you:

• write functions with short names like lcm that do simple things like calculating the LCM of two numbers
• take algorithms like folding a list of values into an accumulator using a binary operator and abstract them into higher order, reusable functions like reduce
• compose these simple functions together to write more complex programs

As a side note, from a practical standpoint, my seq and reduce leave much to be desired. In Javascript, building an array recursively with concat is not a sane way to create an array of sequential integers (and my reduce is really no better). Of course, that's why we have libraries like Lodash, to provide optimized implementations of these common building blocks.

Which brings me to my last point. If you're an FP beginner, I don't think you're likely to benefit much from trying to write FP code in vanilla Javascript without any external libraries. The main reason these external libraries exist is that FP programming in vanilla Javascript is tedious, inefficient, error-prone, unpleasant, and a host of other distasteful adjectives.

A programmer who is already experienced with FP can write decent FP programs in vanilla Javascript (but is probably smart enough not to try). Programmers who are trying to improve their FP skills are better off using an FP-friendly library that will encourage writing good FP code.

If you want to get better at FP in Javascript, install a library that supports FP programming, work through its tutorials, and make heavy use of it:

// Euler 1
var _ = require('lodash')
console.log(_.sum(_.filter(_.range(1000), 
    (x) => (x % 3 === 0) || (x % 5 === 0))))
console.log("Awesome!")

Answer 2

You can define a cumulative least common multiple function clcm as clcm(1) = 1 and clcm(n) = lcm(n,clcm(n-1)) if n>1.