4
\$\begingroup\$

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?

\$\endgroup\$
6
\$\begingroup\$

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);
\$\endgroup\$
  • \$\begingroup\$ do you think it makes sense to write divisibleByThreeOrFive in a more parametized way, so it looks like isDivisbleBy(3,5), isDivisibleBy(1,2,3), or isDivisibleBy(1,2,3,4)? \$\endgroup\$ – thadeuszlay Dec 22 '17 at 16:18
  • \$\begingroup\$ Maybe @thadeuszlay. I'm actually still playing with a way to salvage the currying in a nice way. \$\endgroup\$ – RubberDuck Dec 22 '17 at 16:19
  • \$\begingroup\$ @thadeuszlay I updated my answer a bit. I think you might be able to use the new bit to create the interface you're shooting for. \$\endgroup\$ – RubberDuck Dec 22 '17 at 16:38
  • \$\begingroup\$ I see. I also just updated my version in my OP. What do you think about the is helper function? Too generic? \$\endgroup\$ – thadeuszlay Dec 22 '17 at 16:40
  • \$\begingroup\$ Ahh. I like that very much. I was just thinking of using a map to create a list of filter expressions. Well done. \$\endgroup\$ – RubberDuck Dec 22 '17 at 16:42
11
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Your "constant time trick" is called the inclusion exclusion principle. I'd remove the Gauss anecdote, to be honest, you're getting off track at that point. Also, you can use LaTeX to format your answer: \$\sum_{s \in \{1,2,\ldots,999\}, (s \equiv 0\mod 3) \lor (s\equiv 0\mod 5 )} s = \ldots\$. \$\endgroup\$ – Zeta Dec 31 '17 at 12:55
  • \$\begingroup\$ @Zeta Great points, thanks. I didn’t give the name for the technique, but the reason I gave the anecdote about Gauss was that I wanted to give enough information to look up the Gaussian formula without just giving out the answer. And I thought a little humor couldn’t hurt. \$\endgroup\$ – Davislor Dec 31 '17 at 20:16
  • \$\begingroup\$ @Zeta For whatever reason, the LaTeX subsystem here is set up to use the default font for LaTeX, rather than a math font that matches the text, although it does at least support Unicode. I don’t think that looks attractive in the middle of a paragraph of the sans-serif font SX uses, at all. That’s a good example of an expression I couldn’t write properly without TeX, though. \$\endgroup\$ – Davislor Dec 31 '17 at 20:23
5
\$\begingroup\$
  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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Totally agree with your last paragraph. Sometimes the priority is maintainability, sometimes portability, sometimes performance, sometimes getting style points. But real-world programming is never a Code Golf puzzle. \$\endgroup\$ – Davislor Dec 23 '17 at 6:44

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.