范畴category:组合的本质

banq 14-11-07
              



之前我在分解和组合的抽象方法一文中谈了分解decomposition和组合composition具体特点,范畴理论大师Bartosz Milewski最近正好写了这篇Category: The Essence of Composition,从范畴角度挖掘了分解组合和树形结构以及构造定律的本质,并解释了函数编程FP的一些原理,如果你对这方面已经有所思考,让我们一起深入细节吧。下面是大概翻译。

一个范畴category 其实是一个非常简单的概念,一个范畴由多个对象和它们之间的箭头组成,这就是为什么范畴如此容易表达的原因,一个对象能用一个圆和一个点画出来,一个箭头就是一个箭头,如下图所示。

但是范畴的基本本质是组合,当然你也可以说,组合的本质是范畴,如果你有一个箭头从对象A到对象B,又有一个箭头从对象B指向对象C,那么这两个箭头的组合结果是,肯定有一个箭头从对象A指向对象C。

箭头作为函数
这就是抽象吗?可能你有点失望,让我们讲些核心的,想想箭头,也称为态射morphisms,它用来作为函数,如果你有一个函数f,其将类型A作为输入参数,返回输出的是类型B,如果还有另外一个函数g,它是将类型B作为输入参数,返回输出的是类型C,你就能通过将f的结果传给g组合它们,你也就定义了一个新的函数,它是将类型A作为输入参数,返回输出的是类型C。

在数学中,这样的组合是在函数之间使用小圆圈表达,如:g∘f,注意从右到左是组合的顺序,如果你还有写疑惑,如果你熟悉Unix/linux,其管道命令如下:

lsof | grep Chrome

或者F#中的>>,它们都是表达从左到右,但是在数学和Haskell函数组合中,组合是从右到左,你可以将 g∘f 读成, “g after f.”(g在f后面)

我们可以使用C代码来更明确表达,我们有一个函数f,它将类型A作为输入参数,返回输出的是类型B的值。

B f(A a);

另外一个函数:

C g(B b);

它们的组合是:

C g_after_f(A a)
{
return g(f(a));
}


这里你看到从右到左的组合: g(f(a)),这是在C语言中。

我很希望告诉你在C++标准库中有一个模板能够将两个函数组合在一起然后返回,但是没有,而在Haskell中,我们可以这样表达一个A到B的函数:
f :: A -> B

类似有:
g :: B -> C

它们的组合是:
g . f

一旦你看到Haskell如此简单表达函数组合,而C++如此无力,其实Haskell可以直接让你用Unicode字符表达组合如下:
g ∘ f

甚至可以使用双冒号和箭头表达如下:
f ∷ A → B

这是Haskell 的第一课,双冒号表达的是:有某个类型,一个函数的类型是使用在两个类型之间插入一个箭头来表达,你能这样通过一个句号点来表达两个函数的组合。


组合的特性

在范畴论中,组合必须满足两个特性:

1. 组合是关联的associative
(banq:组合是一种关系,如同金木水火土是一种组合关系一样),如果你有三个态射(箭头),比如f, g 和h,那就能够组合(它们的对象必须是端对端end-to-end,树叶?),你不必使用括号组合它们,数学符合表达成:
h∘(g∘f) = (h∘g)∘f = h∘g∘f

使用Haskell伪代码如下:


f :: A -> B
g :: B -> C
h :: C -> D
h . (g . f) == (h . g) . f == h . g . f


(伪代码的意思是等于号并不是为函数定义的)

关联性是在处理函数时相当显目,也许在其他范畴并没有如此明显。

2.对于每个对象A有一个箭头代表组合单元,这个箭头是从对象循环指向自己,那就意味着是一个组合的基本单元,从A开始在A自身终结的箭头,相应地其返回同样的箭头,对象A的箭头单元称为idA (banq注:由于字符原因,后面的A要矮一半),这表达A的标识identity ,在数学符号中如果f是从A到B,那么:
f∘idA = f

idB∘f = f

当处理函数时,标识箭头被实现为标识函数,该函数返回的是自己的输入参数,这个实现对于每个类型都是相同的,那就意味这个函数是通用的多态性。在C++我们能将其作为一个模板定义:
template<class T> T id(T x) { return x; }

当然,在C++中没有这么简单,因为你不只是传递它,而且还要涉及如何传递,是按引用传递 按值传递 等等。

