论坛徽章:: 0

电梯直达

1楼 [收藏(0)] [报告]

发表于 2009-03-28 14:32 |只看该作者 |倒序浏览

转载自：
http://wiki.woodpecker.org.cn/moin/fp4python
还是全文整体转过来看比较舒服
(其中，修改了三四处错别字)

1. 前言
本文的写作计划源于2004年9月 GreyRoar 的提议, 可惜真正动手却推到了现在, 在近一年的时间里, python的函数编程也发生了一些改变, python3000计划和最近的已经出现的"匿名块"等都使得python在这个方面的发展充满着不确定因素, 本文只讨论目前已知的能用的功能, 不保证满足将来可能发生的变化. 另外在一切开始前, 记住Python和数学里一样记号只是记号.

2. 函数式编程的概念

函数编程源自 Lisp 等高阶语言, 他们以λ演算为基础. 所谓λ演算其实指基于算子λ的一个演算体系. 他的特殊性在于, 存在一个算子 λ (λ只是记号, 没有更多含义),他的作用是将运算式子变成函数 . 例如: λx: x+1 就将 x+1这个运算式子, 变成了关于x的一个函数, 他的值是x+1. 光有λ算子构成不了完整的λ运算体系, 还需要一些辅助算子, 但是λ演算体系的基础就是这个算子. 要完全了解这个体系则需要一环扣一环的定义和定理, 太复杂这里不再详述(书丢学校了, 回校有时间补齐

).

3. python中的函数编程

3.1. lambda

和数学中的 λ 一样, python的函数编程体系中有一个 lambda 语句, 用来生成函数, 一般这样的函数称为匿名函数.
例:

lambda x: x+1

复制代码

就生成了一个函数 λ(x) = x+1. 可以在python的解释器中试试:

>>> lambda x: x+1 # 生成一个匿名函数 λ(x) = x+1
<function <lambda> at 0x00C99770>
>>> f = lambda x: x+1 # 将这个函数绑定名字 'f'
>>> f(1) # 调用 'f'
2

复制代码

lambda的具体语法是: lambda [parameter_list]: expression
parameter_list 是参数表, expression 是后面跟的表达式,
lambda本身是个运算符, 作用在这两个元素上产生一个匿名函数, 类似于以下函数定义:

def name(parameter_list):
return expression

复制代码

expression 是一个合法的python表达式, 显然 expression 中的变量量除了在 parameter_list 中的外必须是已知的. 注意experssion中是不能用print语句的, 要想产生输出的话可以用sys.stdout.write()等函数.
(下面会不断给出 lambda 的例子 )

3.2. 高阶函数

所谓的高阶函数其实是一组以函数为参量的函数. 下面介绍 Python 中高阶函数的具体形式.

3.2.1. map

map是最基本的函数, 搞懂了map其他函数就很容易搞懂.
map( function, list, ...)
将函数function作用到 list 的每个元素上, 将结果组成一个列表返回. 如果参数列表有多个, 函数应该是有多参数的, 每个分量取各列表上的对应值, 如果有列表比其他列表短, 不足部分当作 None . 这里list可以是任意序列(sequence), 例如列表(list) , 元组(tuple)等.
例:

>>> a = range(5);
>>> b = range(4);
>>> map(lambda x, y: (x, y) , a, b) # lambda x,y 接受两个参数, 生成个包含这两个参数的tuple.
[(0, 0), (1, 1), (2, 2), (3, 3), (4, None)]

复制代码

另一种多参数调用的方法是组合列表(这也是我本人最喜欢用的方法):
map(lambda (arg1, ..., argn): expression, multiple_list)
multiple_list 是一个列表, 他的元素还是一个列表, 即参数列表. 这种方法实质还是单参数调用(这个不一定要完全理解).
例:

>>> ml = [[0, 1], [2, 3], [3, 4]]
>>> map(lambda (x,y): x+y , ml) # lambda (x,y): x+y 接受一个有两元元组(tuple), 计算他们的和.
[1, 5, 7]

复制代码

如果map 的第一个参数, 即function等于None, 则默认为恒等变换.
例:

>>> a = range(3)
>>> map(None , a)
[0, 1, 2]

复制代码

3.2.2. reduce

reduce( function, sequence[, initializer])

将函数function从左到右作用在序列的每个元素上, 函数function为二元函数, 第一个变量为上次计算所得结果,第二个变量为列表元素.
例:

>>> reduce(lambda x,y: x+y , [1,2,3,4,5]) # 相当于 ((((1+2)+3)+4)+5)
15

复制代码

整个计算过程就像列表在不断缩减一样.

initializer为初值.
例:

>>> reduce(lambda x,y: x+y , [1,2,3,4,5], 10) # 相当于(((((10+1)+2)+3)+4)+5)
25

复制代码

3.2.3. filter

filter( function, list)

