Haskell的类型类提供了高于具体类型的抽象。为了更好地理解抽象类型,有必要抽象出一些概念以方便表达和理解,这是范畴学研究的一个主要目的。本节就来简单介绍下范畴论,然后使用范畴论的一些概念,来帮助我们更好地去理解函子。

在集合论中,集合(set)代表了是一个含有某些共同性质的类型的集体,例如整数的集合、有理数的集合和字符串的集合等,这些集合与Haskell程序中对应的概念就是具体的类型,例如Int和String等。但是相比集合本身的性质,我们有时更想了解集合和集合的关系,于是就定义了映射,也就是Haskell中的函数。函数可以把一个集合里的元素映射到另一个集合中,而现在我们想要了解这些映射还有没有更加有趣的性质。

于是定义了一个概念,叫作范畴(category)。在范畴中,每个组成元素叫作物体(object),它可能是类型,也可能只是一个值,或者是其他的范畴。我们没有规定物体一定要像集合那样满足某些性质,但是要求在范畴中能够定义出物体和物体之间的关系,两个物体之间可能有关系,也可能没关系,我们把存在的关系叫作态射。态射不一定是函数,例如对于一个含有"a"、"abc"和"abcd"的范畴,可以规定短于是一个态射,那么"a"和"abc"之间存在这种态射,而"abcd"和"abc"之间不存在。现在试着用图11-1表示一下这个范畴。

enter image description here

范畴1中的箭头代表短于这个态射。态射在图中是一个单向的箭头,从源物体(source)指向目标物体(target)。实际上,在范畴学中,想要让图11-1成为一个范畴,还必须定义一个很重要的规则,那就是如何组合两个态射。在上面的这个范畴中,我们定义规则:如果x短于y,而且y短于z,则x短于z,这样就定义出了这个只有三个物体的范畴。

我们试着用规范化的数学语言细化并明确范畴的定义。

一个范畴C,应该由如下3个要素组成。

 一个集合类ob(C),其元素被称为物体。

 一个集合类hom(C),其元素被称为态射。每个态射f都只有一个源物体a及一个目标物体b(其中a和b都在ob(C) 内),态射f被称为从a至b的态射,记作f : a → b。

 一个二元运算,被称为态射组合,该组合使得对于任意3个物体a、b及c,都有hom(b, c) × hom(a, b) → hom(a, c)。两个态射f: a → b及g: b → c的组合写作g ∘f ,并符合下列两个公理。

 结合律(associativity):若f: a → b、g: b → c及h: c → d,則h ∘(g ∘f) = (h ∘ g) ∘f。

 单位律(identity):对于任意物体x,总存在一个态射idx: x → x(x的单位态射),使得对于每个态射f: a → b,都会有idb ∘f = f = f ∘ida。

其中,集合类(class)这个概念是指满足某一类特点的不含糊的集合。不含糊这个概念其实是为了避免罗素悖论,下面的定义就是一个非常含糊的集合:

包含所有集合的集合。

这个集合应不应该包含自身呢?如果它不包含自身,显然不符合定义,而如果它包含了自身,那么它发生了改变,产生的新的集合是不是也应该被包含呢?这么一直重复下去,我们永远无法给出一个严格的定义,所以我们说这是一个含糊的集合。

就像上面的集合类ob(C)和hom(C),暂时先理解成集合就好:对于一个范畴,所有的物体构成了集合ob(C),所有态射构成了集合hom(C)。

看来对于刚刚的范畴,我们需要补充一个每个元素到自身的态射,才能满足严格的数学定义。一种方式是,我们规定每个元素都短于它自身,这样每个元素就拥有了到自身的态射,这符合上面的所有要求。另一种方式是,再定义出一个更符合直觉的态射,叫作不长于,并规定出不长于和短于这两种态射是如何组合的。你可以验证下这个单位态射是否满足数学上idb ∘ f = f = f ∘ ida的要求,最后会得到图11-2。

除了有不同物体之间的态射之外,我们还有每个物体自身到自身的态射,而且只要从a到b和从b到c有态射,从a到c也一定有态射,于是我们成功地定义出了一个范畴。实际上,在范畴学中,我们把具有大小秩序的范畴叫作有序类,其中只有一种秩序的(例如短于)叫作偏序类,而包含相反秩序的叫作全序类,这些范畴之所以成为范畴,也都是要满足某些关系的。

enter image description here

你可能会想,什么情况不算是范畴。我们随意举个例子,对于一个三人小组——小明、小红和小丽,假设现在定义态射是暗恋关系,那么可能会有图11-3所示的关系。

enter image description here

图11-3之所以不是范畴,是因为存在两个问题:一是暗恋关系没有对应的合成方法,小丽暗恋小明,小明暗恋小红,但这不足以说明小丽和小红的关系,他们可能甚至彼此不认识,二是每个物体没有到自身的映射。

