Clever Geek Handbook

程序员的范畴论。在手指上

大家好也许有人会说，







在严肃的学术文献中发展出我们坚定的兴趣，我们进入了范畴论。巴托斯·米列夫斯基（Bartosz Milevsky）著名的演讲中的这个话题已经出现在哈布雷（Habré）上，并且现在可以夸耀这样的指标了：







能够找到相对新鲜的材料（2020年1月）变得更加令人高兴，这是一本极好的书籍，同时又对类别理论进行了尽可能简短的介绍。希望我们能够引起您对该主题的兴趣。



如果您和我，亲爱的读者，遇到类似的问题，那么您曾经被“什么是单子？”这个问题所困扰。然后，您用谷歌搜索了这个问题，悄悄地滑入了抽象数学的兔子洞，陷入了函子，monoid，类别直到他们注意到他们已经忘记了什么问题把您带到这里。如果您以前从未看过函数式编程语言，但是不用担心，这种体验可能会让人不知所措！我为您研究了许多页面的密集数学，并观看了数小时的有关该主题的讲座。因此，为您省去麻烦，我将在这里总结该主题，并向您展示如何应用类别理论，以便您现在就可以以功能样式思考（并编写代码）。



本文适用于在函数式编程领域中自认为是“新手”并且刚开始使用Scala，Haskell或其他类似语言的任何人。阅读本文之后，您将对解释类别理论的基础并“在地面上”确定其原理感到更有信心。另外，如果您曾经尝试过理论数学，请不要直接提及此处讨论的概念。通常，关于它们的内容要比这里写的多得多，但是对于一个好奇的程序员来说，这篇文章就足够了。



基础



那么类别到底是什么，它与编程有什么关系？像编程中使用的许多概念一样，类别是一个非常简单的名称。这只是带有一些附加限制的标记有向图。类别中的每个节点都称为“对象”，其每个边缘都称为“形态”。







您可能已经猜到，并不是每个有向图都是一个类别。要将图形视为类别，必须满足一些其他条件。在下一张图片中，我们注意到每个对象都有一个指向自身的态射。这是相同的形态，每个对象必须具有这样的特征，才能将图形视为一个类别。接下来，请注意该对象A的态射f表示B，并且对象同样B具有g指向的态射C。由于是从路径A到B从B到C，显然是有从路径A到C，对不对？这是对态射的下一个要求类别，必须进行相关的合成，这样对于射态来说f: A = > B ，g: B = > C就存在一个射态h = g(f): A = > C。



这些计算似乎已经有点抽象了，所以让我们看一个满足该定义并用Scala编写的示例。 



trait Rock
trait Sand
trait Glass
def crush(rock: Rock): Sand
def heat(sand: Sand): Glass


我认为这个例子使关系变得容易一些。将石头擦成沙子是将物体rock变成物体的形态sand，而从沙子上熔炼玻璃是将物体sand变成物体的形态glass。在这种情况下，这些关系的组成肯定会像 



val glass: Glass = heat(crush(rock))


还有身份函数（在PredefScala中定义），因为对于任何对象，编写返回相同对象的函数并不困难。因此，该系统是一个类别，尽管相当简单。



更加熟悉类别







现在，我们将对类别理论的术语进行更深入的研究，并从一个称为岩浆的类别开始。如果您还不太熟悉这个基本概念，请让我解释一下岩浆仅仅是一个二进制运算，即对两个值的运算，因此将获得一个新值。为了不赘述，在这里我不会证明所有二进制运算的集合实际上是一个类别，但是对于那些对细节感兴趣的人，我建议阅读Bartosz Milevsky的以下文章。从加法到乘法的所有算术都属于子类别，按岩浆类别统一（见图）。



以下继承顺序在这里适用：



  • 1.岩浆：所有二进制运算
  • 2.半组：所有关联的二进制运算
  • o : .
  • 3. : ,
  • o : , (aka )


因此，回到我们前面的示例，加法和乘法都是单义的，因为它们是关联的(a + (b + c) = (a + b) + c)并且具有单个元素（ax 1 = 1 xa = a）。该图上的最后一个圆圈包含准群，与半群或类半群不同，它们可能适用于不同的嵌入原理。准组是可逆的二进制操作。解释此属性并非易事，因此，我请您参考Mark Siman撰写的有关该主题的系列文章。二进制运算是可逆的，当对于任何值a和b有这样的值x，并y在允许转换a到b... 我知道这听起来很棘手。为了清楚起见，让我们看下面的减法示例： 



val x = a - b
val y = a + b
assert(a - x == b)
assert(y - a == b)


