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

  • A+

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.


:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: