在范畴论中，`filter`是什么类型的态射？

Question

在范畴论中，filter操作被认为是一个态射吗？如果是，它属于什么类型的态射？示例（使用Scala语言）。

范畴论中，是否将filter操作视为态射？如果是，它属于哪种类型的态射？例如（使用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

- Polymerase

Answer 1

一种有趣的看待这件事情的方式是，不把filter作为原始概念。有一个名为Filterable的Haskell类型类 被恰当地描述为：

类似于Functor，但它包含Maybe效应。

严格来说，类Filterable代表从Kleisli Maybe到Hask的函子。

"从Kleisli Maybe到Hask的函子"的态射映射由该类的mapMaybe方法捕获，这确实是同名Data.Maybe函数的推广：

mapMaybe :: Filterable f => (a -> Maybe b) -> f a -> f b

类别律就是适当的函子律（注意，在Kleisli Maybe中，Just和(<=<)分别是恒等和复合函数）：

mapMaybe Just = id
mapMaybe (g <=< f) = mapMaybe g . mapMaybe f

这个类也可以用catMaybes来表示...

catMaybes :: Filterable f => f (Maybe a) -> f a

...这与mapMaybe是可以互相定义的（类似于sequenceA和traverse之间的关系）...

catMaybes = mapMaybe id
mapMaybe g = catMaybes . fmap g

...并且相当于Compose f Maybe和f之间的自然变换，它们都是Hask函子的一部分。

那么这一切与你的问题有什么关系呢？首先，函子是范畴之间的态射，自然变换是函子之间的态射。因此，在这里可以以比“在Hask中的态射”更有趣的方式谈论态射。你不一定会想要这样做，但无论如何，这是一个现有的观点。

其次，filter也是Filterable的一种方法，其默认定义为：

filter :: Filterable f => (a -> Bool) -> f a -> f a
filter p = mapMaybe $ \a -> if p a then Just a else Nothing

或者，使用另一个可爱的组合符号拼写：

filter p = mapMaybe (ensure p)

这间接地使得filter在这个特定的范畴概念中有了位置。

- duplode

Answer 2

为了回答这样的问题，我首先想要了解过滤的本质。例如，输入是否为列表是否重要？你可以过滤树吗？我认为是可以的！你可以对树的每个节点应用谓词，并丢弃未通过测试的节点。

但结果的形状会是什么样子呢？节点删除并非总是被定义或者含义不明确。你可以返回一个列表。但为什么是列表？任何支持追加的数据结构都可以工作。你还需要一个空成员来开始追加过程。因此，任何具有单位结构的集合结构都可以。如果你坚持要结合律，那么你就得到了一个幺半群。回顾一下filter的定义，结果是一个列表，这确实是一个幺半群。所以我们在正确的轨道上。

因此，filter只是称为Foldable的数据结构的特殊情况：在其中折叠时积累结果的幺半群。特别地，您可以使用谓词将其输出为单例列表（如果为真）或空列表（身份元素）（如果为假）。如果你想要一个明确的答案，那么fold是catamorphism的一个例子，也是在代数范畴中的morphisms的一个例子。你正在对其进行折叠的（递归）数据结构（在filter的情况下是一个列表）是某个函子（在这种情况下是列表函子）的初始代数，而你的谓词用于为该函子定义代数。

- Bartosz Milewski

---

我认为这是分歧概括开始的地方。你正在看List数据结构，并将其概括为Foldable。然而，我不明白为什么不能将filter应用于模拟随机抽样的单子上，以仅生成满足某些谓词的样本。这与可折叠数据结构基本没有关系，但它可以很好地适应用于生成复杂随机对象的单子框架中。我不确定Foldable是从filter中提取的唯一可能的“本质”。 - Andrey Tyukin

@AndreyTyukin 看起来这个单子必须包含一个可折叠的结构。例如，考虑 Supply — 它有一个操作 supplies，可以获取一个列表。在我看来，所有的响应式编程都是另一种情况，你在单子中生成事件列表，然后像处理纯数据一样处理它。这是否让您重新考虑“这与可折叠数据结构基本没有关系”的说法？ - Ignat Insarov

@IgnatInsarov 你提供的 Supply 看起来有点像一个无限元素流，这又是一种可数无限数据结构，与 List 相似。但我也可以过滤掉所有不像 Foldable 数据结构的东西。例如，可以明显地通过某个条件 cond 来定义集合并对其进行过滤：class Set[X](cond: X => Boolean) { def contains(x: X) = cond(x) ; def filter(p: X => Boolean) = new Set[X](x => cond(x) && p(x)) }。我不知道这样的内涵 Set[X] 如何成为 Foldable。 - Andrey Tyukin

@AndreyTyukin 我不确定我理解这种语言（它是Scala吗？我只会Haskell），但是说这个定义不具有建设性是否正确呢？换句话说，它暗示了某种类型X的存在并定义了一个谓词。如果是这样，那么X就是Foldable，我们在这里拥有的是_(同构于)_一个过滤器。 - Ignat Insarov

@IgnatInsarov 不确定您所说的“建设性”是什么意思。它不是外延的（无法枚举集合的所有元素，更不用说以任何有意义的方式对其进行折叠），但对于例如建设性实体几何来说，它仍然足够建设性，在那里我们可以奇妙地过滤立方体中未包含在球体中的所有元素，而无需调用任何类型的fold。 - Andrey Tyukin

