Soy nuevo en C ++ 11. Estoy escribiendo la siguiente función recursiva lambda, pero no se compila.

sum.cpp

#include <iostream>
#include <functional>

auto term = [](int a)->int {
  return a*a;
};

auto next = [](int a)->int {
  return ++a;
};

auto sum = [term,next,&sum](int a, int b)mutable ->int {
  if(a>b)
    return 0;
  else
    return term(a) + sum(next(a),b);
};

int main(){
  std::cout<<sum(1,10)<<std::endl;
  return 0;
}

error de compilación:

vimal @ linux-718q: ~ / Study / 09C ++ / c ++ 0x / lambda> g ++ -std = c ++ 0x sum.cpp

sum.cpp: en la función lambda: sum.cpp: 18: 36: error: ' ((<lambda(int, int)>*)this)-><lambda(int, int)>::sum' no se puede usar como una función

versión gcc

gcc versión 4.5.0 20091231 (experimental) (GCC)

Pero si cambio la declaración de la sum()siguiente manera, funciona:

std::function<int(int,int)> sum = [term,next,&sum](int a, int b)->int {
   if(a>b)
     return 0;
   else
     return term(a) + sum(next(a),b);
};

¿Podría alguien arrojar luz sobre esto?

Piense en la diferencia entre la versión automática y la versión de tipo completamente especificada. La palabra clave automática infiere su tipo de lo que sea que se haya inicializado, pero lo que está inicializando necesita saber cuál es su tipo (en este caso, el cierre lambda necesita saber los tipos que está capturando). Algo de un problema de huevo y gallina.

Por otro lado, el tipo de un objeto de función completamente especificado no necesita "saber" nada sobre lo que se le está asignando, por lo que el cierre de la lambda también puede estar completamente informado sobre los tipos que captura.

Considere esta ligera modificación de su código y puede tener más sentido:

std::function<int(int,int)> sum;
sum = [term,next,&sum](int a, int b)->int {
if(a>b)
    return 0;
else
    return term(a) + sum(next(a),b);
};

Obviamente, esto no funcionaría con auto . Las funciones lambda recursivas funcionan perfectamente bien (al menos lo hacen en MSVC, donde tengo experiencia con ellas), es solo que no son realmente compatibles con la inferencia de tipos.

El truco consiste en introducir la implementación lambda en sí misma como parámetro , no mediante captura.

const auto sum = [term,next](int a, int b) {
  auto sum_impl=[term,next](int a,int b,auto& sum_ref) mutable {
    if(a>b){
      return 0;
    }
    return term(a) + sum_ref(next(a),b,sum_ref);
  };
  return sum_impl(a,b,sum_impl);
};

Todos los problemas en informática pueden resolverse mediante otro nivel de indirección . Primero encontré este truco fácil en http://pedromelendez.com/blog/2015/07/16/recursive-lambdas-in-c14/

Que no requiere C ++ 14, mientras que la cuestión está en C ++ 11, pero tal vez más interesante.

Ir a través de std::functiontambién es posible pero puede resultar en un código más lento. Pero no siempre. Eche un vistazo a las respuestas a std :: function vs template

Esto no es solo una peculiaridad sobre C ++, sino que se asigna directamente a las matemáticas del cálculo lambda. De Wikipedia :

Lambda calculus cannot express this as directly as some other notations:
all functions are anonymous in lambda calculus, so we can't refer to a
value which is yet to be defined, inside the lambda term defining that
same value. However, recursion can still be achieved by arranging for a
lambda expression to receive itself as its argument value

Con C ++ 14, ahora es bastante fácil hacer un lambda recursivo eficiente sin tener que incurrir en la sobrecarga adicional de std::function, en solo unas pocas líneas de código (con una pequeña edición del original para evitar que el usuario tome una copia accidental ):

template <class F>
struct y_combinator {
    F f; // the lambda will be stored here

    // a forwarding operator():
    template <class... Args>
    decltype(auto) operator()(Args&&... args) const {
        // we pass ourselves to f, then the arguments.
        // [edit: Barry] pass in std::ref(*this) instead of *this
        return f(std::ref(*this), std::forward<Args>(args)...);
    }
};

// helper function that deduces the type of the lambda:
template <class F>
y_combinator<std::decay_t<F>> make_y_combinator(F&& f) {
    return {std::forward<F>(f)};
}

