注：本文为转载，原文地址作者Trustno1

FP的Combinator 特性

那么我来讲一下FP的Combinator 特性。为了方便描述我们将采用大家比较熟悉的Python 的语法来描述问题。我们同样也沿用XP的refectoring的方法来逐渐的展现整个Combinator 的特性。为了方便期间，我们把FP中的函数称为算式以示与imperative语言的函数进行区别理由见上贴。考虑下面的三个算式，第一个算式计算从a到b的所有自然数之和:

def sum_integers (a,b):  
    if a>b then:  
        return 0  
    else:  
        a+sum_integers(a+1,b)

第二个算式计算从a到b的每个自然数的立方和

#定义立方算式  
def cube (x):  
    return x*x*x  
  
def sum_cubes(a,b):  
    if a>b then:  
        return 0  
    else:  
        cube(a)+sum_cubes(a+1,b)

第三个算式，我们来计算一个级数展开式，这是一个计算 π/8 的莱布尼兹展开式。

1/(1*3) +  1/(5*7) + 1/(9*11) + ...

def pi_sum (a,b):  
    if a>b then:  
        return 0  
    else:  
        1.0/((a+2)*a)+pi_sum(a+4,b)

很明显，这三个算式内部具有相同的模式。他们大部分是相同的。他们不同之处仅仅在于，每个函数的被加数不同，每次步进的长度不同，当然还有他们的名字不同。是不是已经闻到了badsmell 了？好那么我们来refactoring.我们可以生成这样一个模板:

def <name> (a,b):  
    if (a>b)  
      return 0  
    else  
      <term>(a)+<name>(<next>(a),b)

这种抽象模式应该很简单不用多说。不过实际上在数学中这种抽象表达早就存在了，那就是我们非常熟悉的Sigma 标记。例如

Sigma标记的威力在于它允许数学家们处理和运算这个概念本身，而不仅仅是具体的加法运算。同样，对于程序设计者来说，抽象这样的运算也是情理之中的事情的。

def sum(term,a,next,b):  
    if a>b then:  
        return 0  
    else:  
        term(a)+sum(term,next(a),next,b)  
def inc(n):  
    return n+1  
  
def sum_cubes(a,b):  
    sum(cube,a,inc,b)  
  
def sum_integers(a,b):  
    sum(lambda x:x,a,inc,b)  
  
def pisum(a,b):  
    sum(lambda x:1.0/((x+2)*x),a,lambda y:y+4,b)

sum这个函数就称为一个High order Fucntion,或者称为一个Combinator.他能把各种不同的函数连接起来形成一个新算法。我们可以用这个sum干很多事情，例如我们可以轻而易举的算出一个函数从区间[a,b]的积分。我们可以用龙贝格积分展开式来求解:

def integral(f, a, b, dx):
    dx * (sum(f, a+dx/2.0, lambda x:x+dx, b))

我们可以看到，如果换成C语言，我们或许会用，函数指针，这种丑陋的东西我就不说了。如果我们采用Java则只能使用interface。例如我们可以改成这样。

class sum  
{
private:  
  Iterm term;  
  Inext next;  
  int a;  
  int b;  
public:  
   sum(Iterm t,int a,Inext n,int b)  
  {
    term=t;  
    next=n;  
    a=a;  
    b=b;  
  }
int   do_sum()  
  {
     if (a>b)  
     return 0;  
     else  
     {
       int  t=a;  
       a=n.donext(a);  
       t.doterm(t)+do_sum();     
     }
  }
}

从抽象的效果来说，他们是同样的。但是从语法上实在是太累赘，Combinator本身抽象的就是算法或者说是业务逻辑，而承载逻辑的最基本单元函数却不是第一等的公民，只能负载在类上进行传递。从OO来说的确不善于抽象逻辑和算法。以前 STL之父说过，不是所有的东西都是对象，算法就不是对象。STL中的用functor抽象算法和FP有些像，但是还只是东施效颦罢了。FP并不长于运算，而是长于逻辑的推导。这种推导，在数学上称为算子空间什么算子和算子空间呢？我们数学中知道，f(x)，x有定义域 f(x)有值域。而我们把x 的定义域的概念进行扩展，我们把每个函数看成一个集合中的元素。然后将所有算子的集合为抽象空间或者函数空间(也就是说值域这个集合中的每个元素都是一个函数).例如上面的各种各样的term和next就是一系列的算子，他们的集合就叫做抽象空间。一个算子可以看作这个空间里面的一个点，算子的组合即可以看作函数空间中的向量组合。在数学里我们空间的两个点表示a:[x1,y1,z1]，b:[x2,y2,z2],他们的组合就成为一个线段，如果有这个线段产生方向就成为一个a->b的向量。因为算子和算子之间也是有方向的，最简单就是运算顺序。那么算子和算子之间就是算子向量。由于算子所作用的集合并没有维数的限制，在函数空间集础上所研究出来算子的各种性质，成为处理用有穷维或者线性空间逼近无穷维集合问题的有力武器。因此我们可以看到其实算子空间本身具有的性质就是N维正交。也就是说每个算子都是独立互不干扰的。他不会有OO那样牵扯不清的各种问题。所以我经常说FP的研究的就是算法的算法。这只是一个简单的实现。Combinator 可以做很多你都想不到的事情，例如最著名的Y Combinator和不动点。这个东西可以说是 FP中最精彩的一笔，限于篇幅以及鉴于它让人抓狂的程度我是不准备介绍他们了。

