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
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 "
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
Acan be considered to be a partially ordered set with implication, that is
p LEQ qif
p(x)must be false, or
q(x)must be true for all
- Analogously, on functions
Set[A] => Set[A], we can define a partial order with
f LEQ gwhenever for each set
s: Set[A]it holds that
f(s)is subset of
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.