Rekurencyjne funkcje lambda w C ++ 11

143

Jestem nowy w C ++ 11. Piszę następującą rekurencyjną funkcję lambda, ale nie kompiluje się.

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

błąd kompilacji:

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

sum.cpp: W funkcji lambda: sum.cpp: 18: 36: błąd: „ ((<lambda(int, int)>*)this)-><lambda(int, int)>::sum” nie można użyć jako funkcji

wersja gcc

gcc wersja 4.5.0 20091231 (eksperymentalna) (GCC)

Ale jeśli zmienię deklarację sum()jak poniżej to działa:

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

Czy ktoś mógłby rzucić na to światło?

weima
źródło
Czy może to być deklaracja statyczna lub niejawnie dynamiczna?
Hamish Grubijan
3
Co mutabletam robi słowo kluczowe?
Pozdrawiam i hth. - Alf,
Przechwytywanie zmiennych z nieautomatycznym czasem przechowywania jest niedozwolone. Powinieneś to zrobić w ten sposób: chat.stackoverflow.com/transcript/message/39298544#39298544
Euri Pinhollow
Do Twojej wiadomości, w drugim fragmencie kodu twoja lambda jest zbyt szczegółowa, rozważ tę zmianę:std::function<int(int,int)> sum = [&](int a, int b) {
armanali

Odpowiedzi:

189

Pomyśl o różnicy między wersją automatyczną a pełną wersją typu. Te auto wyprowadza słów kluczowych jego typ z cokolwiek to jest inicjowany, ale co ty inicjowanie go musi wiedzieć, co jest jego typ (w tym przypadku potrzeby zamykania lambda znać typy to przechwytywanie). Coś w rodzaju problemu jajka i kury.

Z drugiej strony, w pełni określony typ obiektu funkcji nie musi „wiedzieć” o tym, co jest do niego przypisane, a więc zamknięcie lambdy może być również w pełni poinformowane o typach, które przechwytuje.

Rozważ tę niewielką modyfikację swojego kodu i może mieć więcej sensu:

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

Oczywiście to nie zadziała z auto . Rekurencyjne funkcje lambda działają doskonale (przynajmniej działają w MSVC, gdzie mam z nimi doświadczenie), po prostu nie są tak naprawdę zgodne z wnioskiem o typie.

IM McIntosh
źródło
3
Nie zgadzam się z tym. Typ lambda jest dobrze znany, gdy tylko zostanie wprowadzona treść funkcji - nie ma powodu, aby nie można go było wtedy wydedukować.
Puppy
16
@DeadMG, ale specyfikacja zabrania odwoływania się do autozmiennej w jej inicjatorze. typ zmiennej auto nie jest jeszcze znany, kiedy inicjalizator jest przetwarzany.
Johannes Schaub - litb
1
Zastanawiasz się, dlaczego nie jest to oznaczone jako „odpowiedź”, a Python jest sklasyfikowany jako „odpowiedź” ?!
Ajay
1
@Puppy: Jednak w przypadku niejawnego przechwytywania, dla wydajności, tylko zmienne, do których istnieją odniesienia, są faktycznie przechwytywane, więc treść musi zostać przeanalizowana.
kec
Czy istnieje poprawna interpretacja dla suminnego niż std::function<int(int, int)>, czy specyfikacja C ++ po prostu nie zadała sobie trudu, aby ją wywnioskować?
Mateen Ulhaq
79

Sztuczka polega na tym, aby przekazać implementację lambda do siebie jako parametr , a nie przez przechwycenie.

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

Wszystkie problemy w informatyce można rozwiązać na innym poziomie pośrednictwa . Po raz pierwszy znalazłem tę prostą sztuczkę na http://pedromelendez.com/blog/2015/07/16/recursive-lambdas-in-c14/

To nie wymaga C ++ 14, natomiast pytanie o C ++ 11, ale być może najbardziej interesujące.

Przechodzenie przez std::functionjest również możliwe, ale może skutkować wolniejszym kodem. Ale nie zawsze. Spójrz na odpowiedzi na std :: function vs template


To nie tylko osobliwość C ++, ale bezpośrednie odwzorowanie na matematykę rachunku lambda. Z Wikipedii :

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
Johan Lundberg
źródło
3
Wydaje się to znacznie gorsze niż jawne używanie function<>. Nie rozumiem, dlaczego ktoś by to wolał. Edycja: najwyraźniej jest szybszy.
Timmmm,
17
jest to o wiele lepsze niż std :: function z 3 powodów: nie wymaga kasowania typu ani alokacji pamięci, może być constexpr i działa poprawnie z parametrami auto (szablonowymi) / typem zwracanym
Ivan Sanz-Carasa
3
Przypuszczalnie to rozwiązanie ma również tę zaletę, że można je skopiować bez odniesienia do funkcji std :: wykraczającego poza zakres?
Uri Granta
3
Hm, próbując, GCC 8.1 (linux) narzekał: error: use of ‘[...]’ before deduction of ‘auto’- potrzebne do jawnego określenia typu zwracanego (z drugiej strony nie potrzebował mutowalności).
Aconcagua
@Aconcagua to samo tutaj z Xcode10 i ustawiłem standard C ++ na nawet 17
IceFire
39

W C ++ 14 jest teraz całkiem łatwo stworzyć wydajną rekurencyjną lambdę bez konieczności ponoszenia dodatkowego narzutu std::function, w zaledwie kilku wierszach kodu (z niewielką edycją oryginału, aby uniemożliwić użytkownikowi wykonanie przypadkowej kopii ):

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

z którym twoja pierwotna sumpróba staje się:

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

W C ++ 17 z CTAD możemy dodać przewodnik po dedukcji:

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

Co eliminuje potrzebę funkcji pomocniczej. Możemy po prostu napisać y_combinator{[](auto self, ...){...}}bezpośrednio.


W C ++ 20, z CTAD dla agregatów, przewodnik dedukcji nie będzie potrzebny.

Barry
źródło
To jest świetne, ale można rozważyć std::forward<decltype(sum)>(sum)zamiast sumw ostatniej linii.
Johan Lundberg
@Johan Nie, jest tylko jeden, operator()więc nie ma nic do zyskania przez przekazywaniesum
Barry
Och, to prawda. Nie jest używany do korzystania z odwołań do przekazywania dalej bez przekazywania.
Johan Lundberg
Z pewnością najlepszy jest kombinator Y. Ale naprawdę powinieneś dodać nie- constprzeciążenie na wypadek, gdyby dostarczony obiekt-funkcji nie był constoperatorem wywołania. I użyj SFINAE i oblicz noexceptdla obu. Ponadto nie ma już potrzeby korzystania z funkcji maker w C ++ 17.
Deduplicator
2
@minex Tak, auto sumkopiuje ... ale kopiuje a reference_wrapper, co jest tym samym, co pobieranie referencji. Zrobienie tego raz podczas implementacji oznacza, że ​​żadne użycie nie zostanie przypadkowo skopiowane.
Barry
22

Mam inne rozwiązanie, ale pracuję tylko z bezstanowymi lambdami:

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

Sztuczka polega na tym, że lambdy mają dostęp do zmiennych statycznych i można przekonwertować je bezstanowe na wskaźnik funkcji.

Możesz go używać ze standardowymi lambdami:

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

Jego praca w GCC 4.7

Yankes
źródło
3
Powinno to mieć lepszą wydajność niż std :: function, więc +1 dla alternatywy. Ale tak naprawdę, w tym momencie zastanawiam się, czy użycie lambd jest najlepszą opcją;)
Antoine,
Jeśli masz bezstanową lambdę, równie dobrze możesz po prostu nadać jej pełną funkcję.
Timmmm
1
@Timmmm Ale wtedy część implementacji przecieka do zewnętrznego słowa, zwykle lambdy są ściśle powiązane z funkcją nadrzędną (nawet bez przechwytywania). Gdyby tak nie było, nie należy w pierwszej kolejności używać lambd i używać normalnych funkcji funktorów.
Yankes,
10