con lo que tu sumintento original se convierte en:

auto sum = make_y_combinator([term,next](auto sum, int a, int b) {
  if (a>b) {
    return 0;
  }
  else {
    return term(a) + sum(next(a),b);
  }
});

En C ++ 17, con CTAD, podemos agregar una guía de deducción:

template <class F> y_combinator(F) -> y_combinator<F>;

Lo que evita la necesidad de la función auxiliar. Solo podemos escribir y_combinator{[](auto self, ...){...}}directamente.

En C ++ 20, con CTAD para agregados, la guía de deducción no será necesaria.

Tengo otra solución, pero solo trabajo con lambdas sin estado:

void f()
{
    static int (*self)(int) = [](int i)->int { return i>0 ? self(i-1)*i : 1; };
    std::cout<<self(10);
}

El truco aquí es que lambdas puede acceder a variables estáticas y puede convertir las sin estado en puntero de función.

Puedes usarlo con lambdas estándar:

void g()
{
    int sum;
    auto rec = [&sum](int i) -> int
    {
        static int (*inner)(int&, int) = [](int& _sum, int i)->int 
        {
            _sum += i;
            return i>0 ? inner(_sum, i-1)*i : 1; 
        };
        return inner(sum, i);
    };
}

Su trabajo en GCC 4.7

Usted puede hacer una función lambda llama a sí mismo de forma recursiva. Lo único que debe hacer es hacer referencia a él a través de un contenedor de funciones para que el compilador sepa su tipo de retorno y argumento (no puede capturar una variable, la lambda misma, que aún no se ha definido) .

  function<int (int)> f;

  f = [&f](int x) {
    if (x == 0) return 0;
    return x + f(x-1);
  };

  printf("%d\n", f(10));

Tenga mucho cuidado de no salirse del alcance del envoltorio f.

Para hacer que lambda sea recursiva sin usar clases y funciones externas (como std::functionun combinador de punto fijo), se puede usar la siguiente construcción en C ++ 14 ( ejemplo en vivo ):

#include <utility>
#include <list>
#include <memory>
#include <iostream>

int main()
{
    struct tree
    {
        int payload;
        std::list< tree > children = {}; // std::list of incomplete type is allowed
    };
    std::size_t indent = 0;
    // indication of result type here is essential
    const auto print = [&] (const auto & self, const tree & node) -> void
    {
        std::cout << std::string(indent, ' ') << node.payload << '\n';
        ++indent;
        for (const tree & t : node.children) {
            self(self, t);
        }
        --indent;
    };
    print(print, {1, {{2, {{8}}}, {3, {{5, {{7}}}, {6}}}, {4}}});
}

huellas dactilares:

1
 2
  8
 3
  5
   7
  6
 4

Tenga en cuenta que el tipo de resultado de lambda debe especificarse explícitamente.

Ejecuté un punto de referencia comparando una función recursiva frente a una función lambda recursiva utilizando el std::function<>método de captura. Con las optimizaciones completas habilitadas en la versión 4.1 de clang, la versión lambda se ejecutó significativamente más lenta.

#include <iostream>
#include <functional>
#include <chrono>

uint64_t sum1(int n) {
  return (n <= 1) ? 1 : n + sum1(n - 1);
}

std::function<uint64_t(int)> sum2 = [&] (int n) {
  return (n <= 1) ? 1 : n + sum2(n - 1);
};

auto const ITERATIONS = 10000;
auto const DEPTH = 100000;

template <class Func, class Input>
void benchmark(Func&& func, Input&& input) {
  auto t1 = std::chrono::high_resolution_clock::now();
  for (auto i = 0; i != ITERATIONS; ++i) {
    func(input);
  }
  auto t2 = std::chrono::high_resolution_clock::now();
  auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(t2-t1).count();
  std::cout << "Duration: " << duration << std::endl;
}

int main() {
  benchmark(sum1, DEPTH);
  benchmark(sum2, DEPTH);
}

Produce resultados:

Duration: 0 // regular function
Duration: 4027 // lambda function

(Nota: también confirmó con una versión que tomó las entradas de cin, para eliminar la evaluación del tiempo de compilación)

Clang también produce una advertencia de compilación:

