C ++ 11의 재귀 람다 함수

C ++ 11의 재귀 람다 함수

---

저는 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 @ linux-718q : ~ / 연구 / 09C ++ / c ++ 0x / lambda> g ++ -std = c ++ 0x sum.cpp

sum.cpp : 람다 함수에서 : sum.cpp : 18 : 36 : 오류 : ' ((<lambda(int, int)>*)this)-><lambda(int, int)>::sum'를 함수로 사용할 수 없습니다

gcc 버전

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

누군가 이것에 빛을 던져 주시겠습니까?

---

자동 버전과 완전히 지정된 유형 버전 의 차이점에 대해 생각하십시오 . 자동 키워드가 추정의가로 초기화있어 어떤에서 유형,하지만 당신은 그것의 유형이 무엇인지 알고 요구를 초기화하고 (이 경우, 람다 폐쇄 요구가 끄는 콘텐츠 유형을 알고). 닭과 계란 문제.

다른 한편으로, 완전하게 지정된 함수 객체의 타입은 그것에 할당 된 것에 대해 아무것도 "알지 않아도"되며, 따라서 람다의 클로저는 캡쳐하는 타입에 대해 완전히 정보를받을 수 있습니다.

다음과 같이 코드를 약간 수정하면 더 이해 될 수 있습니다.

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

분명히 auto와는 작동하지 않습니다 . 재귀 람다 함수는 완벽하게 잘 작동합니다 (적어도 경험이있는 MSVC에서는 그렇습니다). 유형과 실제로 호환되지 않는다는 것입니다.

---

트릭은 람다 구현을 캡처가 아닌 매개 변수 로 공급하는 것 입니다.

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

컴퓨터 과학의 모든 문제는 다른 수준의 간접 지시로 해결 될 수 있습니다 . 나는이 쉬운 트릭을 http://pedromelendez.com/blog/2015/07/16/recursive-lambdas-in-c14/ 에서 처음 발견했습니다 .

그것은 않는 문제는 C ++ 11 일 동안 C ++ (14)을 필요로하지만, 대부분에 아마 흥미 롭군요.

경유 std::function도 가능하지만 코드 속도가 느려질 수 있습니다. 그러나 항상 그런 것은 아닙니다. std :: function vs template에 대한 답변을 살펴보십시오.

---

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

---

CTAD와 함께 C ++ 17에서는 추론 가이드를 추가 할 수 있습니다.

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

도우미 기능이 필요하지 않습니다. 우리는 y_combinator{[](auto self, ...){...}}직접 쓸 수 있습니다.

---

CTAD를 사용하여 C ++ 20에서는 추론 가이드가 필요하지 않습니다.

---

다른 해결책이 있지만 상태 비 저장 람다에서만 작동합니다.

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에서의 작업

---

람다 함수 호출 자체를 재귀 적으로 만들 수 있습니다 . 컴파일러가 반환 및 인수 유형을 알 수 있도록 함수 래퍼를 통해 참조하는 것이 유일한 방법입니다 (아직 정의되지 않은 변수-람다 자체를 캡처 할 수 없음) .

  function<int (int)> f;

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

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

랩퍼의 범위를 벗어나지 않도록 매우주의하십시오. f.

---

외부 클래스 및 함수 (예 std::function: 고정 소수점 조합기) 를 사용하지 않고 람다를 재귀 적으로 만들려면 C ++ 14 ( 실례 ) 에서 다음 구성을 사용할 수 있습니다 .

#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

람다의 결과 유형은 명시 적으로 지정해야합니다.

---

std::function<>캡처 방법을 사용하여 재귀 함수와 재귀 람다 함수를 비교하는 벤치 마크를 실행했습니다 . clang 버전 4.1에서 전체 최적화를 사용하면 람다 버전이 상당히 느리게 실행되었습니다.

#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소규모 펑터를위한 라이브러리 최적화 공간 사용에 맞지 않을 때 자체 성능이 직접 함수를 호출하는 속도 저하의 원인 일 수 있습니다 (다양한 짧은 문자열 최적화와 비슷한 것 같습니까?).

---

이것은 고정 소수점 연산자를 약간 더 간단하게 구현하여 진행 상황을 조금 더 분명하게 만듭니다.

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

---

C ++ 14 : 다음은 재귀 익명의 stateless / no 캡처 일반 람다 세트로 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-combinator 솔루션을 사용하고 있습니다.

그리고 여기 sum (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

---

다음은 OP에 대한 최종 답변입니다. 어쨌든 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;
}

---

정의하는 동안 변수 (합계)를 캡처하려고합니다. 좋지 않습니다.

나는 진정한 자기 재귀 C ++ 0x 람다가 가능하다고 생각하지 않습니다. 그래도 다른 람다를 캡처 할 수 있어야합니다.

---

이 대답은 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);

---

고정 소수점 조합기가 필요합니다. 참조 이 .

또는 다음 코드를보십시오 :

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

참고 URL : https://stackoverflow.com/questions/2067988/recursive-lambda-functions-in-c11