Sum of multiples of 3 or 5 using functional programming

Question

I wanted to practice functional programming (fp) without using any library. So I took the 1st problem from project euler:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

My solution in fp looks like this:

const isDivisibleBy = i => number => i % number === 0;
const selected = criteria => (...numbers) => i => numbers.filter(criteria(i))
    .length > 0;
const getSumOf = conditionFor => (sum, _, i) => conditionFor(i) ? sum + i :
    sum;
const solution = Array(1000)
    .fill()
    .reduce(getSumOf(selected(isDivisibleBy)(3, 5)), 0);

I have questions regarding efficiency and parametization:

1. Is there a more efficient way to write the function selected that is still functional? Because right now the filter functions runs through all elements of numbers - even if it finds an element that is not divisible for the given condition. Also .length > 0 makes it look like a hack. Is there a more declarative way?

2. I assume getSumOf can't be refactored any more?

Answer 1

This is fairly good for someone fairly new to FP. You seem to have quickly grasped the idea of function composition and lazy evaluation.

I would take a slightly different approach though. You're essentially baking a filter operation into your sum function.

const getSumOf = conditionFor => (sum, _, i) => conditionFor(i) ? sum + i : sum;

That ternary condition has no place in a function called getSumOf. I would try to keep those separate. You should be able to call sum on any array of numbers.

// define a nice alias for creating a range
// https://stackoverflow.com/a/29559308/3198973
const range = num => Array.from(new Array(num), (x,i) => i);

const sum = (acc,val) => acc + val;
const divisibleBy = (num, divisor) => num % divisor === 0;
const divisibleByThreeOrFive = i => divisibleBy(i, 3) || divisibleBy(i, 5);    

// let's solve
range(1000)
    .filter(divisibleByThreeOrFive))
    .reduce(sum);

This way reduces (no pun intended) each step of the problem into a simple function and applies each in turn. Get comfortable with the filter/map/reduce concept. It greatly simplifies your code.

---

If you'd like to stick with your curried version of divisibleBy, I'd recommend swapping the parameter order so you can do this, which reads pretty well without the intermediate function name.

// define a nice alias for creating a range
// https://stackoverflow.com/a/29559308/3198973
const range = num => Array.from(new Array(num), (x,i) => i);

const sum = (acc,val) => acc + val;
const divisibleBy = divisor => num => num % divisor === 0;

// let's solve
range(1000)
    .filter(i => divisibleBy(3)(i) || divisibleBy(5)(i))
    .reduce(sum);

---

Since you seem to be very interested in an API where you can specify a list of divisors to check, you might like this solution. I can't speak to it's efficiency though.

const range = num => Array.from(new Array(num), (x,i) => i);

const sum = (acc,val) => acc + val;
const divisibleBy = divisor => num => num % divisor === 0;

const divisibleByAny = (...divisors) => i => 
    divisors.map(divisibleBy) // list of functions (divisibleBy(3) etc.)
        .some(f => f(i));

// let's solve
range(1000)
    .filter(divisibleByAny(3,5))
    .reduce(sum);

Answer 2

This is one of those programming problems where there’s a special trick that can give you a better algorithm, in this case constant-time instead of linear.

If you add the multiples of 3 and the multiples of 5, you’ll count the multiples of 15 twice. So subtract those out. The answer becomes (3+6+9+...+999) + (5+10+15+...+995) - (15+30+45+...+990).

Then, to get all the multiples of m from 1 to N, factor the series m+2·m+... to m· (1 + 2 + ... + ⌊N/m⌋). There’s a simple formula for the series from 1 up to some number, called the Gaussian formula after its discoverer, Carl Friedrich Gauss. The story goes that he found it as a child, and when his math teacher ordered the whole class to add the numbers from 1 to 100, just to keep them busy so he could take a nap, young Carl shocked him by finding the answer in seconds. It works on computers, too! So, substitute this formula into the previous equation to get a constant-time formula for the sum of all multiples of m up to N. Then substitute that formula into the paragraph above this one, with m = 3, 5 and 15.

Maybe you know all that. The point of the exercise might have been to practice the specific idioms you used here, like list comprehension and reduction. Now that you have, you might want to compare an optimal algorithm in functional style. The last time I posted a better algorithm for a Project Euler problem, someone informed me that the point of Code Review is not to write a better answer myself, so I’ll leave that to you if you feel like it.

Answer 3

1. You can use Array#some instead of Array#filter to get the behavior you want. Per the documentation:

   some() executes the callback function once for each element present in the array until it finds one where callback returns a truthy value (a value that becomes true when converted to a Boolean). If such an element is found, some() immediately returns true.

   So Array#some will let you drop the length > 0 check and also returns after finding one truthy value, instead of having to iterate through the whole array.

2. I don't think you could do much other than shorten the ternary check, but even then it would make the code a bit less readable, so I'm not sure there's much merit in trying. You could shorten it to something like this:

   sum + (conditionFor(i) && i)
   

   Functional programming is great, but opting for brevity over readability is not a good thing to do. At this point, there's not a lot of refactoring I can think of without making it hard to read and process (or completely changing the approach) -- so I would say your assumption is correct.