C++实现的一个可以写递归lambda的Y函数

时间:2021-09-10 08:21:30

最近学习C++11的variadic template argument,终于可以摆脱用fpmacro模板来复制一大堆代码的做法了,好开心。这个例子的main函数lambda写了一个斐波那契数列的递归计算函数。跟以往不同的是,在Y函数的帮助下,这个lambda表达是可以成功看到自己,然后递归调用。当然这仍然需要用普通的C++递归来实现,并不是λ-calculus那个高大上的Y Combinator。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <functional>
#include <memory>
#include <iostream>
#include <string>
 
using namespace std;
 
template<typename TResult, typename ...TArgs>
class YBuilder
{
 
private:
 
  function<TResult(function<TResult(TArgs...)>, TArgs...)> partialLambda;
 
public:
 
  YBuilder(function<TResult(function<TResult(TArgs...)>, TArgs...)> _partialLambda)
 
    :partialLambda(_partialLambda)
 
  {
 
  }
 
  TResult operator()(TArgs ...args)const
 
  {
 
    return partialLambda(
 
      [this](TArgs ...args)
 
      {
 
        return this->operator()(args...);
 
      }, args...);
 
  }
 
};
 
template<typename TMethod>
 
struct PartialLambdaTypeRetriver
 
{
 
  typedef void FunctionType;
 
  typedef void LambdaType;
 
  typedef void YBuilderType;
 
};
 
template<typename TClass, typename TResult, typename ...TArgs>
 
struct PartialLambdaTypeRetriver<TResult(__thiscall TClass::*)(function<TResult(TArgs...)>, TArgs...)>
{
 
  typedef TResult FunctionType(TArgs...);
 
  typedef TResult LambdaType(function<TResult(TArgs...)>, TArgs...);
 
  typedef YBuilder<TResult, TArgs...> YBuilderType;
 
};
 
 
template<typename TClass, typename TResult, typename ...TArgs>
 
struct PartialLambdaTypeRetriver<TResult(__thiscall TClass::*)(function<TResult(TArgs...)>, TArgs...)const>
 
{
 
  typedef TResult FunctionType(TArgs...);
 
  typedef TResult LambdaType(function<TResult(TArgs...)>, TArgs...);
 
  typedef YBuilder<TResult, TArgs...> YBuilderType;
 
};
 
 
 
template<typename TLambda>
 
function<typename PartialLambdaTypeRetriver<decltype(&TLambda::operator())>::FunctionType> Y(TLambda partialLambda)
 
{
 
  return typename PartialLambdaTypeRetriver<decltype(&TLambda::operator())>::YBuilderType(partialLambda);
 
}
 
 
 
int _tmain(int argc, _TCHAR* argv[])
 
{
 
  auto fib = Y([](function<int(int)> self, int index)
 
  {
 
    return index<2
 
      ?1
 
      :self(index-1)+self(index-2);
 
  });
 
 
 
  for (int i = 0; i < 10; i++)
  {
 
    cout << fib(i) << " ";
 
  }
 
  cout << endl;
 
}