在Haskell中,标识函数是标准库的一部分,称为Prelude,下面是它的定义表达:
id :: a -> a
id x = x

正如你看到,在Haskell多态函数是出奇简单,你只需要使用一个类型变量替代类型,核心类型的名称总是以大写字母开始,类型变量的名称总是以小写字母开始,这里a代表所有类型。

Haskell函数定义是由函数的名称,后面跟着一个形式参数,这里只有一个x,函数体跟在等号后面,这种简洁常常初学者震惊,但你很快就会看到它意义非凡,函数定义和函数调用是函数编程中的面包和黄油,这样它们的语法是需要简单到最小,不仅没有包围参数的括号,参数之间也没有逗号间隔开。

函数体总是一个表达式,在函数中没有任何statements,函数的结果也是一个表达式,这里只是x。

这是Haskell的第二课。

标识情况能用伪Haskell代码写如下:
f . id == f
id . f == f

这里你也许会有一个问题,为什么人们总是要用到标识函数,一个什么都不做的函数?那么,为什么人们使用数字零呢?零是代表什么也没有,古罗马的数字系统是没有零的,他们能够建立很棒的道路和渡槽,一些保留至今。

自然数字零或id实际非常有用,这是当它们使用在符号变量中时,那就是为什么罗马人不擅长代数的原因,相反,阿拉伯人和波斯人擅长,他们非常熟悉零的概念,一个标识函数可以非常便利地作为参数或返回参数,或一个高阶函数,高阶函数其实就是函数可能的符号实现,它们是函数的代数。

总结一下,一个范畴是由对象和箭头组成,箭头能够组合 组合是关联的,每个对象都有一个标识箭头,作为组合的基本单元使用。

组合是编程的本质
(banq:下面关于组合的意义干货来了)

函数编程者们有一个奇特的目标性问题,他们总是询问类似零的问题, 实际中,当我们设计一个交互程序,他们会问:什么是交互?什么时候实现Conway的人生游戏?他们可能会思考人生的意义,以这种范式,我会问什么是编程?最基本概念,编程是告诉电脑做什么. 将内存地址的x的内容加入到寄存器EAX的内容,但是当我们汇编编程时,我们发给计算机的指令是有意义的表达式,我们解决了一个不平凡的问题(如果平凡我们就不需要计算机帮助了),那么我们是怎么解决问题?

我们分解大的问题为小的问题,如果小的问题还是很大,我们继续分解它,最后我们编写代码来解决这些分解后的小问题,那么编程的本质就来了:我们是组合这些代码片段来为一个大问题创建解决方案。如果我们不能将那些碎片代码组合起来,分解就没有必要 (banq注:如果拆了不能装起来,拆就是破坏了)

分解和组合的并不影响电脑,但是它受限于人的智力,我们的大脑在某个时间只能处理一些概念,最常见的心理学论文之一:The Magical Number Seven, Plus or Minus Two指出我们只能保持 7 ± 2 个信息片段,我们对人类短期记忆的理解已经改变,但是我们确认它是有限的,底线是我们不能处理一锅汤一样的代码,我们需要结构不是因为良好结构的代码看上去让人高兴,而是因为我们的大脑不能有效处理(非结构的数据),我们经常描述一段代码如何优雅和美丽,但是我们真实意思是它们容易被人类智力处理,优雅代码代表的数量正好符合我们大脑处理大小,符合我们精神系统能够消化的食物量大小。

那么程序组合的数量是多少正好呢?表面数量总是小于它们的体积(几何学中表面积的增长总是慢于体积的增长),表面积是我们需要组合的信息片段,而体积是我们需要实现的信息,一旦一段信息被实现,我们就会忘记实现细节,而关注它是如何和其他片段交互上 (banq注:符合老子道德经中的无以为用),在面向对象编程中,表面是对象的类,或它的抽象接口,在函数编程中,它是函数的声明。

范畴理论总是鼓励我们从对象内部细节中转移开来(banq注:我之前帖子中的一张桌子理论,无才能用),在范畴理论中一个对象是一个抽象模糊的实体,你所有需要知道的只是它如何和其他对象交互(关系),它是怎么使用箭头和其他对象连接的,这就是为什么互联网搜索引擎(Google)能够通过分析有多少其他网站链接指向你的这个网站,根据这些链入和链出的链接数量对你的网站进行排名(PageRank)。

