Esiste un tipo di funzione std :: o simile per lambda con parametro auto?

Question

Quando assegno un lambda a una variabile tipizzata in modo esplicito (ad esempio quando è ricorsiva, per acquisire la funzione in se stessa), utilizzo std::function.

considerare questo "bit contare" sciocco funzione come esempio:

std::function<int(int)> f; 
f = [&f](int x){ return x ? f(x/2)+1 : 0; }; 

Che dire del caso in cui usiamo un parametro auto per generalizzare x, introdotto in C++ 14 lambda generica?

std::function<int(???)> f; 
f = [&f](auto x){ return x ? f(x/2)+1 : 0; }; 

Ovviamente, non posso mettere auto nei parametri di tipo function.

Esiste la possibilità di definire una classe di functor genericamente sufficiente a coprire il caso esatto sopra, ma utilizzando ancora lambda per la definizione della funzione?

(Non generalizzare troppo, accetta solo un singolo parametro auto e codifica il valore restituito.) Il caso d'uso sarebbe per lo scenario come sopra: acquisizione della funzione in sé per riferimento per le chiamate ricorsive.

Answer 1

È possibile creare una lambda che si definisce passandolo a se stesso come parametro:

auto f = [](auto self, auto x) -> int { 
    return x ? self(self, x/2) + 1 : 0; 
}; 

std::cout << f(f, 10); 

È quindi possibile catturare quel lambda in un altro lambda, in modo da non dovete preoccuparvi di passarlo a stessa:

auto f2 = [&f](auto x) { 
    return f(f, x); 
}; 

std::cout << f2(10); 

Answer 2

Ecco un breve y-combinatore motore basato ricorsivo:

template<class F> 
struct recursive_t { 
    F f; 

    // note Self must be an lvalue reference. Things get 
    // strange if it is an rvalue: 
    // invoke makes recursive ADL work a touch better. 
    template<class Self, class...Args> 
    friend auto invoke(Self& self, Args&&...args) 
    -> decltype(self.f(self, std::declval<Args>()...)) 
    { 
    return self.f(self, std::forward<Args>(args)...); 
    } 
    // calculate return type using `invoke` above: 
    template<class Self, class...Args> 
    using R = decltype(invoke(std::declval<Self>(), std::declval<Args>()...)); 

    template<class...Args> 
    R<recursive_t&, Args...> operator()(Args&&...args) 
    { 
    return invoke(*this, std::forward<Args>(args)...); 
    } 
    template<class...Args> 
    R<recursive_t const&, Args...> operator()(Args&&...args)const 
    { 
    return invoke(*this, std::forward<Args>(args)...); 
    } 
}; 

template<class F> 
recursive_t< std::decay_t<F> > recurse(F&& f) 
{ 
    return {std::forward<F>(f)}; 
} 

Ora si può fare:

auto f = recurse([](auto&& f, auto x){ return x ? f(x/2)+1 : 0; }); 

e si ottiene un lambda ricorsiva che non dispone di una cattura & (che limita il suo utilizzo per l'ambito corrente).

Catturare un std::function in base al riferimento significa che il tempo di vita del vostro lambda è l'ambito corrente e che ogni chiamata ricorsiva richiede la cancellazione del tipo (bloccando qualsiasi ottimizzazione possibile, come la ricorsione in coda, sulla chiamata ricorsiva). Lo stesso vale per altre soluzioni simili.

L'uso di recursive_t è necessario anziché utilizzare una lambda, perché un lambda non può nominarsi al suo interno.

Live example.

Una versione basata su lambda è in qualche modo più semplice nell'implementazione. Si noti che avresti bisogno di una funzione di tipo diverso per lambda mutabili e immutabili:

template<class F> 
auto recurse(F&& f) { 
    return [f=std::forward<F>(f)](auto&&...args){ 
    return f(f, decltype(args)(args)...); 
    }; 
}; 

I recursive_t opere come:

auto fib = recurse([](auto&& fib, int x){ if (x<2) return 1; return fib(x-1)+fib(x-2); }); 

la versione lambda funziona come:

auto fib = recurse([](auto&& self, int x){ if (x<2) return 1; return self(self, x-1)+self(self,x-2); }); 

che ho , personalmente, trovare più imbarazzante.

È anche più difficile descrivere il tipo di recurse. Per la versione recursive_t, recurse è di tipo:

((A->B)->A->B)->(A->B) 

che è scomodo, ma un tipo finito.

La versione lambda è più complicata. Il tipo dell'argomento funzione recursive è di tipo:

F:= F->A->B 

quali è fastidiosamente infinita, e quindi recurse è di tipo

F->A->(A->B) 

che eredita l'infinito.

In ogni caso, il valore di ritorno recurse può quindi essere memorizzato in un banale std::function o non memorizzato in alcun contenitore cancellato dal tipo.