Рекурсивные лямбда-функции в C++ 11

Question

Я новичок в C++ 11. Я пишу следующую рекурсивную лямбда-функцию, но она не компилируется.

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

ошибка компиляции:

Vimal @ линукс-718q: ~/Исследование/09C++/C++ 0x/лямбда> г ++ -std = C++ 0x сумма. каст

sum.cpp: В лямбда-функции: sum.cpp: 18: 36: ошибка: '((<lambda(int, int)>*)this)-><lambda(int, int)>::sum' не может быть использован в качестве функции

НКУ версия

GCC версии 4.5.0 20091231 (экспериментальный) (GCC)

Но если изменить декларацию sum(), как показано ниже, это работает:

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

Может кто-то пожалуйста, пролить свет на это?

Answer 1

Подумайте о разнице между версией и полностью указанной версией типа. Ключевое слово auto вводит его тип из того, что инициализируется, но то, что вы инициализируете, должно знать, каков его тип (в этом случае закрытие лямбда должно знать типы, которые он захватывает). Что-то вроде проблемы с курицей и яйцом.

С другой стороны, тип полностью заданного функционального объекта не должен «знать» что-либо о том, что ему назначено, и поэтому закрытие лямбды также может быть полностью информировано о типах, которые он захватывает.

Рассмотрим небольшую модификацию кода, и это может сделать больше смысла:

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

Очевидно, что это не будет работать с авто. Рекурсивные лямбда-функции работают отлично (по крайней мере, они работают в MSVC, где у меня есть опыт работы с ними), просто они не совместимы с выводами типа.

Answer 2

Вы пытаетесь захватить переменную (сумму), находящуюся в середине определения. Это не может быть хорошо.

Я не думаю, что действительно саморекурсивный C++ 0x lambdas возможен. Однако вы должны уметь захватить другие лямбды.

Answer 3

Вам нужен комбинатор с фиксированной точкой. См. this.

или посмотрите на следующий код:

//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 4

Вот окончательный ответ на ОП. Во всяком случае, Visual Studio 2010 не поддерживает захват глобальных переменных. И вам не нужно их захватывать, потому что глобальная переменная доступна глобально путем определения. В следующем ответе вместо этого используется локальная переменная.

#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 5

Вы можете сделать функцию лямбда называть себя рекурсивно.Единственное, что вам нужно сделать, это связать его через оболочку функции, чтобы компилятор знал, что это тип возврата и аргумента (вы не можете захватить переменную - сама лямбда - которая еще не определена) ,

function<int (int)> f; 

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

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

Будьте очень осторожны, чтобы не выходить из сферы действия обертки f.

Answer 6

У меня есть другое решение, но работает только с лицами без лямбды:

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

Трюк в том, что лямбды может получить доступ к статическим переменным и вы можете конвертировать лиц без них, чтобы указатель на функцию.

Вы можете использовать его со стандартными лямбды:

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

свою работу в GCC 4.7

Answer 7

Это немного проще реализация Fixpoint оператора, что делает его немного более очевидным, что именно происходит.

#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

Я провел тест сравнения рекурсивной функции против рекурсивного лямбда-функции с использованием методы std::function<> захвата. Благодаря полной оптимизации, включенной в версии 4.1 clang, версия лямбда работала значительно медленнее.

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

Производит результаты:

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

(Примечание: я также подтвердил версию, унесшей входы от CIN, с тем, чтобы исключить компилировать оценки времени)

Clang также производит компилятор предупреждение:

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

Ожидается и безопасно, но следует отметить.

Это здорово, если у вас есть решение в наших инструментальных поясах, но я думаю, что для этого случая язык будет лучше, если производительность будет сопоставима с текущими методами.

Примечание:

Как комментатор отметил, что, кажется, последняя версия VC++ нашел способ оптимизировать это с точки равной производительности. Может быть, нам не нужен лучший способ справиться с этим, в конце концов (кроме синтаксического сахара).

Кроме того, как и некоторые другие сообщения SO, изложенные в последние недели, производительность std::function<> сама по себе может быть причиной замедления или прямой функции вызова, по крайней мере, когда захват лямбда слишком велик, чтобы вписаться в некоторое пространство, оптимизированное библиотекой std::function использует для малых функторов (я думаю, вроде как различные короткие строковые оптимизации?).

Answer 9

Этот ответ уступает одному Yankes', но до сих пор, вот он идет:

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 10

Хитрость заключается в том, чтобы питаться в реализации лямбда себе в качестве параметра, а не захвата.

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

Все проблемы в информатике может быть решена другой уровень косвенности. Я впервые нашел этот простой трюк в http://pedromelendez.com/recursive-lambdas-in-c14/

Это . требует C++ 14, хотя вопрос стоит на C++ 11, но, возможно, интересен для большинства.

Answer 11

С C++ 14 теперь довольно легко сделать эффективную рекурсивную лямбда, не требуя дополнительных накладных расходов std::function, всего несколькими строками кода (с небольшим изменением от оригинала, чтобы не допустить пользователя от принятия случайной копии):

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

, с которым ваш оригинальный sum попытка становится:

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 12

Для того, чтобы лямбда-рекурсивной без использования внешних классов и функций (например, std::function или фиксированной Точка комбинатор) можно использовать следующую конструкцию в C++ 14 (live example):

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

отпечатков:

1 
2 
    8 
3 
    5 
    7 
    6 
4 

Обратите внимание, что результат типа лямбды должен быть задан в явном виде.

Answer 13

C++ 14: Здесь не является рекурсивным анонимным без гражданства/нет захвата общего набора лямбд , который выводит все числа от 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); 

Если я правильно понял это с помощью Y-комбинатор решения

А вот сумма (п, т) версия

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