Java 语言中的函数编程

I/O概念。
在FP中，是不能寄存状态的。在说明状态寄存这点之前首先要明确一点。FP中的函数与java/C#中的函数有相当大的区别，而与数学中的函数是趋于一致的。这是什么意思呢？我们来看这样的例子
数学函数
f(x)=3x+1，一个非常简单的一次函数，
我们再对比C的函数
int f(int x){return 3x+1;}
这两个函数最大的区别就在于自变量X上，在数学函数上x是immutable的.也就是说f(x),如果我们设定x=1的话，在函数内部x无论如何都不会改变值。
而C函数中就不一样了

int f(int x);{
x=100;
return 3x+1;
}

其中的X是可以随意改变的。FP的函数语义尊从数学表达式的语义，其自变量是不能进行从新邦定的，这在FP中叫做referentially transprenty引用透明。
那么也就是说FP函数中的Fuction是不能寄存状态的。一个函数接受一个输入，得到一个输出。只要输入一样，输出的结果也必然一样。我们在Java里面经常这样做

class A
{
  int t;
   A();
   {
     t=100;
    }
    void  dec();
    {
       System.out.pring(t--);;
     }
}

A a=new A();
a.dec();
99
a.dec();
98

这样的函数我们就称为带了状态了。I/O其实就是这样带状态的处理方式。但是我们说了FP中的函数是不能带状态的。一般有两种方式进行处理，在非pure FP例如Lisp中，有专门的语法来允许对变量进行
设值，因此我们称这种FP叫非pure FP。那么其实在这些语言里面处理I/O的方式和java，C也没有多大区别了。而Haskell这种pure FP中永远是不允许对变量进行assignment的。在Haskell里面I/O被称为action而不是fuction,可以通过do关键字，实现类似java,c的I/O读写

main = do
s <- readFile "somefile"
putStrLn (show (f s););

当然haskell的牛人们就不会使用这种imperative的风格。他们会采用一种叫Monad的技巧将这种
imperative style转化到fuctional风格。

main =
readFile "somefile" >>= \s ->putStrLn (show (f s););

至于这Monad是什么？这里太小了，写不下。不过Ajoo是Monad高手，可以让他来登坛讲经。

至于Haskell，和Python那个好？我觉得关键是看解决什么样的问题，对于业务逻辑来说FP的比imperative更加强大,处理I/O人机交互这类的东西imperative更加自然。多一种手段，总能多解决一些问题。

至于Command模式的问题。FP最为强大的就是各种各样的Combinator和high order function，它能把很多不相关的逻辑粘合到一起。至于什么是combinator，我肚子饿了。等我回去吃完了告诉你。

关于referentially transprenty引用透明

我似乎记得
以前的导师讲到这个概念的时候也提到
正是由于很多语言缺乏引用透明性的机制
使得软件形式化中的逻辑证明很难实行

ok酒足饭饱,那么我来讲一下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
的莱布尼兹展开式。

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中最精彩的一笔，限于篇幅以及鉴于它让人抓狂的程度我是不准备介绍他们了。

Trustno1大哥,
上面这篇是你的原创么? 简单易懂, 比你最初转的那个狗屁翻译要强多了......

认认真真的读了一遍，真的有收获。

但是到算子空间的那部分看不懂了。等我想通了，再来提问题。

算子空间么。不用懂也没有问题，我说这个只是为了体现出FP在数学上的意义。
也就是说，数学表示上，f(x)的自变量不一定是初等数学那样是一个数的集合，也可以是一个函数的集合。

Haskell、Scheme、Erlang 和 Lisp在我读的大学里根本没有开设！
这是我们教育的悲哀！

Lisp，Schema无论如何都应该在大学开设，而且应该作为一门必修的重要基础课程来教授。
记得以前读书的时候老想到一个问题，就是数学中的多元函数怎么用C/C++实现，当一个简单的多元函数居然耗费C几百行代码（调试N>100次之后）之后，被一种不明白计算机语言能够给我们解决多少问题，怎么解决问题的模糊笼罩，连区区一个数学问题都不能解决，当时就大大打击了学计算机的热情。
现在想想，如果能够在当时就接触到这些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,我们可爱的多利羊是个克隆羊，他只有母亲没有父亲。如果我们为一只羊建立一个族谱，也就是说建立一颗二叉树 如下
        

                     Sheep
       mother              father
 mother father    mother father
 .................................

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

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[generation]==None:
        return child
    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语言来得更加清楚和方便。

Sigh原本想让大家体会一下Java的FP，没想到现在全部跑题到Python了。不过这也是没有办法的事情，Java那种丑陋的Functor实在让人吐阿吐阿，不过我估计写那文章的印度人也已经习惯了。