recursivas - recursividad arreglos c++

Funciones lambda recursivas en C++ 11

Question

Soy nuevo en C ++ 11. Estoy escribiendo la siguiente función recursiva lambda, pero no 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 de gcc

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

Pero si cambio la declaración de sum() como a continuación, 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 por favor arrojar luz sobre esto?

Answer 1

Aquí está la respuesta final para el OP. De todos modos, Visual Studio 2010 no admite la captura de variables globales. Y no necesita capturarlos porque la variable global es accesible globalmente por definir. La siguiente respuesta usa una 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;
}

Answer 2

C ++ 14: Aquí hay un conjunto recursivo anónimo sin estado / sin captura genérica de lambdas que genera todos los números desde 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 es usando la solución Y-combinator

Y aquí está la versión de 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

Answer 3

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 unas pocas líneas de código (con una pequeña edición del original para evitar que el usuario tomando 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 el cual su intento de sum 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);
  }
});

Answer 4

Ejecuté un benchmark comparando una función recursiva versus una función lambda recursiva utilizando el método de captura std::function<> . Con las optimizaciones completas habilitadas en la versión 4.1 de clang, la versión de lambda corría 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 toolbelts, pero creo que el lenguaje necesitará una mejor manera de manejar este caso si el desempeño es comparable a los métodos actuales.

Nota:

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

Además, como algunas otras publicaciones SO han esbozado en las últimas semanas, el rendimiento de std::function<> puede ser la causa de la función de ralentización frente a llamada directamente, al menos cuando la captura lambda es demasiado grande para caber en una biblioteca optimizada space std::function usa para pequeños funtores (supongo que me gustan las diversas optimizaciones cortas de cadenas).

Answer 5

El truco es alimentar la implementación de lambda a sí mismo como un parámetro , no por 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;
    else return term(a) + sum_ref(next(a),b,sum_ref);
  };
  return sum_impl(a,b,sum_impl);
};

Todos los problemas en la informática se pueden resolver con otro nivel de indirección . Primero encontré este truco fácil en http://pedromelendez.com/recursive-lambdas-in-c14/

Requiere C ++ 14 mientras que la pregunta está en C ++ 11, pero quizás sea interesante para la mayoría.

Answer 6

Estás tratando de capturar una variable (suma) que estás en el medio de definir. Eso no puede ser bueno.

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

Answer 7

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

#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'';
    }
}

Answer 8

Esta respuesta es inferior a la de Yankes, 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);

Answer 9

Necesitas un combinador de punto fijo. Mira this

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;
}

Answer 10

Para hacer que lambda sea recursiva sin utilizar clases y funciones externas (como std::function o combinator 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.

Answer 11

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

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

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 automático . Las funciones recursivas de lambda 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.

Answer 12

Puede hacer que una función lambda se llame recursivamente. Lo único que debe hacer es hacer referencia a ella a través de un contenedor de funciones para que el compilador sepa que es un 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 quedarse sin el alcance de la envoltura f.

Answer 13

Tengo otra solución, pero trabajo solo 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 las lambdas pueden acceder a las variables estáticas y usted puede convertir las apátridas en puntero a la 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