Sum of Even Fibonacci numbers in functional programming

Question

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.

Answer 1

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.

Answer 2

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