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