范畴论中的“过滤器"是什么样的态射? [英] What kind of morphism is `filter` in category theory?

问题描述

在范畴论中，filter运算是否被视为态射?如果是，那是什么射晶呢?示例(在Scala中)

In category theory, is the filter operation considered a morphism? If yes, what kind of morphism is it? Example (in Scala)

val myNums: Seq[Int] = Seq(-1, 3, -4, 2)

myNums.filter(_ > 0)
// Seq[Int] = List(3, 2) // result = subset, same type

myNums.filter(_ > -99)
// Seq[Int] = List(-1, 3, -4, 2) // result = identical than original

myNums.filter(_ > 99)
// Seq[Int] = List() // result = empty, same type

推荐答案

要回答这样的问题，我想首先了解什么是过滤的本质.

To answer are question like this, I'd like to first understand what is the essence of filtering.

例如，输入是列表是否重要?你能过滤一棵树吗?我不明白为什么不！您将对树的每个节点应用谓词，并丢弃未通过测试的谓词.

For instance, does it matter that the input is a list? Could you filter a tree? I don't see why not! You'd apply a predicate to each node of the tree and discard the ones that fail the test.

但是结果的形状是什么?节点删除不总是定义的，或者是模棱两可的.您可以返回一个列表.但是为什么要列出?任何支持追加的数据结构都可以使用.您还需要数据结构的空成员才能开始附加过程.所以任何单位的岩浆都可以.如果您坚持关联性，那么您会得到一个半身像.回顾filter的定义，结果是一个列表，它的确是一个monoid.所以我们走在正确的轨道上.

But what would be the shape of the result? Node deletion is not always defined or it's ambiguous. You could return a list. But why a list? Any data structure that supports appending would work. You also need an empty member of your data structure to start the appending process. So any unital magma would do. If you insist on associativity, you get a monoid. Looking back at the definition of filter, the result is a list, which is indeed a monoid. So we are on the right track.

因此，filter只是所谓的Foldable的特例:一种数据结构，您可以在折叠该数据结构的同时将结果累积在一个monoid中.特别是，您可以使用谓词来输出单例列表(如果为真)；或一个空列表(标识元素)(如果为false).

So filter is just a special case of what's called Foldable: a data structure over which you can fold while accumulating the results in a monoid. In particular, you could use the predicate to either output a singleton list, if it's true; or an empty list (identity element), if it's false.

如果您想得到绝对的答案，那么折线就是类别同构的一个例子，即代数范畴中的一个同构的一个例子.您要折叠的(递归)数据结构(在filter情况下为列表)是某个函子(在此情况下为list函子)的初始代数，并且您的谓词用于为以下子项定义代数这个函子.

If you want a categorical answer, then a fold is an example of a catamorphism, an example of a morphism in the category of algebras. The (recursive) data structure you're folding over (a list, in the case of filter) is an initial algebra for some functor (the list functor, in this case), and your predicate is used to define an algebra for this functor.

这篇关于范畴论中的“过滤器"是什么样的态射?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！