如何理解functional programming里的currying与partial application?

在F#里,各种函数的signature 都是 int -> int -> int ->什么的…… what does that even mean?? Currying和partial application对于functional programming有怎样的真正的威力? currying和partial application会affect performance吗?
关注者
145
被浏览
11856
为什么我们需要(or不需要)科里化

我们见过的多参函数

多参函数似乎是个很无聊的话题,定义或者调用一个多参函数这事儿是每个学习编程的人最先学会的几件事之一。大家使用起多参函数来,似乎是那么的自然,那么的理所应当,甚至大家还在这上面玩出了各种花样,比如什么不定长参数啦,什么具名参数啦,总之各个语言都有自己的一套,大家都各自玩得很high。

好吧,不废话,先揪几个小喽啰出来让大家指认一下:


这是一个典型的C语言里的多参函数

int plus(int a, int b) {
    return a + b;
}

这是以上函数的Python版本

def plus(a, b):
    return a + b

python君觉得仅仅是这样当然还不够帅气,所以又加了不定长参数的功能

def sum(*arr):
    return foldl(plus, 0, arr)

于是你就可以这样调用这个sum函数了:

print sum(1, 2)
print sum(1, 2, 3)

(台下有同学一脸迷茫:"foldl"是神马?好吧,你可以先无视它,我仅仅是想偷个懒少写个for而已。。


当然了,仅仅这样是不足以体现python君的帅(zi)气(lian)的,于是又有了这样的东西

def sum(*arr, **opts):
    plus = (lambda a, b: (a + b) % opts.get('mod', 1024))
    return foldl(plus , opts.get('init', 0), arr)

然后用的时候是这样子

print sum(1, 2)
print sum(1, 2, init = 100, mod = 3)

当然了,除此之外,python君还允许参数有默认值,以及各种传参方式可以混合使用等等,我就不一一举例了。


多参带来的不便

乍一看,Python君用起来好方便,参数想怎么传就怎么传,多happy。但是事实是,这种做法,在你需要做一些高阶抽象的时候,就会带来无尽的麻烦了。

比如,我想定义一个叫作echo_param的函数,它接受一个函数f作为参数,返回一个稍加修饰后的f2,f2跟f做一样的事情,区别仅仅是f2会将其接收的参数先打印出来。


如果仅仅考虑f是单参函数的情况,我们可以这样实现echo_param:

def echo_param(f):
    def f2(x):
        print "param:", x
        return f(x)
    return f2

然后你可以这样用这个echo_param来帮助你调试代码:

inc = (lambda x: x + 1)
inc = echo_param inc
print 'returns:', inc(1)
# param: 1
# returns: 2

然而,当你希望你的echo_param函数可以用在任何函数上的时候,你就会发现麻烦来了,为了适应各种传参方式,你的代码得写成这样:

def echo_param(f):
    def f2(*a, **d):
        print "param:", a, d
        return f(*a, **d)
    return f2

于是,你在写很多高阶函数的时候,你都得考虑你的 参数函数f 在面临各种传参方式的情况下要怎么处理,这事儿是痛苦并且容易忘记的,因为你本不应该关心f的参数是些啥的! 类似情况的例子还有memoize等等。 同样的,如果你想把一个函数和函数的参数(这些信息描述了一个调用过程)记录下来,然后在合适的时间再去调用(如threading.Thread),那么你也会遇到“函数的参数难以表达”这个问题。


盲目地引入传递多参的机制,其实是没有把问题想明白的表现。


元组和列表

元组和列表在我看来是最自然和最容易理解的两种组合基本元素的方式。 元组表达的是固定数量的不同类别(这里指“不一定同类别“)的值的组合,而列表则表达了不定数量的多个同类的值的罗列。比如("张三", 123)是一个元组,而[123, 456, 789]是一个列表。

有了元组和列表,我们能很容易地表达任何一种复杂数据。现在让我们想象一下这样一门语言,我们暂时称之为QP(”奇葩“)语言,这门语言的设计者忘记了有“多参函数”这种需求,不过他恰好实现了元组和列表,可现在我们需要在QP语言里定义plus这个“二元函数”和sum这个“?元函数”,我们该怎么办呢?


好吧,为了防止台下的观众因为抢答太过激烈引发安全事故,我就直接贴出答案了:

plus (a, b) = a + b
sum xs = foldl (+) 0 xs

然后你可以在QP语言里这样调用它们

u = plus (1, 2)
v = sum [1, 2, 3]

于是聪明的你瞬间惊奇地发现:之前的猫猫狗狗语言里定义的各种传参方式完全是多余的! 事实上,我们需要的仅仅是表达复合数据类型的能力,以及单参函数,这些就已经完全足够了,再复杂的参数也能通过两种组合方式来构造:要么就是不同类型的事物的有限组合,要么就是同一类型的多个事物的罗列。

至于怎么实现“具名参数”和“带默认值的参数”,就留作思考题吧。


函数作为一等公民,以及“科里化”

不同与猫猫狗狗语言的设计者们(他们在多年后才意识到函数是大大的良民不该被歧视),QP语言在一开始就十分欢迎函数这种外星生物的到来,并且把它们当做一等公民,享有和Int,String,元组,列表等原住民一样的进出各类公共场所的权利。


函数这种外星生物在QP语言里长这样(下面是四个这类生物的标本):

\x -> x + 1
\(x, y) -> x + y
\f -> f 1
\f -> (\x -> f x)

因为Int,String,元组,列表们都可以以“函数参数”的身份进入某个函数,或者以“函数返回值”的身份走出某个函数,所以函数作为一等公民也就自然的拥有这些权利,比如以上生物标本中的第三个,就是一个以另一个函数f为参数的函数;而标本中的第四个,不仅参数是个函数,且返回值也是一个函数。嗯,不要觉得奇怪,函数们只是肤色暗一点而已,它们被允许做这些是理所应当的。

当函数被允许返回另一个函数后,QP语言里就会发生一些更有意思的事情了。比如,你可以这样来重新定义plus了:

plus = \x -> (\y -> x + y)

然后你可以这样用这个plus函数:

r = (plus 1) 2

嗯,这很好理解,既然(plus 1)的值是个函数(它是(\y -> 1 + y)),那么(plus 1) 2就相当于(\y -> 1 + y) 2,也就相当于1 + 2,即是3了。

我们通过这样辗转的方式,同样定义了一个“二元函数”。这种利用函数的一等公民身份委婉地定义多元函数的方式,通常被称作“科里化”(curry)

嗯,先不说这么定义多元函数好不好。既然你接纳“函数是一等公民”这个事情了,那么它们做出这样违背伦常的事情也是不可避免的了。


为什么我们需要科里化

科里化这种现象是随着函数被当做一等公民自然而然地产生的,原本与我们需要或不需要无关。但既然这样的自然现象存在了,那么我们当然可以考虑一下这现象有什么可以利用的地方。

先来举个栗子,比如我们现在需要一个all函数,这个函数用来判断一个列表里的所有元素,是否都满足某一给定条件。它应该是接受一个judge函数和一个列表,然后返回一个bool值。我们当然可以这样来定义它:

all = \(judge, xs) -> if xs == [] then true else ((judge (head xs)) and all (judge, (tail xs)))
flag = all ((\x -> x > 0), [1, 2, 3])

但是,如果现在的情况是,我需要判断一系列的列表分别是否“合法”(即列表的每个元素都使judge返回True),那么我得这样写:

flag1 = all ((\x -> x > 0), [1, 2, 3])
flag2 = all ((\x -> x > 0), [4, 5])
flag3 = all ((\x -> x > 0), [6, 7, 8, 9])

当然,把judge函数写这么多遍太二了,所以大家一般会写成这样:

judge = (\x -> x > 0)
flag1 = all (judge, [1, 2, 3])
flag2 = all (judge, [4, 5])
flag3 = all (judge, [6, 7, 8, 9])

事实上,你会发现以上的代码仍然有all (judge, XXX)这样的公共模式,于是聪明的你当然会这样写:

judge = (\x -> x > 0)
judge_list = (\xs -> all (judge, xs))
flag1 = judge_list [1, 2, 3]
flag2 = judge_list [4, 5]
flag3 = judge_list [6, 7, 8, 9]

甚至,聪明的你连judge_list这个名字也不想重复这么多遍

judge = (\x -> x > 0)
judge_list = (\xs -> all (judge, xs))
[flag1, flag2, flag3] = (map judge_list) [[1, 2, 3], [4, 5], [6, 7, 8, 9]]

这里,从发现all (judge, XXX)这样的公共模式,到judge_list这个函数,我们所做的事情是“抽象”,即把一个以XXX为模板变量的公共模式,抽象成一个以x为自变量的函数。我们发现,通过合适的抽象,我们总是能得到我们想要的东西。不过,有没有更方便一点点的方式呢?

如果我们考虑通过“科里化”的方式来处理all函数的两个参数,那么all的定义就是这样:

all = \judge -> (\xs -> ...)
flag = (all (\x -> x > 0)) [1, 2, 3]

这样一来,当我们需要judge_list函数的时候,我们可以通过“函数应用”来得到,而不再需要做“抽象”了:

judge_list = all (\x -> x > 0)
[flag1, flag2, flag3] = (map judge_list) [[1, 2, 3], [4, 5], [6, 7, 8, 9]]

嗯,这样当然会让事情简单一些,并且由于可以方便地“部分应用”函数(毕竟“抽象”还是相对麻烦一点点),我们可以不用取很多临时的名字啦(毕竟你看,通过“部分应用”得到的all (\x -> x > 0)并不比它的名字judge_list长很多对吧):

[flag1, flag2, flag3] = (map (all (\x -> x > 0))) [[1, 2, 3], [4, 5], [6, 7, 8, 9]]

这样一来,我们的代码似乎帅气了很多对吧


为什么我们不需要科里化

其实,构造这个judge_list函数,是基于一种叫做Point-free的想法。Point-free就是说,你定义的东西(如函数),应该可以独立的存在,并且具有完整的语义,而与应用到的具体目标无关。在以上的演示中,我们已经看到,Point-free的想法,是避免重复的有效手段。

当然了,只要做到了Point-free,不管用不用“科里化”这种方式,我们都可以有效地避免重复,科里化的意义,仅仅是某些时候可以让事情方便那么一点点。


然而,在“方便一点点”之余,科里化的风格的大量应用还会带来一些别的副作用,让我们对比一下用元组参数风格和科里化参数风格定义的两个all函数在实际使用的时候会让你的代码变成什么样子:

judge = (\x -> x > 0)
judge_list = (\xs -> all (judge, xs))
[flag1, flag2, flag3] = (map judge_list) [[1, 2, 3], [4, 5], [6, 7, 8, 9]]
[flag1, flag2, flag3] = (map (all (\x -> x > 0))) [[1, 2, 3], [4, 5], [6, 7, 8, 9]]

前者是元组风格的多参,后者是科里化风格的多参,我们很容易发现,当我们只有元组形式的多参函数可以用的时候,我们更倾向于定义一些中间步骤来做适当的抽象,然后再将这些中间步骤组合起来。而当我们大量使用科里化风格的时候,我们则倾向于省略这些中间步骤,毕竟给这些中间步骤取个名字的话,名字的长度不会比组合这些函数来得简短。 请注意,我在这里讨论的是“倾向”,不是必然。很多人会说,即使用科里化,也可以给中间步骤取些名字,这不假,但大量使用科里化,会让人倾向于写出例子中的代码,却是事实。


值得注意的是,这种不同,会给代码的可读性带来非常微妙的影响,我们发现,由于缺少必要的中间步骤,科里化风格常常倾向于让人写出包含过多细节的代码,而不太愿意适时地给出一些中间步骤。


事实上,如何在构建程序的过程中,保持一个合适的抽象粒度,这本身就是一个很有意思的话题。我会在一篇单独的博文里详细地聊一聊这件事。


三种传递多参数的方式比较

语法层面支持的多参函数定义是一种扁平、简单、有效的方式,但是,当程序需要做高阶函数抽象的时候,这种方式会带来麻烦。


通过组合型数据来传递复杂参数,是一种很自然的方式,这种情况下并不需要刻意考虑“多参函数”这种问题,并且这种方式对于做高阶函数抽象非常友好。


科里化的方式定义多参函数,同样是一种自然产生的方式,只要把函数当做一等公民,就会存在科里化的方式。科里化的方式使得我们的函数可以更细粒度地方便地组合。


这么看来,如果要设计一门函数式语言,仅支持后两者是自然且明智的选择。然而,大多数流行的语言(包括流行的lisp家族语言)却都选择了包含第一种方式的多参——即支持多参语法,从我目前的分析来看,这真的不是一个好的选择。事实上,在同时存在三种传递多参的方式的时候,定义一个多参函数时,选择传参的方式都是一件令人头疼的事情。


如何选择

当你需要定义一个多参函数的时候,你会把它定义成什么样子呢?

在支持多参函数语法的语言里,把它定义成“接受一个组合型参数的函数”或是定义成“多参函数”通常仅仅是出于美观和习惯上的考虑。虽然我个人是更倾向于用组合型参数的方式的,但是很多时候这么做并不符合该语言的用户习惯,而有些语言甚至就没有提供方便的组合数据的方式。

但是,是否要使用科里化的方式,却是一件需要细细揣摩的事情。比如,我要定义一个rotate函数,它接受一个二维向量的坐标,返回一个逆时针旋转九十度后的向量坐标,那么你可能会把它定义成

rotate = (\x -> (\y -> (y, -x)))

或者

rotate = (\(x, y) -> (y, -x))

你觉得哪种定义方式比较好呢? 在这个例子里,显然是第二种定义方式比较好,一来,二维向量的两个坐标通常是成对出现的,很少会有“部分应用”的需要,所以也就自然用不到科里化的任何好处;二来,当你需要把一个向量rotate两次的时候,科里化版本就会体现出异常的麻烦了。

所以,我的结论是:

  1. 如果某些参数在大部分情况下,总是需要同时给出,才具有真实的意义,那么应该把这些参数组合成一个组合型参数来处理,而不应该科里化。
  2. 如果要定义的多参函数是一个闭合函数,那么它是很可能需要被多次应用的,这种情况下,应该用组合型参数的方式来处理。
  3. 如果先指定某一些参数就有明确的意义,那么就应该用科里化的方式来处理。

以上内容copy自我自己的blog:为什么我们需要(or不需要)科里化——关于三种定义多参函数的风格的讨论