我前面也说过了，从Fortran开始的所有主流计算机语言其实都背叛了Turning machine.Church-Turing Thesis说，一个机械算法(mechanical method)总能被转化为等价的图灵机。但是这并不是是说一切机械算法都是从图灵计算理论出发的，冯。诺依曼体系结构下的机械算法也可以转化为图灵机，但是它绝对不是图灵计算模型。简言之，就是它们可能是两套完备的体系，都能用来描述世界。

图灵计算模型，或者说图灵机的精髓在于模拟人的计算过程。一根无限长的纸带，一个读写头和一个状态，就能够模拟人的基本计算过程。在计算的过程中，以一套公理体系为基础，不加以区分程序或者数据。然而，假想一条无限长的纸带是不现实的，计算机尚不能拥有无限的寄存器和内存，因此冯。诺依曼体系以"存储程序"的方式提供一个另外的选择，使得计算机能够被实际制造出来。正是因为计算机的存储限制，程序需要和数据区分开来，才能够在合适的时间调入合适的程序。

Lisp无疑是最根本遵循图灵计算模型的语言，其本身就是计算公理化的结果。例如，准旬van Nueman的c++/Java中的函数都是通过堆栈来记录状态来代替那条无穷长的纸带，所有的数组都是有限的。而lisp中的函数与状态无关，而且 list这样的结构也可以表示成无穷数组例如(1,2,3....)就是一个自然数集合，因为他所有的数据都是lazy的只有计算到了才会有意义。 Lisp语言族所注重的是通过统一的数据结构使得程序和数据之间再没有界限（它们都是S表达式），从而能够以公理体系的方式得到演进并解决问题。而从 Fortran 开始的编译语言采用的模型正是强类型系统，数据结构和算法分离，以及程序与数据分离，追求的是速度和效率。著名的紫皮书中谈到Lisp和 Pascal的区别时也说："Pascal是为了建造金字塔...Lisp是为了建造有机体...""作为Lisp的内在数据结构，表对于这种可用性起着重要的提升作用...""采用100函数在一个数据结构上操作，远远优于采用10个操作在十个数据结构上工作""金字塔矗立在那里千年不变，而有机体则必须演化，否则就会消亡"(XP,refactoring的思想源泉就是在这里，所以我特别推荐程序员学习FP，对自己的思维都很有好处)。

我说C++和Fortran等语言背离了图灵的基本计算理论，并不是说它们有什么不好的地方，它们正是最贯彻执行了冯。诺依曼这一经典体系结构的东西。但是在讨论到函数式编程的时候，如果不这样区分清楚，就根本不能触及到函数式编程的本质。

"金字塔矗立在那里千年不变，而有机体则必须演化，否则就会消亡" 大家有可能觉得这些话似乎有些夸张而且不可理解。那么我们现在来体会一下什么是金字塔和有机体的区别。在这里我同时会介绍Monad Combinator。好我们现在先不管那些神神道道的东西。我们先来看个Case,我们可爱的多利羊是个克隆羊，他只有母亲没有父亲。如果我们为一只羊建立一个族谱，也就是说建立一颗二叉树如下

 1   
 2                      Sheep  
 3        mother              father  
 4  mother father    mother father  
 5  .................................  
 6

这个很简单没有什么可以多说的。那么我们可以建立这样一个数据结构

class Sheep:  
    def __init__(self,name,mother,father):  
        self.name=name  
        self.mother=mother  
        self.father=father  
if __name__=="__main__":  
    adam=Sheep("adam",None,None)  
    eve =Sheep("eve",None,None)  
    uranus=Sheep("uranus",None,None)  
    gaea=Sheep("gaea",None,None)  
    kronos=Sheep("kronos",gaea,uranus)  
    holly=Sheep("Holly",eve,adam)  
    roger=Sheep("Roger",eve,kronos)  
    molly=Sheep("Molly",holly,roger)  
    dolly=Sheep("Dolly",molly,None)