当然,让上面的小组成为范畴也很简单,你需要补充每个物体到自己的一个关系,例如每个人都讨厌自己,同时新增暗恋关系的组合规则。例如,如果A暗恋B,B暗恋C,则A讨厌C。这个看似非常无聊的例子实际上在暗示范畴的本质,范畴是对物体和物体之间对应关系的描述。我们引入“范畴”这个概念,是因为在程序中,数据和函数构成了各种各样的范畴,这些范畴很多时候都很模糊,而我们必须通过这些看似模糊的范畴和他们满足的一些直觉上容易理解的性质,推导出一些直觉上不那么容易理解的性质。这是抽象的力量。

现在考虑在Haskell中的情况,Haskell中的所有类型可以构成一个巨大的范畴Hask。Hask里的物体是一个个类型或者小的范畴,不同物体之间的态射就是它们的函数,而态射组合的规则是通过组合函数(.)定义的,示例图如图11-4所示。

enter image description here

而对于上面说的函子类型类,我们说函子可以把一个Hask中的范畴C态射成另外一个范畴D,这个函子我们记作:F: C → D。例如,对于列表函子和一个我们任选的范畴C:

enter image description here

列表函子把范畴C态射成了范畴D,这里它做的事情有两件。

 把ob(C)映射成ob(D),即把范畴C中的每一个物体x映射成范畴D中对应的物体F(x),即一个物体的列表。

 把hom(C)映射成hom(D),即把范畴C中每两个物体间的态射f映射成范畴D中对应的态射F(f),例如从sqrt映射到fmap sqrt。

我们注意到fmap id在范畴D中出现在了id的位置。实际上,我们遇到了函子在范畴学上的第一个约束——单位律,在这个约束中,F: C → D必须要把范畴C中的id映射到范畴D中的id。

紧接着,根据范畴学的定义,如果物体A到物体B,物体B到物体C之间都有态射的话,物体A到物体C之间也一定存在态射。可以看出,在范畴C中,从Int到Bool之间一定还存在一个态射odd∘sqrt,这个态射同样可以把Int变成Bool。而在范畴D中,也一定对应着一个映射fmap (odd ∘ sqrt),实际上范畴D中已经存在fmap odd和fmap sqrt这两个被F: C → D映射过去的态射了,它们的组合(fmap odd) ∘(fmap sqrt)出现在了被映射过去的fmap (odd ∘sqrt)的位置上。我们现在遇到了函子在范畴学上的第二个约束——组合律,在这个约束中,F必须满足F(f) ∘ F(g) ≡ F(f ∘g),≡在这里代表同构(isomorphic),即在任何条件下都成立。

也就是说,在范畴C中态射的组合等同于组合之后的态射在范畴D中的映射。换句话说,对于Haskell中的列表,fmap (odd . (^2))和fmap odd . fmap (^2)作用在列表上应该得到相同的结果:

Prelude> fmap (odd . (^2)) [1..10]
[True,False,True,False,True,False,True,False,True,False]
Prelude> (fmap odd . fmap (^2)) [1..10]
[True,False,True,False,True,False,True,False,True,False] 

注意这里为了类型匹配,并没有使用函数库中针对浮点数的sqrt,而是使用(^2)来求平方。第一个式子对列表中的每一个元素先求平方,再判断是否是奇数;第二个式子则是先对列表中的每一个元素求平方得到新的列表,再对这个新的列表中每一个元素做判断,所以第一个式子只需要遍历列表一次,而第二个式子需要先后遍历列表两次。

而范畴学要求这两个式子的值必须相等,这也是Haskell编译器做融合循环优化的理论基础,多次遍历的组合等同于组合的遍历。我们用Haskell的语言再次描述一下函子必须满足的要求,函子实例的fmap必须满足下面的等式:

fmap id ≡ id
fmap (f . g) ≡ fmap f . fmap g
可以把刚刚定义的列表和Maybe函子拿过来试试:
Prelude> fmap id [1..10] == id [1..10]
True
Prelude> fmap id Nothing == id Nothing
Prelude> fmap (odd . (^2)) (Just 3) == (fmap odd . fmap (^2)) (Just 3)
True
Prelude> fmap (odd . (^2)) Nothing == (fmap odd . fmap (^2)) Nothing
True

这是我们把范畴学里的约束引入Haskell得出的约束。注意,当声明一个函子的实例时,编译器并不能帮助你检查fmap是否满足这两个约束,因为函数是无法比较相等的。你需要通过自己的推理自行验证这两个约束是成立的,而实际上对于一个函子类型,满足上面两个约束条件的fmap是唯一确定的,这也是GHC可以帮助你推导函子实例的原因。请仔细思考一下,对于列表来说,有可能写出一个满足上面两个条件,且和map不等价的fmap吗?

评论

本文目前还没有评论……

我要评论

需要登录后才能发言
登录未成功,请修改提交。

× 451
× 1756
× 2435
× 933
× 1
× 1
× 1190
× 0
× 1
× 0
× 2
× 1
× 3
× 3
× 2750
× 817
× 1104