请注意：y本身不参与减法，但是示例仍然有效。类别中的对象是抽象的，几乎可以是任何东西。在这种情况下，重要的是，对于任何a和b可以产生，这些语句保持真实。



上下文中的类型



不管您的特定学科如何，对于理解编程中数据类型含义的任何人，类型主题都应该清楚。所有类型都是整数，布尔值，浮点数，等等，但是您如何用单词描述理想的柏拉图类型呢？ Milevsky在他的著作《面向程序员的分类理论》中，成为一系列博客文章，将类型简单地描述为“值的集合”。例如，布尔值是包含值``true''和“ false''（false）的有限集。字符（字符）是所有数字字符的有限集合，而字符串（字符串）是字符的无限集合。



问题在于，在范畴论中，我们倾向于远离集合，并从对象和形态学的角度进行思考。但是类型是简单集合的事实是不可避免的。幸运的是，由于这些对象是抽象的并且可以表示任何内容，因此在这些集合的类别理论中占有一席之地。因此，我们完全有权说我们的对象是集合，并进一步将我们的Scala程序视为类别，其中类型是对象，功能是态射。对许多人来说，这似乎很痛苦。毕竟，在Scala中，我们习惯于处理对象，但是值得明确指出。



如果您使用过诸如Java之类的面向对象的语言，那么您可能会熟悉泛型类型的概念。这些像LinkedList或者，对于Scala，Option[T]其中T表示存储在某些结构中的基础数据类型。如果我们想创建从一种类型到另一种类型的映射以保留第一种类型的结构怎么办？欢迎来到函子的世界，函子定义为类别之间的映射，以维持结构。在编程中，通常必须使用函子的子类别，即所谓的endofunctors，它们有助于将类别映射到自身。所以我只是说，当我谈论函子时，我是指内函子。



作为函子的示例，让Option[T]我们结合前面的示例（涉及石头，沙子和玻璃）来查看Scala类型： 



val rockOpt: Option[Rock] = Some(rock)


上面有Rock我们前面定义的类型，但是包裹在中Option。这是一种泛型类型（更多信息，请参见下文），它告诉我们对象是我们正在寻找的特定实体，或者None可以与null其他语言进行比较。



如果我们没有使用仿函数，那么我们可以想像我们如何将一个函数crush()来Rock，这需要诉诸操作if 来处理它的情况Option是None。 



var sandOpt: Option[Sand] = None
if(rockOpt != None) {
  sandOpt = Some(crush(rockOpt.get))
}


我们可能会说这是一个旁白，但是请不要使用var-这样的代码在Scala中是不好的，原因有几个。再次回到主题：在Java或C＃中，这将不是问题。您检查以查看您的值是否属于您期望看到的类型，并对其执行任何操作。但是借助函子的功能，可以使用函数更优雅地完成所有操作map()： 



val sandOpt: Option[Sand] = rockOpt.map(crush)


繁荣，一行，您就完成了。可以使用三元运算符或类似的东西将第一个示例放在一行中，但是您不会那么成功。这个例子非常简单。这是这里发生的事情：它map()接受一个函数并将该函数（在数学意义上）映射到自身。该结构被Option保留下来，但现在它包含两种Sand或None代替Rock或None。这可以通过以下示例进行说明：







请注意，所有内容的排列多么精美，每个对象和形态都保留在两个系统中。因此，中心的射影是一个函子，表示从T到的映射Option[T]。



一起



现在，我们终于可以回到原来的问题：“到底是什么单子”？有一个答案，如果您只是尝试使用Google，您可能会盲目地发现它，它听起来像是：monad只是endofunctors类别中的一个类人动物，通常后面跟着非常讽刺的话，“这是什么问题？”通常，以这种方式，他们尝试开玩笑地显示此主题中的所有内容有多么困难，但实际上，并非所有内容都如此可怕-毕竟，我们已经弄清楚了该短语的含义。让我们再次逐步进行。



首先，我们知道monoid是关联的二进制运算，每个运算都包含一个中性（单个）元素。其次，我们知道endofunctors允许我们将类别映射到自身，同时保持结构。因此，monad只是某种包装类型（如上面的通用类型示例中所示），它维护某种接受函数并将其映射到自身的方法。List-这是一个单子，Option（就像上面我们所考虑的那样）是一个单子，甚至有人可以告诉你，Future它也是一个单子。例： 



val l: List[Int] = List(1, 2, 3)
def f(i: Int) = List(i, i*2, i*3)
println(l.flatMap(f)) // : List(1, 2, 3, 2, 4, 6, 3, 6, 9)


看似简单，不是吗？至少应该有一种感觉，在这里掌握所有内容并不难，即使乍一看并不清楚该概念的用途。


More articles:


All Articles