main.cc:10:29: warning: variable 'sum2' is uninitialized when used within its own initialization [-Wuninitialized]

Lo cual es esperado y seguro, pero debe tenerse en cuenta.

Es genial tener una solución en nuestros cinturones de herramientas, pero creo que el lenguaje necesitará una mejor manera de manejar este caso si el rendimiento es comparable a los métodos actuales.

Nota:

Como señaló un comentarista, parece que la última versión de VC ++ ha encontrado una manera de optimizar esto hasta el punto de un rendimiento igual. Tal vez no necesitemos una mejor manera de manejar esto, después de todo (excepto el azúcar sintáctico).

Además, como algunas otras publicaciones de SO han descrito en las últimas semanas, el rendimiento en std::function<>sí mismo puede ser la causa de la desaceleración frente a la función de llamada directamente, al menos cuando la captura lambda es demasiado grande para caber en algunos std::functionusos de espacio optimizados para bibliotecas para pequeños functores (¿Supongo que te gustan las diversas optimizaciones de cadenas cortas?).

Esta es una implementación un poco más simple del operador de punto fijo que lo hace un poco más obvio exactamente lo que está sucediendo.

#include <iostream>
#include <functional>

using namespace std;

template<typename T, typename... Args>
struct fixpoint
{
    typedef function<T(Args...)> effective_type;
    typedef function<T(const effective_type&, Args...)> function_type;

    function_type f_nonr;

    T operator()(Args... args) const
    {
        return f_nonr(*this, args...);
    }

    fixpoint(const function_type& p_f)
        : f_nonr(p_f)
    {
    }
};


int main()
{
    auto fib_nonr = [](const function<int(int)>& f, int n) -> int
    {
        return n < 2 ? n : f(n-1) + f(n-2);
    };

    auto fib = fixpoint<int,int>(fib_nonr);

    for (int i = 0; i < 6; ++i)
    {
        cout << fib(i) << '\n';
    }
}

Aquí hay una versión refinada de la solución Y-combinator basada en una propuesta por @Barry.

template <class F>
struct recursive {
  F f;
  template <class... Ts>
  decltype(auto) operator()(Ts&&... ts)  const { return f(std::ref(*this), std::forward<Ts>(ts)...); }

  template <class... Ts>
  decltype(auto) operator()(Ts&&... ts)  { return f(std::ref(*this), std::forward<Ts>(ts)...); }
};

template <class F> recursive(F) -> recursive<F>;
auto const rec = [](auto f){ return recursive{std::move(f)}; };

Para usar esto, uno podría hacer lo siguiente

auto fib = rec([&](auto&& fib, int i) {
// implementation detail omitted.
});

Es similar a la let recpalabra clave en OCaml, aunque no es lo mismo.

C ++ 14: Aquí hay un conjunto genérico de lambdas anónimo recursivo sin estado / sin captura que genera todos los números del 1, 20

([](auto f, auto n, auto m) {
    f(f, n, m);
})(
    [](auto f, auto n, auto m) -> void
{
    cout << typeid(n).name() << el;
    cout << n << el;
    if (n<m)
        f(f, ++n, m);
},
    1, 20);

Si entiendo correctamente, esto está usando la solución del combinador Y

Y aquí está la versión suma (n, m)

auto sum = [](auto n, auto m) {
    return ([](auto f, auto n, auto m) {
        int res = f(f, n, m);
        return res;
    })(
        [](auto f, auto n, auto m) -> int
        {
            if (n > m)
                return 0;
            else {
                int sum = n + f(f, n + 1, m);
                return sum;
            }
        },
        n, m); };

auto result = sum(1, 10); //result == 55

Aquí está la respuesta final para el OP. De todos modos, Visual Studio 2010 no admite la captura de variables globales. Y no es necesario capturarlos porque la variable global es accesible globalmente mediante define. La siguiente respuesta utiliza la variable local en su lugar.

#include <functional>
#include <iostream>

template<typename T>
struct t2t
{
    typedef T t;
};

template<typename R, typename V1, typename V2>
struct fixpoint
{
    typedef std::function<R (V1, V2)> func_t;
    typedef std::function<func_t (func_t)> tfunc_t;
    typedef std::function<func_t (tfunc_t)> yfunc_t;

