# What kind of morphism is `filter` in category theory?

• A+
Category：Languages

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 ``

In this answer, I will assume that you are talking about `filter` on `Set` (the situation seems messier for other datatypes).

Let's first fix what we are talking about. I will talk specifically about the following function (in Scala):

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

When we write it down this way, we see clearly that it's a polymorphic function with type parameter `A` that maps predicates `A => Boolean` to functions that map `Set[A]` to other `Set[A]`. To make it a "morphism", we would have to find some categories first, in which this thing could be a "morphism". One might hope that it's natural transformation, and therefore a morphism in the category of endofunctors on the "default ambient category-esque structure" usually referred to as "`Hask`" (or "`Scal`"? "`Scala`"?). To show that it's natural, we would have to check that the following diagram commutes for every `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]] ``

however, here we fail immediately, because it's not clear what to even put on the horizontal arrow at the bottom, since the assignment `A -> Hom[Set[A], Set[A]]` doesn't even seem functorial (for the same reasons why `A -> End[A]` is not functorial, see here and also here).

The only "categorical" structure that I see here for a fixed type `A` is the following:

• Predicates on `A` can be considered to be a partially ordered set with implication, that is `p LEQ q` if `p` implies `q` (i.e. either `p(x)` must be false, or `q(x)` must be true for all `x: A`).
• Analogously, on functions `Set[A] => Set[A]`, we can define a partial order with `f LEQ g` whenever for each set `s: Set[A]` it holds that `f(s)` is subset of `g(s)`.

Then `filter[A]` would be monotonic, and therefore a functor between poset-categories. But that's somewhat boring.

Of course, for each fixed `A`, it (or rather its eta-expansion) is also just a function from `A => Boolean` to `Set[A] => Set[A]`, so it's automatically a "morphism" in the "`Hask`-category". But that's even more boring.