Państwo może dokonać funkcja lambda nazywać się rekurencyjnie. Jedyne, co musisz zrobić, to odwołać się do niego za pomocą opakowania funkcji, aby kompilator wiedział, jaki jest jego zwrot i typ argumentu (nie możesz przechwycić zmiennej - samej lambdy - która nie została jeszcze zdefiniowana) .

  function<int (int)> f;

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

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

Uważaj, aby nie zabraknąć opakowania opakowania f.

Zuza
źródło
3
Ale jest to identyczne z zaakceptowaną odpowiedzią i może mieć karę za użycie funkcji std.
Johan Lundberg
9

Aby uczynić lambdę rekurencyjną bez użycia zewnętrznych klas i funkcji (takich jak std::functionlub kombinator stałoprzecinkowy), można użyć następującej konstrukcji w C ++ 14 ( przykład na żywo ):

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

wydruki:

1
 2
  8
 3
  5
   7
  6
 4

Uwaga: typ wyniku lambda powinien być jawnie określony.

Tomilov Anatoliy
źródło
6

Przeprowadziłem test porównawczy porównujący funkcję rekurencyjną z rekurencyjną funkcją lambda przy użyciu std::function<>metody przechwytywania. Z pełną optymalizacją włączoną w wersji Clang 4.1, wersja lambda działała znacznie wolniej.

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