    class loopfunc_t {
    public:
        func_t operator()(loopfunc_t v)const {
            return func(v);
        }
        template<typename L>
        loopfunc_t(const L &l):func(l){}
        typedef V1 Parameter1_t;
        typedef V2 Parameter2_t;
    private:
        std::function<func_t (loopfunc_t)> func;
    };
    static yfunc_t fix;
};
template<typename R, typename V1, typename V2>
typename fixpoint<R, V1, V2>::yfunc_t fixpoint<R, V1, V2>::fix = [](tfunc_t f) -> func_t {
    return [f](fixpoint<R, V1, V2>::loopfunc_t x){  return f(x(x)); }
    ([f](fixpoint<R, V1, V2>::loopfunc_t x) -> fixpoint<R, V1, V2>::func_t{
        auto &ff = f;
        return [ff, x](t2t<decltype(x)>::t::Parameter1_t v1, 
            t2t<decltype(x)>::t::Parameter1_t v2){
            return ff(x(x))(v1, v2);
        }; 
    });
};

int _tmain(int argc, _TCHAR* argv[])
{
    auto term = [](int a)->int {
      return a*a;
    };

    auto next = [](int a)->int {
      return ++a;
    };

    auto sum = fixpoint<int, int, int>::fix(
    [term,next](std::function<int (int, int)> sum1) -> std::function<int (int, int)>{
        auto &term1 = term;
        auto &next1 = next;
        return [term1, next1, sum1](int a, int b)mutable ->int {
            if(a>b)
                return 0;
        else
            return term1(a) + sum1(next1(a),b);
        };
    });

    std::cout<<sum(1,10)<<std::endl; //385

    return 0;
}

Estás intentando capturar una variable (suma) que estás definiendo. Eso no puede ser bueno.

No creo que las lambdas C ++ 0x verdaderamente recursivas sean posibles. Sin embargo, deberías poder capturar otras lambdas.

Esta respuesta es inferior a la de Yankees, pero aún así, aquí va:

using dp_type = void (*)();

using fp_type = void (*)(dp_type, unsigned, unsigned);

fp_type fp = [](dp_type dp, unsigned const a, unsigned const b) {
  ::std::cout << a << ::std::endl;
  return reinterpret_cast<fp_type>(dp)(dp, b, a + b);
};

fp(reinterpret_cast<dp_type>(fp), 0, 1);

Necesitas un combinador de punto fijo. Mira esto .

o mira el siguiente código:

//As decltype(variable)::member_name is invalid currently, 
//the following template is a workaround.
//Usage: t2t<decltype(variable)>::t::member_name
template<typename T>
struct t2t
{
    typedef T t;
};

template<typename R, typename V>
struct fixpoint
{
    typedef std::function<R (V)> func_t;
    typedef std::function<func_t (func_t)> tfunc_t;
    typedef std::function<func_t (tfunc_t)> yfunc_t;

    class loopfunc_t {
    public:
        func_t operator()(loopfunc_t v)const {
            return func(v);
        }
        template<typename L>
        loopfunc_t(const L &l):func(l){}
        typedef V Parameter_t;
    private:
        std::function<func_t (loopfunc_t)> func;
    };
    static yfunc_t fix;
};
template<typename R, typename V>
typename fixpoint<R, V>::yfunc_t fixpoint<R, V>::fix = 
[](fixpoint<R, V>::tfunc_t f) -> fixpoint<R, V>::func_t {
    fixpoint<R, V>::loopfunc_t l = [f](fixpoint<R, V>::loopfunc_t x) ->
        fixpoint<R, V>::func_t{
            //f cannot be captured since it is not a local variable
            //of this scope. We need a new reference to it.
            auto &ff = f;
            //We need struct t2t because template parameter
            //V is not accessable in this level.
            return [ff, x](t2t<decltype(x)>::t::Parameter_t v){
                return ff(x(x))(v); 
            };
        }; 
        return l(l);
    };

int _tmain(int argc, _TCHAR* argv[])
{
    int v = 0;
    std::function<int (int)> fac = 
    fixpoint<int, int>::fix([](std::function<int (int)> f)
        -> std::function<int (int)>{
        return [f](int i) -> int{
            if(i==0) return 1;
            else return i * f(i-1);
        };
    });

    int i = fac(10);
    std::cout << i; //3628800
    return 0;
}