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

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

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

}
赞 (0)

相关推荐

  • c++递归实现n皇后问题代码(八皇后问题)

    还是先来看看最基础的8皇后问题: 在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行.同一列或同一斜线上,问有多少种摆法. 扩展到N皇后问题是一样的.一看,似乎要用到二维数组.其实不需要.一维数组就能判断,比如Arr[i],就可以表示一个元素位于第i行第Arr[i]列--应用广泛的小技巧.而且在这里我们不用考虑去存储整个矩阵,如果Arr[i]存在,那么我们在打印的时候,打印到皇后位置的时候输出1,非皇后位输出0即可. 这种思路的实现方式网上大把,包括前面提到的那

  • C++使用递归函数和栈操作逆序一个栈的算法示例

    本文实例讲述了C++使用递归函数和栈操作逆序一个栈的算法.分享给大家供大家参考,具体如下: 题目: 一个栈依次压入1.2.3.4.5,那么栈顶到栈底分别为:5.4.3.2.1. 将这个栈逆置后栈顶到栈底分别为1.2.3.4.5. 用递归函数来实现,不能用其他数据结构. 解题思路及代码 1.递归函数一:将栈的栈底元素一个个返回并移除. 2.递归函数二:逆序栈,调用递归函数一实现. C++实现: class Solution { public: //递归函数一 static int getAndRe

  • C++函数的嵌套调用和递归调用学习教程

    C++函数的嵌套调用和递归调用学习教程

    C++函数的嵌套调用 C++不允许对函数作嵌套定义,也就是说在一个函数中不能完整地包含另一个函数.在一个程序中每一个函数的定义都是互相平行和独立的. 虽然C++不能嵌套定义函数,但可以嵌套调用函数,也就是说,在调用一个函数的过程中,又调用另一个函数. 在程序中实现函数嵌套调用时,需要注意的是:在调用函数之前,需要对每一个被调用的函数作声明(除非定义在前,调用在后). [例]用弦截法求方程f(x)=x3-5x2+16x-80=0的根. 这是一个数值求解问题,需要先分析用弦截法求根的算法.根据数学知

  • C/C++函数调用栈的实现方法

    本文实例讲述了C/C++函数调用栈的实现方法.可用于实现简单的脚本解释器.分享给大家供大家参考.具体实现方法如下: 头文件声明部分: 复制代码 代码如下: #pragma once const int BUFFERSIZE = 1024; const int growfactor = 2;   // this stack is used as call stack. class TStack{ private: size_t size;   // the stack length size_t

  • C++递归删除一个目录实例

    本文实例讲述了C++递归删除一个目录的实现方法.分享给大家供大家参考.具体方法如下: CFindFile的使用框架如下: 复制代码 代码如下: void Recurse(LPCTSTR pstr)  {     CFileFind finder;       // build a string with wildcards     CString strWildcard(pstr);     strWildcard += _T("\\*.*");       // start work

  • C++非递归建立二叉树实例

    C++非递归建立二叉树实例

    本文实例讲述了C++非递归建立二叉树的方法.分享给大家供大家参考.具体分析如下: 思路: 设置一个标记变量flag并初始化为1. flag = 1表示现在需要创建当前结点的左孩子,2表示需要创建右孩子,3则表示当前结点的左右孩子都已经创建完毕,需要执行出栈操作,直到当前结点不是父结点的右孩子为止. 以先序创建如图所示二杈树: 实现代码: PBTree create() { char ch[20]; scanf("%s",ch); int len = strlen(ch); PBTree

  • C++ 数据结构实现两个栈实现一个队列

    C++ 数据结构实现两个栈实现一个队列 栈为后进先出,队列为先进先出 用两个栈实现一个队列.是一个比较经典的问题. 看到这个问题,我的第一个解题思路为: 定义两个栈,s1,s2.s1作为入队列栈,s2作为出队列栈: 入队列:每次入队列的时候,将数值压入s1栈中: 出队列:出队列时,将s1中的所有数据,压进s2栈中,然后删除s2的栈顶数据,然后再将s2中的剩余数据压入s1中. 在这其中s1是一个存储空间,s2是一个辅助空间. 进一步想一下上述办法,在出队列时,每一次都要将s1倒进s2,然后删除s2

  • C++中用栈来判断括号字符串匹配问题的实现方法

    本文实例主要实现:输入一个括号字符串,依次检验,若为左括号则入栈,若为右括号则出栈一个字符判断是否与之相对应,在最后还需判断栈是否为空,如果不为空则不匹配. 首先回顾栈的基本知识: 1.定义栈的结构体并初始化一个新栈: struct stack { char strstack[stacksize]; int top; }; void InitStack(stack &s) { s.top=-1; } 2.出栈和入栈操作: char Push(stack &s,char a) { if(s.

  • c++递归解数独方法示例

    复制代码 代码如下: #include<iostream> using namespace std; void init();void function(int m); int canplace(int row,int col,int c); void outputresult(); int a[9][9], maxm = 0; int main() {   init(); function(0);  return 0; } void init(){ int i, j; for(i = 0;

  • C++使用递归方法求n阶勒让德多项式完整实例

    C++使用递归方法求n阶勒让德多项式完整实例

    本文实例讲述了C++使用递归方法求n阶勒让德多项式的实现方法.分享给大家供大家参考,具体如下: /* * 作 者: 刘同宾 * 完成日期:2012 年 11 月 24 日 * 版 本 号:v1.0 * 输入描述: * 问题描述: 用递归方法求n阶勒让德多项式的值.. * 程序输出: * 问题分析:略 * 算法设计:略 */ #include<iostream> using namespace std; int main() { double p(double,double); double s

  • 全排列算法的非递归实现与递归实现的方法(C++)

    (一)非递归全排列算法基本思想是:    1.找到所有排列中最小的一个排列P.    2.找到刚刚好比P大比其它都小的排列Q,    3.循环执行第二步,直到找到一个最大的排列,算法结束.下面用数学的方法描述:给定已知序列 P =  A1A2A3An ( Ai!=Aj , (1<=i<=n  , 1<=j<=n, i != j  ) )找到P的一个最小排列Pmin = P1P2P3Pn  有  Pi > P(i-1) (1 < i <= n)从Pmin开始,总是目

  • C++使用一个栈实现另一个栈的排序算法示例

    本文实例讲述了C++用一个栈实现另一个栈的排序算法.分享给大家供大家参考,具体如下: 题目: 一个栈中元素类型为整型,现在想将该栈从顶到底按从小到大的顺序排序,只许申请一个辅助栈. 除此之外,可以申请新的变量,但不能申请额外的数据结构.如何完成排序? 算法C++代码: class Solution { public: //借助一个临时栈排序源栈 static void sortStackByStack(stack<int>& s) { stack<int>* sTemp =

随机推荐