Daje wyniki:

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

(Uwaga: potwierdziłem również wersją, która pobierała dane wejściowe z cin, aby wyeliminować ocenę czasu kompilacji)

Clang generuje również ostrzeżenie kompilatora:

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

Co jest oczekiwane i bezpieczne, ale należy to zauważyć.

Wspaniale jest mieć rozwiązanie w naszych paskach narzędzi, ale myślę, że język będzie wymagał lepszego sposobu obsługi tego przypadku, jeśli wydajność ma być porównywalna z obecnymi metodami.

Uwaga:

Jak zauważył komentator, wydaje się, że najnowsza wersja VC ++ znalazła sposób na zoptymalizowanie tego do punktu równej wydajności. Może w końcu nie potrzebujemy lepszego sposobu, aby sobie z tym poradzić (z wyjątkiem cukru syntaktycznego).

Ponadto, jak wskazały inne posty SO w ostatnich tygodniach, wydajność std::function<>sama w sobie może być przyczyną spowolnienia w porównaniu do bezpośredniego wywoływania funkcji, przynajmniej gdy przechwytywanie lambda jest zbyt duże, aby zmieścić się w niektórych zoptymalizowanych bibliotekach std::functionzastosowań przestrzeni dla małych funktorów (Myślę, że trochę lubię różne optymalizacje krótkich ciągów?).

mmocny
źródło
2
-1. Zauważ, że jedynym powodem, dla którego wersja "lambda" trwa dłużej, jest to, że wiąże się ją z funkcją std ::, co powoduje, że operator () wywołuje wywołanie wirtualne, a to oczywiście trwało dłużej. Co więcej, Twój kod w trybie wydania VS2012 zajmował mniej więcej tyle samo czasu w obu przypadkach.
Yam Marcovic
@YamMarcovic What? Jest to obecnie jedyny znany sposób zapisania rekurencyjnej lambdy (taki był punkt przykładu). Bardzo się cieszę, że VS2012 znalazł sposób na zoptymalizowanie tego przypadku użycia (chociaż ostatnio pojawiło się więcej zmian w tym temacie, najwyraźniej gdyby moja lambda przechwyciła więcej, nie mieściłaby się w std :: function small- optymalizacje funktorów pamięci lub inne).
mmocny
2
Potwierdzony. Źle zrozumiałem twój post. Wtedy +1. Gah, możesz głosować za głosem tylko wtedy, gdy edytujesz tę odpowiedź. Czy mógłbyś więc nieco to podkreślić, na przykład w komentarzu?
Yam Marcovic
1
@YamMarcovic Gotowe. Doceniam Twoją chęć udzielenia informacji zwrotnej i poprawienia jej w razie potrzeby. +1 dla ciebie, dobry panie.
mmocny
Czas 0 zwykle oznacza „zoptymalizowano całą operację”. Pobieranie danych wejściowych z cin nic nie daje, jeśli kompilator udowodni, że nic nie robisz z wynikiem obliczeń.
Yakk - Adam Nevraumont
1