在面向对象编程中,一个理想化的对象不仅是通过其抽象接口可见的(纯表面,无体积),还有对象的方法method,因为方法代表箭头(如果方法里调用其他对象会产生对其他对象的依赖,箭头代表对象之间的组合关系),这一刻你得进入对象的内部才能搞清楚它和其他对象如何组合,但是你就失去了编程的优点。


[该贴被admin于2014-11-08 08:57修改过]

              

4
banq
2014-11-07 13:02

是否可以这么总结:

面向对象属于分解,函数编程属于组合。

有以为利,通过面向对象我们将一分解为多个,数量多了,“有”,而函数编程则是将多个组合成一个,数量少了,“无”,无才能用,只有忽略事物内部的细节,我们才能用它,否则陷入细节迷失方向。换句话说:数学分数考得好,不代表在实际中用数学用的好,牛顿没有发明几何学,但是用了几何学,创造了微积分,用它们推导出万有引力;爱因斯坦用了非几何学推导了相对论。

学习是一种分解能力,使用是一种组合能力,这是两种不同的能力。

再看看老子道德经的一段:三十幅共一毂,当其无,有车之用。埏埴以为器,当其无,有器之用。凿户牖以为室,当其无,有室之用。故有之以为利,无之以为用。

这段话意思是:三十根棍子做成的圆轱辘,只有忽视圆轱辘内部这种结构,着眼于圆轱辘外部,才会发现它原来是可以做车的轮子这一用处,两个轱辘与车架组合成一辆车。比如门窗,只有忽视其内部如何结构的构建,才会从外部想到用它在房间组合中。

我们分解大的问题为小的问题,如果小的问题还是很大,我们继续分解它,最后我们编写代码来解决这些分解后的小问题,我们组合这些片段来为了解决一个大问题。如果我们不能将那些碎片代码组合起来,分解就没有必要。如果拆了不能装起来,拆就是破坏了。

分解和组合的并不影响电脑,但是它受限于人的智力,我们的只能某个时间只能处理一些概念,最常见的心理学论文之一:The Magical Number Seven, Plus or Minus Two指出我们只能保持 7 ± 2 个信息片段,我们对人类短期记忆的理解已经改变,但是我们确认它是有限的,我们需要结构不是因为良好结构的代码看上去让人高兴,而是因为我们的大脑不能有效处理(大量数据),我们之所以使用树形结构,用一个根节点代表其聚合群体,用组长代表所有组员,用名字代表人的全部,等等这些组合抽象的办法就是让我们大脑去除大量对象内部的细节,用一个符号代替它们,这样我们才能基于这个树的根节点再组合成新的树形结构。

魔鬼出现在细节中,细节做不好整个事情会失败,但是细节做得太好,会让你沉湎于细节,无法宏观(组合成更大事物)。再打个比喻,我们使用名字代表一个人,但是如果你和这个人非常熟悉,感性感情无法让你用一个名字替代他,提到他的名字你会动容有感情,在这种情况下,对象内部大量细节占据了你的大脑,已经无法使得你理智地进行组合思考。

范畴理论总是鼓励我们从对象内部细节中转移开来,在范畴理论中一个对象是一个抽象模糊的实体,你所有需要知道的只是它如何和其他对象交互(关系),它是怎么使用箭头和其他对象连接的,这就是为什么互联网搜索引擎Google Baidu等能够通过分析链入和链出的链接来排名网站一样。

范畴英文是Category,也是分类的意思,打个比喻,Google能根据哪些网站引用你的网站这个外部信息进行PageRank评分,从而对你的网站权重进行排序,这个道理和我们评价一个人有些类似,看一个不认识的人怎么样,那就看看他交往的什么朋友,什么环境,近墨者黑,人以群分,物以类聚,这些都是从事物所在的分类类别中判断其价值,而不是从事物内部细节。

以一张桌子为案例,分解思维的人看到后首先想到这张桌子由什么构成,长宽高和材质,这些都是桌子的内部细节;而组合思维的人看到后,环顾四周,看看其处于什么环境,如果放在教室中,他判断这是一张课桌,如果放在食堂,他判断这是一张饭桌。

所以,只有忘记对象的细节才能用好它,两个原因总结一下:首先,首先人脑短时记忆有限,如果大量对象内部细节占据大脑,而我们需要从对象外部组合它们,这些细节是干扰。其次,范畴也认为组合对象只要将对象看成模糊实体,注重它们之间关系。

