[PLT] 柯里化的前生今世(一):函数面面观

关于

本文作为开篇,介绍了出场人物,并形象化的引入了高阶函数,
得到了柯里化的概念。

后续文章,会介绍高阶函数的实现方式,词法作用域和闭包,参数化类型,类型上的柯里化,
敬请期待。
如有不同的认识,或者感兴趣的点,请直接联系我,欢迎指教。

人物介绍

球星库里

库里,Stephen Curry,1988年3月14日出生于美国俄亥俄州阿克伦(Akron, Ohio),
美国职业篮球运动员,司职控球后卫,效力于NBA金州勇士队。

斯蒂芬·库里2009年通过选秀进入NBA后一直效力于勇士队,新秀赛季入选最佳新秀第一阵容;
2014-15赛季随勇士队获得NBA总冠军;
两次当选常规赛MVP,两次入选最佳阵容第一阵容,三次入选全明星赛西部首发阵容。

Haskell Curry

这次我们说的不是NBA的库里,而是美国著名的数学家,逻辑学家Haskell Curry,它在组合子逻辑方面有杰出贡献。
Curry本科就读于哈佛大学医学专业,业余选修了数学,1917年转到了数学系。
毕业后,在通用电气找到了一份电气工程师工作,继续在麻省理工进修电气工程,但意识到自己更适合做理论研究,而非应用科学。
1922年转专业到了物理学,但物理学哈佛会更好些,于是作为助教回到了哈佛,1924年拿到了物理硕士学位。
随后,在哈佛攻读数学博士学位。

1924年,他最开始的研究方向是微分方程理论,与此同时他接触了一些逻辑学。
阅读了罗素和怀特海的《数学原理》之后,他产生了使用组合子来分析代换规则的设想。
于是,放弃了微分方程的研究,准备撰写一篇逻辑方面的博士论文。
1929年,他的第一篇论文《逻辑代换的分析》在《美国数学报》发表。

之后,Curry在宾夕法尼亚大学担任教员直至1966年退休,期间曾担任国家研究委员,普林斯顿的高级学会会员。
发表的论文包括,《组合子逻辑的全称量词》《组合子理论的补遗》《显式变量的组合逻辑观点》《组合逻辑中相等性及推导的几个性质》。
1942年,Curry作为符号逻辑学会会长,发表了离职演说《数理逻辑的组合子基础》。
Curry阐明了组合子逻辑与Chruch的lambda演算之间的密切联系,
建立了一套类似于Church和Rosser的完备系统。

第二次世界大战期间,Curry又开始研究应用数学,1943年发表了《Heaviside演算》。
1946年,Curry在应用物理实验室工作后,去了阿伯丁实验场,发布了《使用ENIAC的逆向插值法研究》和《使用ENIAC的四阶插值法研究》。

主要著作有,《组合逻辑》和《数理逻辑基础》。
注:这里说的这么仔细,是有原因的。组合子逻辑和lambda演算 ,我们多多少少也会提到。

柯里化

名字的由来

以下是维基百科关于Currying的定义:
In mathematics and computer science, currying is the technique of translating the evaluation of a function that takes multiple arguments (or a tuple of arguments) into evaluating a sequence of functions, each with a single argument.

Currying这个概念,首先是由Gottlob Frege引入的,以逻辑学家Haskell Curry命名。
虽然,这个概念是Moses Schönfinkel发明的。

表达式的值和类型

为了说明Currying我们先引入类型的概念。
我们知道编程语言中的表达式是有值的,我们常说,表达式的值为1,值为'a'
他们在内存中的存储方式是一样的,都是二进制方式。

但是,感觉上,他们应该是不同的东西,于是,我们用不同的类型加以区分。
我们称值1的类型是Int,整型,
'a'的类型是Char,字符型。

于是,我们就在值的概念上建立了一层抽象,不同的值因此有了不同的属性。
用数学语言来说,类型作为值集上的一种等价关系,诱导出了对该值集的一种划分,
相同类型的值构成了一个等价类。
注:我们后面将会看到函数类型的引入,让事情变得不是这么简单了。

函数面面观

函数用来将一个或多个值变成另一个值,函数也是一种值,它同样具有类型。
例如,加法函数add是把两个整型值变成一个整型值,假如我们已经定义好了add函数,我们可以这样调用它。

注:我们这里使用的编程语言,函数调用是不用加括号的,具有最高优先级。add 1 2类似于add(1,2)

add 1 2
= 3

现在我们考虑一个问题,如果我们只给add提供一个参数,结果是什么呢?
即,add 1是什么?

我们可以形象化的这样考虑,先考虑add
add就像一台有两个插槽的机器,
如果两个插槽分别提供了12,那么它会弹出结果3

问,如果只有一个插槽提供了1,那它是什么?
很显然,它还是一台机器,只不过只有一个插槽罢了。
因此,add 1还是一个函数,只不过它只接受一个参数罢了,
它返回参数值加1的结果,它的类型我们可以记为,

add 1 :: Int -> Int

我们再回过头来考虑add的类型,我们看到,
add接受1作为参数,返回add 1这个函数。
因此,我们对add就有另外一种看法了,
它是一台有一个插槽的机器,接受参数1后,
弹出的结果是另一台有一个插槽的机器add 1

因此add的类型我们可以记为,

add :: Int -> (Int -> Int)

为了书写方便,我们假定->具有右结合律,因此,

add :: Int -> Int -> Int

高阶函数

事实上,Currying指的是这样的一个高阶函数,

curry :: ((a, b) -> c) -> (a -> b -> c)

它把函数f变成函数g

f :: ((a, b) -> c)
g :: a -> b -> c

g = curry f
f = uncurry g

使得任意的x,y,满足,

f (x, y) = g x y

参考

柯里生平
Haskell Curry
Currying
Currying - HaskellWiki

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,602评论 6 481
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,442评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 152,878评论 0 344
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,306评论 1 279
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,330评论 5 373
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,071评论 1 285
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,382评论 3 400
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,006评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,512评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,965评论 2 325
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,094评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,732评论 4 323
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,283评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,286评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,512评论 1 262
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,536评论 2 354
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,828评论 2 345

推荐阅读更多精彩内容