y_combinator.cpp

#include <utility>

// left fold by hand
template <typename F,typename Acc, typename... T>
  constexpr auto foldLeft_initial(F func, Acc acc, T... xs)
{
    auto step = [=](auto self, auto acc_, auto x_, auto... xs_) 
    {        
            auto sum = func(acc_, x_);

            if constexpr(sizeof...(xs_) != 0)
                return self(self, sum, xs_...);
            else
                return sum;        
    };

    return step(step, acc, xs...);
}

// left fold in a more functional style
template <typename Acc, typename F, typename... T>
 constexpr auto foldLeft_verbose(F func, Acc acc, T... xs)
{
    auto step = [=](auto self)
    {
        return [=](auto acc_, auto x_, auto... xs_)
        {
            auto sum = func(acc_, x_);

            if constexpr(sizeof...(xs_) != 0)
                return self(self)(sum, xs_...);
            else
                return sum;
        };
    };

    return step(step)(acc, xs...);
}


// home-made Y combinator
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)};
};


// left fold with Y combinator
template <typename F,typename Acc, typename... T>
constexpr auto foldLeft(F func, Acc acc, T... xs)
{
    auto step = [=](auto self, auto acc_, auto x_, auto... xs_) 
    {        
            auto sum = func(acc_, x_);

            if constexpr(sizeof...(xs_) != 0)
                return self(sum, xs_...);
            else
                return sum;        
    };

    return y_combinate(step)(acc, xs...);
}


// TEST:
#include <iostream>

int main()
{  
    std::cout << "sum_i 1,2,3,4,5,6,7 = " 
              << foldLeft_initial([](int a, int b) { return a + b; }, 
                          0,
                          1,2,3,4,5,6,7);

    std::cout << "\nsum_v 1,2,3,4,5,6 = " 
              << foldLeft_verbose([](int a, int b) { return a + b; }, 
                          0,
                          1,2,3,4,5,6);

    std::cout << "\nsum 1,2,3,4,5 = " 
              << foldLeft([](int a, int b) { return a + b; }, 
                          0,
                          1,2,3,4,5);

    std::cout << "\nfact 1,2,3,4,5 = " 
              << foldLeft([] (int a, int b) { return a * b; }, 
                          1,
                          1,2,3,4,5);                 
  
    // test GCD example
    auto almost_gcd = [](auto gcd, int a, int b) -> int 
    {
        return b == 0 ? a : gcd(b, a % b);
    };
  
    auto gcd = y_combinate(std::ref(almost_gcd));
  
    std::cout << "\ngcd 20,30 = " << gcd(20, 30);
    std::cout << "\ngcd 77,122 = " << gcd(77, 122);


    // test left fold again
    auto lfold_step = [=](auto self, auto func, auto acc_, auto x_, auto... xs_) 
    {        
            auto sum = func(acc_, x_);

            if constexpr(sizeof...(xs_) != 0)
                return self(func, sum, xs_...);
            else
                return sum;        
    };

    auto fold_left = y_combinate(lfold_step); // curried with "lfold_step"!

    std::cout << "\nsum 1,2,3,4,5 = " 
              << fold_left([](int a, int b) { return a + b; }, 
                          0,
                          1,2,3,4,5);

}