Jest to nieco prostsza implementacja operatora punktu stałego, dzięki czemu jest trochę bardziej oczywiste, co się dzieje.

#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';
    }
}
Pseudonim
źródło
Myślę, że możesz poprawić swoją odpowiedź (pod względem wydajności), jeśli zastąpisz std::functionwskaźnikiem funkcji (rdzeni będzie działać tylko z normalną funkcją i bezstanowymi lambdami). Btw fib_nonrpowinien zaakceptować fixpoint<int,int>, jeśli używasz std::functionjego wymaganego tworzenia nowej kopii z *this.
Yankes
1

Oto udoskonalona wersja rozwiązania kombinatora Y oparta na rozwiązaniu zaproponowanym przez @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)}; };

Aby z tego skorzystać, można wykonać następujące czynności

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

Jest podobne do let recsłowa kluczowego w OCaml, ale nie jest takie samo.

Matemagik
źródło
0

C ++ 14: Oto rekurencyjny, anonimowy, bezstanowy / bez przechwytywania zestaw lambd, który wyświetla wszystkie liczby od 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);

Jeśli dobrze rozumiem, jest to rozwiązanie z kombinatorem Y

A oto wersja 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
Jonas Brandel
źródło
-1

Oto ostateczna odpowiedź na PO. W każdym razie Visual Studio 2010 nie obsługuje przechwytywania zmiennych globalnych. I nie musisz ich przechwytywać, ponieważ zmienna globalna jest dostępna globalnie przez zdefiniowanie. Następująca odpowiedź używa zamiast tego zmiennej lokalnej.

#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;
}
Earth Engine
źródło
Czy można uczynić ten kompilator odpowiedzi agnostykiem?
rayryeng
-2

Próbujesz uchwycić zmienną (sumę), którą właśnie definiujesz. To nie może być dobre.

Nie sądzę, aby możliwe były prawdziwie autorekurencyjne lambdy C ++ 0x. Powinieneś być jednak w stanie wychwycić inne lambdy.

Terry Mahaffey
źródło
3
ale działa, jeśli deklaracja sumy zostanie zmieniona z „auto” na std :: function <int (int, int)> bez zmiany listy przechwytywania.
weima
Bo to już nie jest lambda, ale funkcja, której można użyć zamiast lambdy?
Hamish Grubijan
-2

Ta odpowiedź jest gorsza od odpowiedzi Yankesa, ale mimo to brzmi:

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);
user1095108
źródło
Myślę, że powinieneś tego unikać reinterpret_cast. Prawdopodobnie najlepszym sposobem w twoim przypadku jest stworzenie struktury, która zastąpi dp_type. Powinien mieć pole fp_type, może być zbudowany z fp_typei mieć operator ()z argumentami takimi jak fp_type. Będzie to bliskie, std::functionale pozwoli na argumentację odwołującą się do siebie.
Yankes
Chciałem zamieścić minimalny przykład, bez struktury, nie krępuj się edytować mojej odpowiedzi i dostarczyć bardziej kompletne rozwiązanie. A structdodałby również dodatkowy poziom pośredni. Przykład działa, a obsada jest zgodna ze standardami, nie wiem, do czego -1służyła.
user1095108
nie, struct będzie działać tylko jako kontener dla wskaźnika i zostanie przekazana jako wartość. Nie będzie to bardziej pośrednie ani narzuty niż wskaźnik. I o -1tym nie wiedziałem, kto ci go dał, ale myślę, że to dlatego, że reinterpret_castpowinno być używane jako ostateczność.
Yankes
Ma castpodobno działać zgodnie ze standardem c ++ 11. Używanie struct, w moich oczach, mogła pokonać wykorzystanie obiektu lambda. W końcu to, structco proponujesz, jest funktorem wykorzystującym obiekt lambda.
user1095108
Spójrz na rozwiązanie @Pseudonim, usuń tylko, std::functiona będziesz miał coś zbliżonego do tego, o czym myślałem. To prawdopodobnie będzie miało podobną wydajność do twojego rozwiązania.
Yankes
-3

Potrzebujesz kombinatora punktów stałych. Zobacz to .

lub spójrz na poniższy kod:

//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;
}
Earth Engine
źródło