好现在呢？我们需要根据一个给定的路径找到这头羊的特定祖先，例如我们给定 molly->mother->father->father这样一个特定的路径。怎么做呢？当然首先想到的就是我们OO中的.操作，molly.mother.father.father。不过可惜我们有了克隆技术，如果当中某个 Ancestor是None的话那么就会出现exception.而且 molly.mother.father.father，这种东西不容易定制。那么我们现在就用FP的有机体的思考方式来解决一下这个问题: 恩，作为自底向上的方法，我们先不管具体的实现，我们先从最基本的地方开始我们设计两个函数

def mother(sheep):  
       return sheep.mother  
def father(sheep):  
        return sheep.father

这太简单了。那么我们可以这样想，对于molly.mother.father.father最愚蠢的一种实现是什么呢？

if sheep == None :  
    return None  
else:  
    sheep1=mother (sheep)  
    if  sheep1==None:  
       return  None  
    else:  
        sheep2=father(sheep1)  
        if sheep2==None:  
             return None  
        else  
             sheep3=father(sheep2)  
             if(sheep3==None):  
                return None  
             else:  
               return Sheep3

好这个实现够愚蠢把。但是你可别笑，无论你用什么样的算法转译成机器代码都是这个样子。好既然这个算法很bad smell，那么我们再来refectoring一下我们可以看到

  if xx==None:  
        return None  
   else  
         function (xx)

这是这段实现的最基本的材料，有点像细胞一样。我们把他们称为Monad我们可以抽象出这样的函数:

 a->(a->Maybe b)->Maybe b

这里采用了Haskell的描述，因为Haskell的函数类型描述准旬Haskell Curry(一个数学家)表示,所以表达起来就比较方便。这段是什么意思呢？也就说一个函数首先接受一个参数为a。然后再接收一个参数这个参数是一个 function,这个function本身接收一个a的参数，并且返回一个值。这个值是一个Maybe 类型也就是Maybe b=Nothing| Just b。这个类型的意思是这个类型要么是b,要么是Nothing。当然在Python中很简单每个变量都是一个Maybe类型，要么有具体的值要么只有 None.Ok接收了a和这个function后我们返回另外一个Maybe b 类型。怎么样是不是觉得这种表述和上面那段判断代码很像呢？没错我们来看看这个Monad 如何表示成函数

def Combinator(sheep,function):  
    if(sheep==None) :  
        return None  
    else:  
        return function(sheep)

在这里，sheep就是a,fucntion就是a->Maybe b.这里的function 可以father或者mother，他们接受一个sheep有可能返回一个Sheep,有可能返回一个None.那么整个Combinator的函数的返回值不是None就是一个Sheep 也就是一个Maybe b 好了我们现在再来写一个愚蠢的代码

Combinator(Combinator(Combinator(molly,mother),father),father)

好了，自己用逻辑推导一下，他是不是就是molly.mother.father.father 当然写这么长的代码的确有些BadSmell，那么我们再来Refectoring这段代码的抽象过程是，把molly,mother进行运算然后把结果和father再进行运算。这个模式可以一直继续下去。那么我们可以将这个模式抽象成一个函数。当然这个函数不用我们写了Python中已经有了，那就是reduce: reduce(fucntion,[....])这个函数接受一个函数和一个List作为参数，他首先把list的第一第二个元素用function进行运算，然后把运算结果和第三个元素进行运算以此类推。例如

reduce(lambda x,y:x+y,[1,2,3,4,5])

这就是从1到5的和好这个函数正好对我们有用那么我们就可以将上面那个愚蠢的代码写成这样

class Sheep:  
    def __init__(self,name,mother,father):  
        self.name=name  
        self.mother=mother  
        self.father=father  
         
def mother(sheep):
       return sheep.mother  
def father(sheep):  
        return sheep.father  
  
def Combinator(sheep,function):  
    if(sheep==None):  
        return None  
    else:  
        return function(sheep)  
  
def gotAncestor (pedigree):  
    return reduce(Combinator,pedigree)  
  
if __name__=="__main__":  
    adam=Sheep("adam",None,None)  
    eve =Sheep("eve",None,None)  
    uranus=Sheep("uranus",None,None)  
    gaea=Sheep("gaea",None,None)  
    kronos=Sheep("kronos",gaea,uranus)  
    holly=Sheep("Holly",eve,adam)  
    roger=Sheep("Roger",eve,kronos)  
    molly=Sheep("Molly",holly,roger)  
    dolly=Sheep("Dolly",molly,None)   
    test=[molly,mother,father]  
    print gotAncestor(test).name  
    test=[dolly,father,father]  
    ret=gotAncestor(test)  
    if ret==None:  
        print "None"