从list的元素中构造一个列表, 这个列表的元素依次是list中使function为真的元素. list可以是任意序列, 如列表(List)和元组(Tuple)等, 或支出迭代子的容器, 或者迭代子(有关容器,迭代子等概念将在下面介绍,)

例:

>>> filter(lambda x: x>5 , [10,1,5,6,7]) # 将列表中小于5的元素滤去.
[10, 6, 7]

复制代码

和map一样, 若function是None , 则代为恒等函数, 这样将滤去所有取值为false的元素(包括0和None).

4. 列表运算

目前 Guido 对Python的函数式编程很不满意, 它计划在Python3000中去除这些函数, 取而代之的是列表运算. 这些方法在当前的Python版本中也是可用的.
基本形式是 [expression for expression_list in testlist ]
和前面一样 testlist 是一个序列或者迭代子,expression是一个表达式,expression_list 是这个表达式中的参量列表(实质上是解开一个元组).
例:

>>> [ x+y for x,y in [(1,2), (2,3), (4,5)]]
[3, 5, 9]
>>> [ item[0]+item[1] for item in [(1,2), (2,3), (4,5)]] # 和前面的等价
[3, 5, 9]

复制代码

for 语句可以套用:

>>> [ (i,j) for i in range(5) for j in range(3)] # 这个例子可以看出靠近expression的循环是内层循环
[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2), (3, 0), (3, 1), (3, 2),
(4, 0), (4, 1), (4, 2)]

复制代码

for后面还可以跟if语句, 这样相当于一个增强的 filter
例:

>>> [ i for i in range(10) if i%2==0] # 选出所有偶数
[0, 2, 4, 6, 8]

复制代码

同样 if 也可以嵌套, 并可以与for混合嵌套 (但是, 显然过多的嵌套容易使语句变得晦涩难懂) :

>>> [ (i,j) for i in range(10) if i%2==0 for j in range(10) if j%3 == 0]
[(0, 0), (0, 3), (0, 6), (0, 9), (2, 0), (2, 3), (2, 6), (2, 9), (4, 0), (4, 3), (4, 6), (4, 9),
(6, 0), (6, 3), (6, 6), (6, 9), (8, 0), (8, 3), (8, 6), (8, 9)]

复制代码

4.1. 基本方法综述

前面很粗浅得讲了一下Python中函数编程的最基本内容, 下面将列出一些常用的函数编程方法, 这些方法可以大大简化你的代码.

4.2. 应用实例

编程这东西如果理解原理, 不管用那种方法写程序其实都是一样的, 函数编程只是一种方法, 用好了可以简化程序.

4.2.1. 算24点的程序

这只是一个用了点函数编程方法随手写的程序, 1年前的东西, 不是算24点的最好方法, 拿到这里, 只是展示一下函数编程的用法.

funs = [ lambda x, item: (x+item[0],
                           str(x)+'+('+item[1]+')'
                           ),
   lambda x, item: (x-item[0],
                           str(x)+'-('+item[1]+')'
                           ),
   lambda x, item: (item[0]-x,
                           '('+item[1]+')-'+str(x)
                           ),
   lambda x, item: (x*item[0],
                           str(x)+'*('+item[1]+')'
                           ),
   lambda x, item: (item[0]==0 and (0,'ZZZ')) or
                     (x/item[0],
                           str(x)+'/('+item[1]+')'
                           ),
   lambda x, item: (x==0 and (0,'ZZZ')) or
                     (item[0]/x,
                           '('+item[1]+')/'+str(x)
                           )
]

def con(num):
l = len(num)
p = list()
if l==1: return {num[0]:str(num[0])}
for i in range(l):
      for f in funs:
         p += map(lambda item: f(num[i],item),
                     con(num[:i]+num[i+1:]).items()
                  )
return dict(p)

print con(map(float,[1,5,6,7])).get(21.0,0)

5. 函数编程的缺陷

函数编程最明显的缺陷是易用性不够, 对于大多数初学者来说, 函数编程是不容易理解的, 写出正确的函数式程序是有困难的.
同样,函数式编程的形式中含有很多的嵌套,这也使程序看起来很晦涩, 这正是 Guido 计划取消Python中函数式编程特性的原因之一.

[ 本帖最后由 izhier 于 2009-4-25 17:12 编辑 ]

评分

参与人数 1	可用积分 +5	收起理由
MMMIX	+ 5	精品文章

查看全部评分

文库|博客

izhier

稍有积蓄

论坛徽章:: 0

2楼 [报告]

发表于 2009-03-28 20:03 |只看该作者

我说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进行运算，然后把运算结果和第三个元素进行运算，以此类推。

[ 本帖最后由 izhier 于 2009-4-25 17:48 编辑 ]

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

izhier

稍有积蓄

论坛徽章:: 0

3楼 [报告]

发表于 2009-03-28 20:04 |只看该作者

例如

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去抽象这些算法要比原来的imperative语言来得更加清楚和方便。

[ 本帖最后由 izhier 于 2009-4-25 18:10 编辑 ]