C ++ 11의 재귀 람다 함수 return term(a)

저는 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 ++에 대한 특이성이 아니라 람다 미적분학의 수학에 직접 매핑됩니다. 에서 위키 백과 :

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


답변

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, ...){...}}직접 쓸 수 있습니다.


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