"Category laws" 在 Haskell 维基中

Question

根据 Haskell 维基，

https://en.wikibooks.org/wiki/Haskell/Category_theory#Category_laws

Category laws There are three laws that categories need to follow. Firstly, and most simply, the composition of morphisms needs to be associative.

然而，

关系的组合是关联的。

https://en.wikipedia.org/wiki/Composition_of_relations#Properties

函数的组合总是结合的。

https://en.wikipedia.org/wiki/Function_composition#Properties

那么，在什么情况下，Haskell 社区（或 wiki 假设的人）认为态射的组合不是结合违反规则的？

谢谢。

Answer 1

这是一个 datatype/operation 组合，它不是有效的 Category 实例。

数据类型仅包含在一个函数中，该函数用一些 Int 值注释：

import Prelude
import qualified Control.Category as C

data Subs a b = Subs Int (a -> b)

这是伪造的 Category 实例。组合执行注释的减法：

instance C.Category Subs where
    id = Subs 0 Prelude.id
    (Subs x f) . (Subs y g) = Subs (y - x) (f . g)

但是，由于subtraction is not associative，该实例无效！

main :: IO ()
main = do
    let Subs u _ = (Subs 3 id) C.. ((Subs 10 id) C.. (Subs 2 id))
        Subs v _ = ((Subs 3 id) C.. (Subs 10 id)) C.. (Subs 2 id)
    print u
    print v

这个returns

-11
-5

表明组合顺序很重要，这违反了 Category 定律。

Answer 2

您正确地将函数组合和关系组合识别为关联运算，然后似乎问了这个问题：

Since all the operations that we call composition are already proven to be associative, why do we make associativity a requirement of composition operations?

这个问题有两个细微的错误。

您假设我们称为组合的操作集合仅包含函数和关系组合。但事实并非如此：我想我可以，给定时间，写下 20-30 个不同的 classes 组合操作，每个 class 包含一个无限实际合成操作的数量！
你假设的因果关系是倒退的。我们不会首先调用一堆不同的事物组合，然后决定要求它们具有关联性；相反，首先我们确定一些我们喜欢的条件（关联性、具有身份、well-typed），然后让我们自己将标签“组合”附加到满足的 any 操作那些条件。

让我们按照第(2)点的风格来做一些例子。我们会先建立一个我们感兴趣的数学结构，然后我们会问：我们可以把它称为类别吗？

集合函数组合

假设我提出了以下数学结构：

有大量对象，每组对象对应一个对象。（这个陈述不能用集合论来表述！但是没关系。如果我们不想的话，我们不会必须在集合论中工作。）
每对对象都有一组箭头；即，对于集合 X 和 Y，对于定义域为 X 且辅域为 Y 的每个函数，都有一个类型为 X -> Y 的箭头。
为了组合两个箭头，我们使用集合论中的标准函数组合。

这个结构是一个类别吗？正如您在问题中正确观察到的那样，答案是是，因为：

对于任何对象 X，我们可以创建一个类型为 X -> X 的箭头，与其他箭头组合对它没有任何作用（即，return其输入不变的函数）。
正如您正确观察到的那样，我们可以证明函数组合是关联的。

有加法的数字

这里有一个稍微简单的结构：

有一个对象，名为 X。
存在类型为 X -> X 的箭头集合；在这个集合中，每个自然数一个箭头。
要组成表示数字 m 和 n 的箭头，请生成表示数字 m+n 的箭头。

注意在这个结构体中，我们定义的组合操作既不是函数组合也不是关系组合！我们现在要问的问题是：当我们将标签组合附加到这个操作时，我们是在自欺欺人，还是这样称呼它是明智的？

在这种情况下，答案是是，我们可以称它为组合（并将整个结构称为类别），因为：

我们可以创建一个类型为 X -> X 的箭头，它与其他箭头的组合没有任何作用（即代表数字 0 的箭头）。
众所周知，加法是结合的。

正数加法

对前面的例子稍微修改一下如何：

有一个对象，名为 X。
存在类型为 X -> X 的箭头集合；在这个集合中，每个正自然数一个箭头。
要组成表示数字 m 和 n 的箭头，请生成表示数字 m+n 的箭头。

我可以将其称为类别吗？这种关系是我可以贴上“组合”标签的东西吗？（注意操作本身是和之前一样的操作！）在这种情况下，答案是否，我们不应该把这个结构叫做范畴，也不应该把这个操作叫做组合，因为虽然操作是关联的，但是没有箭头在组合时保持其他箭头不变。

具有奇怪指数的数字

多一个结构：

有一个对象，名为 X。
存在类型为 X -> X 的箭头集合；在这个集合中，每个自然数一个箭头。
组合箭头 m 和 n:
- 如果 m 或 n 中的任何一个为 0，return 另一个。比如0和1的组合就是1； 2和0的合成为2； 0和0的组合是0.
- 否则取幂m^n。

我们可以把这个结构称为类别吗？最后的操作是我们可以标记为“组合”的东西吗？在这种情况下，答案是 no，因为虽然有一个箭头在组合下让其他人单独行动（即 0），声称的组合操作不是关联的：

2^(1^2) = 2^1 = 2
(2^1)^2 = 2^2 = 4

通过一些工作，我们可以以更微妙的方式制作出不符合类别法则的更奇特的例子（例如，通过关联，但只有 one-sided 身份）。但到现在为止，我希望模式已经清晰：类别法则是我们使用的必要条件，我们在每种情况下做出的决定都是关于我们感兴趣的数学结构是否是我们可以称之为“类别”的东西。（当然，即使这个问题的答案是否定的，我们仍然可以对它感兴趣并研究它！）

"Category laws" 在 Haskell 维基中

"Category laws" in Haskell wiki

haskell

functional-programming

category-theory