How to define Fibonacci function from non-recursive version?

Question

I'm learning C++. As an exercise to myself, I'm trying to define the Fibonacci function from a non-recursive version using a Y combinator.

In F# (or C#) I'd do it like this:

let rec Y f n = f (Y f) n
let protoFib f x = if n > 1 then f(n-1) + f(n-2) else n
let fib = Y protoFib

In C++ I am stuck how to define Y

So that the following lines work

int protoFib(int f(int), int n) { 
    return (n > 1) ? f(n-1) + f(n-2) : n; 
}

int fib(int n) { return Y(protoFib, n); }

I tried the following function declaration (specific to int functions because I've not yet studied templates):

#include <functional>
int Y(std::function<int(std::function<int(int)>, int)>, int);

but I am stuck on writing the function definition.

Any suggestions?

Yakk - Adam Nevraumont · Answer 1 · 2019-04-09T19:35:00.300

First I'll write a bad, if functional, Y-combinator.

using fib_f = std::function<int(int)>;
using protofib_f = std::function< int( fib_f, int ) >;

int protofib( std::function<int(int)> f, int n) {
  if (n>1) return f(n-1)+f(n-1);
  return n;
}

auto Y( protofib_f f )->fib_f {
  return [=](int n) { return f( Y(f), n ); };
}

ugly, but it works.

We can write a better Y combinator.

template<class R>
auto Y = [&](auto&& f){
  return [=](auto&&...args)->R {
    return f( Y<R>(f), decltype(args)(args)... );
  };
};

which, to be simple, does need to have its return type specified.

auto fib = Y<int>(protofib);

it also defers type erasure, which gives performance.

We can strip type erasure form protofib:

auto protofib = [](auto&& f, int n)->int {
  if (n>1) return f(n-1)+f(n-1);
  return n;
};

by turning it into a lambda.

An improved Y combinator requires a bit more boilerplate, because lambdas cannot access this:

template<class F>
struct y_combinate_t {
  F f;
  template<class...Args>
  decltype(auto) operator()(Args&&...args)const {
    return f(*this, std::forward<Args>(args)...);
  }
};
template<class F>
y_combinate_t<std::decay_t<F>> y_combinate( F&& f ) {
  return {std::forward<F>(f)};
};

again, zero type erasure overhead, and this one doesn't require the return type being passed explicitly. (stolen from myself over here).

In c++17 the y_combinate helper can be eliminated:

template<class F>
struct y_combinate {
  F f;
  template<class...Args>
  decltype(auto) operator()(Args&&...args)const {
    return f(*this, std::forward<Args>(args)...);
  }
};
template<class F>
y_combinate(F&& f)->y_combinate<std::decay_t<F>>;

with a deduction guide.

y_combinate{ protofib }

is then a full fibbonacci function.

Live example.

Going a step further, you could add memoization to your y combinator.

Thanks for replying. In the ugly version, I don't understand all the syntax. Is `Y( protofib_f f )->fib_f` equivalent to `fib_f Y(protofib_f f)` ? What is `[=]` ? — Colonel Panic, Apr 09 '19 at 19:36
@ColonelPanic It is a lamba introducer. `[]` starts a lambda. `[=]` starts a lambda that implicitly copies from the local scope anything referenced in the lambda's body. To mimic F#'s implicit currying, my `Y` takes a function and returns a `std::function` that takes an `int`, instead of taking a function and an `int` and relying on the language curry it. — Yakk - Adam Nevraumont, Apr 09 '19 at 19:37

score 0 · Answer 2 · answered Apr 09 '19 at 19:27

from the rosseta stone https://rosettacode.org/wiki/Y_combinator#C.2B.2B for the Y combinator:

template <typename F>
struct RecursiveFunc {
    std::function<F(RecursiveFunc)> o;
};

template <typename A, typename B>
std::function<B(A)> Y (std::function<std::function<B(A)>(std::function<B(A)>)> f) {
    RecursiveFunc<std::function<B(A)>> r = {
        std::function<std::function<B(A)>(RecursiveFunc<std::function<B(A)>>)>([f](RecursiveFunc<std::function<B(A)>> w) {
            return f(std::function<B(A)>([w](A x) {
                return w.o(w)(x);
            }));
        })
    };
    return r.o(r);
}

I recommend you check the whole code for that example, as it contains other ways of implementing it (e.g. using lambdas)

How to define Fibonacci function from non-recursive version?

2 Answers2