看到了么？这就是FP的惊奇所在，我们之所以把Combinator称为Monad.因为mother father 只是一些代码的片断，就像是DNA的ADTG的四个基因一样，当然这个算式基因只有2 个。Combinator就像是规定了基因的排列顺序，组合成一个单体的细胞。通过reduce又能像细胞的无丝分裂那样分裂出其他的细胞，最后得到一个非常简单的有机体。我也写了一个传统的 imperative的代码

def getAncestor2 (child,pedigree,generation):  
    if pedigree==None:  
        return None  
    else:  
        if(pedigree[generation]=="mother"):  
            return getAncestor2(mother(child),pedigree,generation+1)  
        else:  
            return getAncestor2(father(child),pedigree,generation+1)  
    if __name__=="__main__":  
       getAncestor2 (molly,["mother","father","father"],0)

这样的代码就像是金字塔，从一开始我们就把整个算法规划好了，这个代码不能做任何的改动。与上面的有机体，是截然两种味道。一旦我们要 refectoring这个代码，我们可能就会要做更多的工作，而且有可能是推倒从来。而FP不一样，他所有的代码都是一片一小片的片断，首先这些小片段的改动将比动整个金字塔来的更加容易，其次这些小片断天生就是独立正交不相互干扰，我修改了mother,不会干扰father,而OO要做到这样就要动用接口，模式这种非常笨重的方法。FP中并不存在OO的模式，因为它根本不需要模式。有兴趣的可以把Combinator用Java实现以下，你会发现你的代码很华丽。所以XP和refactoring对于FP来说是最自然不过的事情，FP与OO/impervative相比XP和refaction的成本要底的多。其实这个Combinator是一个非常有用的Monad,不光光是能算羊的祖先(这只是最简单的 Monad，我们还有其他更加强大的 Monad)。他可以用在Hash表或者DataBaseQuery里面都非常有用，举个小例子如果我有一个数据库表形态如下

ID,name,Age,Gender,Position

假设我们现在还没有发明SQL语句。我们要来查询年龄>20,Gender是男性的，Positon为 Manager的人员怎么做呢？

class employee:
    def __init__(self,ID,name,Age,Gender,Position):  
        self.ID=ID  
        self.Name=name  
        self.Age=Age  
        self.Gender=Gender  
        self.Position=Position  
def checkAge(Empee):  
        if(Empee.Age<20):  
             return None  
        else  
             return Empee  
  
def checkGender(Empee):  
        if(Empee.Gender!="male"):  
               return None  
        else  
               return Empee  
  
def checkPosition(Empee):
        if(Empee.Position!="manager"):  
            return None  
        else:  
            return Empee  
  
def Query(Rowset,QuerySet):  
      map(lambda record:reduce(Combinator,record.insert(record,-1)), Rowset)

rowset=[........]#构造数据
Query (rowset,[ checkAge, checkGender,checkPosition]))

先说明一下，map和reduce类似也是一种combinator，他接收一个函数，一个列表，把列表的每个元素送入函数进行运算，然后把结果组合成一个新的列表。这个代码可能大家闻上去有好多的badsmell，但是我说别急你们不都是XP的信徒么。 badsmell没有关系，FP的工作方法就是一开始写最臭不可闻的代码，然后慢慢的归纳算法的规律，慢慢的演化。要一步登天那是不可能的。至于如何refactoring这个代码就当作练习好了。我们先不管这些Badsmell，我们关注一下Query (rowset,[ checkAge, checkGender,checkPosition]))这段代码我们会发现，[ checkAge, checkGender,checkPosition]，这个列表和我们即将要发明的SQL语言是多么的相似。只要我们想办法把CheckAge ,变成可以提供参数的(其实这个非常简单我这里先不说大家慢慢琢磨)，那么这个Query就是一个最基本的SQL雏形了。将来我们发明了SQL，将SQL 解析成这样一张列表也是非常的方便。相反如果你用impervative代码写循环去查询，那么整个代码和SQL就差了好多好多好多。你要发明SQL恐怕要花上相当多的力气。

OK,千言万语汇成一句话，FP就是:运算算法的算法和生成代码的代码。我觉得大家可以把自己经历过的业务逻辑，抽象出来放到python里面去看看是不是用FP去抽象这些算法要比原来的impervative语言来得更加清楚和方便。

FunctionProgramAbt

FP的Combinator 特性