I am attempting to build a clean and neat implementation of recursive-capable lambda self-scoping (which is basically a Y-combinator although I think technically not quite). It's a journey that's taken me to, among many others, this thread and this thread and this thread.

I've boiled down one of my issues as cleanly as I can: how do I pass around templated functors which take lambdas as their template parameters?

#include <string>
#include <iostream>
#define uint unsigned int

template <class F>
class Functor {
public:
    F m_f;

    template <class... Args>
    decltype(auto) operator()(Args&&... args) {
        return m_f(*this, std::forward<Args>(args)...);
    }
};
template <class F> Functor(F)->Functor<F>;

class B {
private:
    uint m_val;
public:
    B(uint val) : m_val(val) {}
    uint evaluate(Functor<decltype([](auto & self, uint val)->uint {})> func) const {
        return func(m_val);
    }
};

int main() {
    B b = B(5u);
    Functor f = Functor{[](auto& self, uint val) -> uint {
        return ((2u * val) + 1u);
    }};

    std::cout << "f applied to b is " << b.evaluate(f) << "." << std::endl;
}

The code above does not work, with Visual Studio claiming that f (in the b.evaluate(f) call) does not match the parameter type.

My assumption is that auto & self is not clever enough to make this work. How do I get around this? How do I store and pass these things around when they are essentially undefinable? Is this why many of the Y-combinator implementations I've seen have the strange double-wrapped thing?

Any help or explanation would be enormously appreciated.

The easiest solution is:

uint evaluate(std::function<uint(uint)> func) const {
    return func(m_val);
}

a step up would be to write a function_view.

uint evaluate(function_view<uint(uint)> func) const {
    return func(m_val);
}

(there are dozens of implementations on the net, should be easy to find).

The easiest and most runtime efficient is:

template<class F>
uint evaluate(F&& func) const {
    return func(m_val);
}

because we don't care what func is, we just want it to quack like a duck. If you want to check it early...

template<class F> requires (std::is_convertible_v< std::invoke_result_t< F&, uint >, uint >)
uint evaluate(F&& func) const {
    return func(m_val);
}

using c++20, or using c++14

template<class F,
  std::enable_if_t<(std::is_convertible_v< std::invoke_result_t< F&, uint >, uint >), bool> = true
>
uint evaluate(F&& func) const {
    return func(m_val);
}

which is similar just more obscure.

You can write a fixes-signature type-erased Functor, but I think it is a bad idea. It looks like:

template<class R, class...Args>
using FixedSignatureFunctor = Functor< std::function<R( std::function<R(Args...)>, Args...) > >;

or slightly more efficient

template<class R, class...Args>
using FixedSignatureFunctor = Functor< function_view<R( std::function<R(Args...)>, Args...) > >;

but this is pretty insane; you'd want to forget what the F is, but not that you can replace the F!

To make this fully "useful", you'd have to add smart copy/move/assign operations to Functor, where it can be copied if the Fs inside each of them can be copied.

template <class F>
class Functor {
public:
  // ...
  Functor(Functor&&)=default;
  Functor& operator=(Functor&&)=default;
  Functor(Functor const&)=default;
  Functor& operator=(Functor const&)=default;

  template<class O> requires (std::is_constructible_v<F, O&&>)
  Functor(Functor<O>&& o):m_f(std::move(o.m_f)){}
  template<class O> requires (std::is_constructible_v<F, O const&>)
  Functor(Functor<O> const& o):m_f(o.m_f){}
  template<class O> requires (std::is_assignable_v<F, O&&>)
  Functor& operator=(Functor<O>&& o){
    m_f = std::move(o.mf);
    return *this;
  }
  template<class O> requires (std::is_assignable_v<F, O const&>)
  Functor& operator=(Functor<O> const& o){
    m_f = o.mf;
    return *this;
  }
  // ...
};

(c++20 version, replace requires clauses with std::enable_if_t SFINAE hack in c++17 and before).

How to decide

The core thing to remember here is that C++ has more than one kind of polymorphism, and using the wrong kind will make you waste a lot of time.

There is both compile time polymorphism and runtime polymorphism. Using runtime polymorphism when you only need compile time polymorphism is a waste.

Then in each category, there are even more subtypes.

std::function is a runtime polymorphic type erasure regular object. Inheritance based virtual functions is another runtime polymorphic technique.

Your Y-combinator is doing compile time polymorphism. It changes what it stores and exposed a more uniform interface.

Things talking to that interface don't care about the internal implementation details of your Y-combinator, and including them in their implementation is an abstraction failure.

evaluate takes a callable thing and pass it in uint and expects a uint in return. That is what it care about. It doesn't care if it is passed a Functor<Chicken> or a function pointer.

Making it care about it is a mistake.

If it takes a std::function, it does runtime polymorphism; if it takes a template<class F> with an argument of type F&&, it is compile time polymorphic. This is a choice, and they are different.

Taking a Functor<F> of any kind is putting contract requirements in its API it fundamentally shouldn't care about.