忘记学习对象的细节才能用好它,无以为用,事物的制造者都不一定能用好它,除非事先有目标制造它,因此,学并不能致用,数理化学得好不一定用得好,博士给老板打工,老板赚大头。因为他把你的学问用处发挥了。自己学自己用因为智力限制也不可能。

这也解释了学生阶段中国学生数理化很好,但是毕业后诺贝尔奖获得者几乎没有,世界自然科学领军人物很少,那些高考状元 学神都哪儿去了?学得好不一定用得好,中国教育制度是以学习能力评价学生,各种考试充斥大量 知识细节,让学生耗费18年于这些可能以后无用的细节中,最终他们已经没有智力空间来思考如何使用这些大量的知识细节了。中国教育制度存在严重的本质错误。

当然,归根到底,还是“无以为用”这个范畴的组合本质很多人都没有搞清楚。

[该贴被banq于2014-11-08 08:36修改过]
[该贴被banq于2014-11-08 08:52修改过]

SpeedVan
2015-05-01 09:46

这篇文章一语中的。
面向对象具有分解能力,但其逻辑组合能力实在是弱,而且其代码表达能力极其容易分散程序员对逻辑的关注力(我认为对于语言来说,这是严重问题。指令式没有定义指令与指令的关系,使得语言上组合能力严重缺乏,而函数却天生具有组合能力)。

代码应该直接体现逻辑组合过程,才能使程序员关注该关注的东西。具备这样能力的,除了函数式和逻辑式,我看不到更多了。

luda
2015-05-01 11:00

2014-11-07 13:02 "@banq"的内容
以一张桌子为案例,分解思维的人看到后首先想到这张桌子由什么构成,长宽高和材质,这些都是桌子的内部细节;而组合思维的人看到后,环顾四周,看看其处于什么环境,如果放在教室中,他判断这是一张课桌,如果放在食堂,他判断这是一张饭桌。 ...

同意。从这个例子可以看出组合是从行为(运动、变化、时间)角度看待世界的,“课桌”、“饭桌”中的“课”和“饭”在这里是动词,意为“上课用”、“吃饭用”的意思,“用”是动词,同一个桌子出现在不同的环境中发挥不同的作用。而分解思维只研究空间,只研究桌子的空间结构是什么,甚至不研究为什么是四条腿,为什么每条腿长度相同,分解思维根本不考虑这些,不用考虑任何桌子之外的世界,在分解思维中没有万有引力、没有地面的水平、没有书房和餐厅,只有空间,分解只考虑空间的组成结构。看来分解和组合是相互依存的,分解时研究的是空间,组合时研究的是行为,把桌子放进餐厅的意义是期待使用它吃饭这样一种运动。
[该贴被luda于2015-05-01 11:16修改过]

luda
2015-05-01 11:13

2015-05-01 09:46 "@SpeedVan"的内容
面向对象具有分解能力,但其逻辑组合能力实在是弱,而且其代码表达能力极其容易分散程序员对逻辑的关注力(我认为对于语言来说,这是严重问题。 ...

面向对象既关注空间又关注运动,面向对象这种方法有利于堆放出一个在空间结构上良好的东西,这样的东西有空间形状,对右脑友好,据说右脑是我们的本能脑,良好堆放的空间有利于我们使用更加高效的本能计算(左脑的计算太耗时间);函数是运动,是个过程,但是函数得在系统中找个地方依附,得把函数挂在系统树的什么地方这样我们才能索引到它使用它,面向对象是把函数挂在了分门别类的对象模板上去了,这种挂在对象模板上的函数被称作方法,方法的第一个入参是this指向的对象。
系统是有限的,只有一个系统是无限的,宇宙系统是无限的。函数式倾向于把函数挂在系统根上,挂在根上的函数可以作用于根节点下的所有子节点,如果我们在根节点上挂成百上千的函数的话这给人的感觉是整个世界没有被良好的分类过很凌乱,越往根上靠近世界越抽象,如果要在根上良好的挂函数的话应该不会挂出成百上前的函数,很可能只能挂一个或者两个函数,从而整个系统内的所有运动都通过这一两个函数的组合来表现,这样就太繁琐了。每一个系统都有父系统,如果一直网上追求根的话就到了宇宙根节点了,宇宙根节点很可能是“无”,而“无”挂不了东西。
[该贴被luda于2015-05-01 11:24修改过]

4Go 1 2 3 4 下一页