@AndreyTyukin 我的意思是你还没有提供展示 X 的方式，包括它的任何点。因此，你并没有定义一个 (可折叠的) 对象，而只是从中定义了一个态射。我不知道这张图片是如何获得的，但我的 3D 图形学理解表明，切割球体和立方体的滤波器被符号线性变换以在平面上获得投影，然后将带有此投影的折叠应用于像素或某些合适的抽象。当然，这一过程绝非简单，但更应该仔细寻找一个更严谨的折叠方法。 - Ignat Insarov

Answer 3

在本回答中，我将假设您在谈论Set上的过滤器（对于其他数据类型来说情况似乎更加混乱）。

让我们首先明确我们在谈论什么。我将具体讨论以下函数（在Scala中）：

def filter[A](p: A => Boolean): Set[A] => Set[A] = 
                                     s => s filter p

我们把它写成这个样子，就可以清楚地看到它是一个多态函数，带有类型参数A，将断言A => Boolean映射到将Set [A]映射到另一个Set [A]的函数。要使它成为“态射”，我们首先必须找到一些范畴，在这些范畴中，这个东西可以成为“态射”。人们可能希望它是自然变换，并因此成为“Hask”（或“Scal”？“Scala”？）通常称为“默认环境类似结构”的endofunctor类别中的态射。为了证明它是自然的，我们必须检查以下图表对于每个f: B => A是否满足交换律：

                       - o f
Hom[A, Boolean] ---------------------> Hom[B, Boolean]
     |                                       |
     |                                       |
     |                                       |
     | filter[A]                             | filter[B]
     |                                       |
     V                  ???                  V
Hom[Set[A], Set[A]] ---------------> Hom[Set[B], Set[B]]

然而，这里我们立即遇到了困难，因为在底部的水平箭头上甚至不清楚要放什么，因为赋值A -> Hom[Set[A], Set[A]]似乎甚至不是函子范畴（出于同样的原因，A -> End[A]也不是函子范畴，请参见此处和此处）。

我在这里看到的唯一“范畴”结构是对于一个固定的类型A：

• 关于A的谓词可以被认为是一个带有蕴含的偏序集，即如果p意味着q（即对于所有x: A，要么p(x)为false，要么q(x)为true），则p LEQ q。
• 类似地，在函数Set[A] => Set[A]上，我们可以定义一个偏序与f LEQ g，每当对于每个集合s: Set[A]，它都满足f(s)是g(s)的子集。

然后filter[A]将是单调的，并且因此是偏序范畴之间的函子。但是这有点无聊。

当然，对于每个固定的A，它（或者更确切地说，它的eta扩展）也只是从A => Boolean到Set[A] => Set[A]的函数，因此它自动成为“Hask-范畴”中的“态射”。但是这更无聊。

- Andrey Tyukin

---

我指的是对集合进行filter操作。或者任何数据结构都可以。只要filter接受一个谓词p: A => Boolean并且必须返回相同类型的结果。根据谓词的条件，结果可能为空、子集或与原始数据相同。我已经在原帖中添加了一个示例。 - Polymerase

自用备忘：这整个线程都是胡说八道。1）Sub(X) ~= Hom(X, \Omega); 2）重新审视有关“自由定理”的论文，它们通常以filter为例。 - Andrey Tyukin

Answer 4

filter可以用foldRight来表示:

filter p ys = foldRight(nil)( (x, xs) => if (p(x)) x::xs else xs ) ys

foldRight 在列表上是一个 T-代数的映射（这里的 T 是 List 数据类型函子），所以 filter 是一个 T-代数的映射。

这里讨论的两个代数是初始列表代数。

[nil, cons]: 1 + A x List(A) ----> List(A)

假设有一个“筛选”代数。

[nil, f]: 1 + A x List(A) ----> List(A)

其中f(x, xs) = if p(x) x::xs else xs。

在这种情况下，我们将filter(p, _)称为从初始代数到过滤器代数的唯一映射（在一般情况下称为fold）。它是代数映射的事实意味着以下方程式得到满足：

filter(p, nil) = nil
filter(p, x::xs) = f(x, filter(p, xs))

- user7971319

---

关于“我只是想留个评论”的问题：这篇文章已经足够清晰地回答了问题，所以不用担心它的长度。 - duplode

通常来说，如果某个东西回答了问题，那么最好将其作为答案。评论主要用于澄清/更正。 - Cubic

嗯，我不确定我理解这个答案。对于foldRight的参数，它们看起来像是T-代数，但是对于filter的参数却不是。我该如何将任意的T-代数塞进类型为a -> Bool的函数中呢？ - Daniel Wagner

@iamcap7 感谢你的回答。顺便问一下，你是不是指 x :: xs？ - Polymerase

foldRight是一个映射函数，它接受T-代数作为参数，但不一定会产生T-代数。特别地，filter传递给foldRight的T-代数并不会产生一个T-代数，因此filter本身既不是一个T-代数，也不接受T-代数作为参数。这篇文章中还有其他几个事实错误。将它们全部剥离后，除了“filter可以用foldRight来定义”这句话之外，几乎没有什么内容了。 - Daniel Wagner