Fibonacci sequence

[andreavaccari]

I'm learning fp-ts by solving Project Euler. Could someone show some ways to solve Problem 2?

Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million.

The Haskell wiki has various solutions, but I can't reimplement them with fp-ts.

Thank you!

[imcotton]

In strict language, manually tail recursion would do the trick:

import { left, right } from 'fp-ts/Either';
import { tailRec } from 'fp-ts/ChainRec';

function fibEvenSum (n: number) {

    const isEven = (num: bigint) => num % 2n === 0n;

    const init = { a: 1n, b: 2n, i: 2, acc: 2n };

    return tailRec(init, ({ a, b, i, acc }) => {

        if (i >= n) {
            return right(acc);
        }

        const c = a + b;

        return left({
            a: b,
            b: c,
            i: i + 1,
            acc: isEven(c) ? acc + c : acc,
        });

    });

}

note: although it's stack safe, do expect reasonable amount of CPU time against four million cycles.

[andreavaccari]

Thank you so much. Your solution calculated the even sum of the first 4 million fibonacci numbers, while the problem asked for the even sum of the fibonacci numbers below 4 million. Please let me know if you think the new solution could be improved further.

import { pipe } from "fp-ts/function"
import { left, right } from "fp-ts/Either"
import { tailRec } from "fp-ts/ChainRec"

const fibEvenSum = (n: number) =>
  pipe(
    { a: 1n, b: 2n, evenSum: 2n },
    tailRec(({ a, b, evenSum }) => {
      if (b >= n) return right(evenSum)

      const c = a + b

      return left({
        a: b,
        b: c,
        evenSum: c % 2n === 0n ? evenSum + c : evenSum,
      })
    }),
  )

pipe(4e6, fibEvenSum, console.log)

[imcotton]

Oops, you are right, then it's much simpler and without involve of bigint.

Your are taking tailRec as pipeable which does not the case in fp-ts right now tho.

[andreavaccari]

I removed the unnecessary use of bigint. Otherwise the solution I posted works correctly.

I should mention I have been using fp-ts version ^3.0.0-alpha.16 which has a newer API.

[imcotton]

I should mention I have been using fp-ts version ^3.0.0-alpha.16 which has a newer API.

That's great, haven't realized yet.

[imcotton]

Since problem space is much smaller, another approach with unfold:

import {
    option as O,
    function as F,
    readonlyArray as A,
} from 'fp-ts';



const fibEvenSum2 = (n: number) => F.pipe(

    A.unfold({ a: 1, b: 1 }, F.flow(

        O.fromPredicate(({ b }) => b < n),

        O.map(({ a, b }) => {
            const c = a + b;
            return [ c, { a: b, b: c } ];
        }),

    )),

    A.filter(m => m % 2 === 0),

    A.reduce(0, (a, b) => a + b),

);

[andreavaccari]

Thank you for showing me the use of both ChainRec.tailRec and ReadonlyArray.unfold. They feel similar after learning how to pass values around. Would there be reasons to favor one over the other? Are there other approaches I should consider, with the purpose of learning FP?

Separately, I tweaked the predicate in your second solution from to O.fromPredicate(({ a, b }) => a + b < n) to avoid producing one last value which is over the threshold. I also replaced A.reduce with M.concatAll which seems more idiomatic. How does this look?

const fibEvenSum2 = (n: number) =>
  pipe(
    A.unfold(
      { a: 1, b: 1 },
      flow(
        O.fromPredicate(({ a, b }) => a + b < n),
        O.map(({ a, b }) => {
          const c = a + b
          return [c, { a: b, b: c }]
        }),
      ),
    ),
    A.filter(n => n % 2 === 0),
    M.concatAll(N.MonoidSum),
  )

[imcotton]

unfold keeps accumulator internally v.s. in tailRec would be manually managed, which gains ability to shrink memory allocation within each round. Given that, tailRec is more flexible in general speaking.

IMO, O(n) and O(n+1) makes no difference, however put a + b in two places would introducing duplication and increase footprint of maintains, one would make educated tread-off in between.

MonoidSum is a good addition there 👍