8
\$\begingroup\$

I want to solve this problem in functional programming (fp) way only.

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Source: https://projecteuler.net/problem=2

This is my fp approach:

const range = num => Array.from(new Array(num), (_, i) => i);
const divisibleBy = divisor => num => num % divisor === 0;
const isEven = i => divisibleBy(2)(i);
const sum = (acc, val) => acc + val;
const fibonacciOf = n => {
    if (n === 0) {
        return 1;
    }
    if (n === 1) {
        return 2;
    }
    return fibonacciOf(n - 1) + fibonacciOf(n - 2);
};
const doUntil = maxVal => (fiboResult, i) => {
    const next = i + 1;
    return fiboResult >= maxVal ? i : doUntil(maxVal)(fibonacciOf(next), next);
};
const until4Mil = doUntil(4000000);
const maxRange = until4Mil(0, 0);

const solution = range(maxRange)
    .map(fibonacciOf)
    .filter(isEven)
    .reduce(sum);

console.log("solution ", solution);

1) I was struggling with the recursion, because that was the only way I could think of how to emulate the do...while loop. Do you know any alternative to the do...while loop (aka. a loop where you don't know when it ends) in fp?

2) Also, I'm not sure whether the part const maxRange = until4Mil(0, 0); is clean code or not.

Any other improvement suggestions are welcomed as well.

\$\endgroup\$
  • \$\begingroup\$ This is Project Euler isn't it \$\endgroup\$ – 13ros27 Dec 23 '17 at 12:25
  • \$\begingroup\$ @13ros27 yes, it is \$\endgroup\$ – thadeuszlay Dec 23 '17 at 12:26
  • \$\begingroup\$ I recognised it because we had to do this exact question in Python. One of my friends got it down to 4 lines. \$\endgroup\$ – 13ros27 Dec 23 '17 at 12:26
  • \$\begingroup\$ @13ros27 For me it's not about the amount of lines, but I want to practice fp first and foremost. \$\endgroup\$ – thadeuszlay Dec 23 '17 at 12:27
  • 1
    \$\begingroup\$ Every 3rd Fibonacci Number is even and no others which may help \$\endgroup\$ – 13ros27 Dec 23 '17 at 16:30
4
\$\begingroup\$

General Notes

  1. The use of map(f1).filter(f2).reduce(f3) is a solid approach to functional programming.
  2. The names of the functions and variables are reasonable.

Things to consider

  • Scope: The lexical scope of the the const = x => ...; is the global namespace. The values are only used locally. In Javascript this is suboptimal practice.
  • Lambdas: Javascript lambda notation facilitates passing anonymous functions. One advantage of passing anonymous functions is that it is done locally. const sum... is four lines from the top of the file. .reduce(sum) is only two lines from the bottom.

    .reduce((x,y) => x + y)

    is almost certainly easier to understand...though it may be harder to write without refactoring.

  • Intent: The use of const is good to express your intent to program in a functional manner, but it does not really make the code easier to read. One of the 'supposed' rationales for using functional programming is that it is easier to reason about. This is a case where: /* This code is written in a functional style. It does not use mutuation */ at the top of the file might be another way to state the your intent while letting the Javascript look more familiar.

Computer Science

In terms of functional programming, the use of recursion is a step in the right direction. However the recursive code calculating the Fibonacci values:

const fibonacciOf = n => {
    if (n === 0) {
        return 1;
    }
    if (n === 1) {
        return 2;
    }
    return fibonacciOf(n - 1) + fibonacciOf(n - 2);
};

Is "tree recursive" and therefore does a lot of extra work. Tree Recursion is described in The Structure and Interpretation of Computer Programs. Section 1.2.2 has a very helpful illustration that shows how tree recursive algorithms wind up performing substantially more work than is necessary.

Alternative Functional Approach

Recursive Design: Structurally recursive algorithms have two part: a base case and an inductive step. The naive approach to Fibonacci treats n == 0 as the base case and n-1 as the induction. The alternative code treats n as the base case and n + 1 as the induction. This means n - 1 has always been computed previously.

function sumOfEvenFibsLessThan (n) {

    /* Returns the array of Fibonacci numbers less than n */
    var fibsLessThan = function (n) {

        /* Takes an Array, returns an Array */
        var generateFibs = function(fibs) {
            var nextFib = fibs[fibs.length - 1] + fibs[fibs.length - 2];
            // test against max
            if (nextFib >= n) {
                return fibs;
            }
            else {
                // concatinate next number to array
                return generateFibs(fibs.concat([nextFib]));
            }
        };
        // check input validity
        if (n <= 1) {
            return [];
        };
        // check base case
        if (n <= 2) {
            return [1,1];
        };
        // otherwise generate array recursively
        return generateFibs([1,1]);
    };

    return fibsLessThan(n).filter(x => x % 2 === 0).reduce((x,y) => x + y);
}
  • Lexical Scope: Only sumOfEvenFibsLessThan is in the global namespace.

  • The map in the map(f1).filter(f2).reduce(f3) pattern can be considered as f1 = x => x (aka "An identity function").

  • A trampoline is used to start generateFibs. Trampolines are a common functional programming technique to invoke a recursive function with a local lexical scope.

\$\endgroup\$
  • \$\begingroup\$ I really like this approach of how to calculate the fibonacci numbers by caching it's results!!!! \$\endgroup\$ – thadeuszlay Dec 24 '17 at 13:20
3
\$\begingroup\$

Some notes about your code:

  • Since you want to solve ProjectEuler problems while learning FP (cool!), look for a module that already implements the typical abstractions using lazy generators, not arrays.
  • const divisibleBy = divisor => num => num % divisor === 0;: Not that using curried functions is bad, but it doesn't look too idiomatic in JS.
  • Use partial application with curried functions: const isEven = divisibleBy(2);
  • fibonacciOf: This naive implementation of the algorithm is extremely inefficient without memoization, there are more efficient alternatives. I'd use the iterate implementation.
  • doUntil: In FP style, you'd use takeWhile.

Using lazit:

const {map, filter, head, takeWhile, foldl, iterate} = require('lazit');

const isEven = x => x % 2 === 0;
const sum = xs => foldl((acc, x) => acc + x, 0, xs);
const fibs = map(head, iterate(([x, y]) => [y, x + y], [0, 1]));
const solution = sum(filter(isEven, takeWhile(x => x < 4e6, fibs)));

Or with lazy.js, which uses a more OOP-like chaining style:

const Lazy = require('lazy.js');

const iterate = (state, fn) => Lazy.generate(() => { return (state = fn(state)); });
const isEven = x => x % 2 === 0;
const fibs = iterate([0, 1], ([x, y]) => [y, x + y]).map(([x, y]) => x);
const solution = fibs.takeWhile(x => x < 4e6).filter(isEven).sum();
\$\endgroup\$
  • \$\begingroup\$ Thanks. But I don't want to use any external library but want to use pure JS. \$\endgroup\$ – thadeuszlay Dec 23 '17 at 14:59
  • 1
    \$\begingroup\$ @thadeuszlay Then just implement those abstractions yourself, it makes no difference about how the final code should look, other than the style, you might decide you prefer to chain calls: _(fibs).takeWhile(...).filter(isEven).sum().value() like lodash does, for example. The important thing is how you identify the abstractions you need and how you build on them, not how you implement them. \$\endgroup\$ – tokland Dec 23 '17 at 15:03
  • \$\begingroup\$ Thanks for the suggestion with the isEven/ partial application. Totally missed that. :D \$\endgroup\$ – thadeuszlay Dec 23 '17 at 15:04

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.