The cats documentation on FunctionK contains:

Thus natural transformation can be implemented in terms of FunctionK. This is why a parametric polymorphic function FunctionK[F, G] is sometimes referred as a natural transformation. However, they are two different concepts that are not isomorphic.

What's an example of a FunctionK which isn't Natural Transformation (or vice versa)?

It's not clear to me whether this statement is implying F and G need to have Functor instances, for a FunctionK to be a Natural Transformation.

The Wikipedia article on Natural Transformations says that the Commutative Diagram can be written with a Contravariant Functor instead of a Covariant Functor, which to me implies that a Functor instance isn't required?

Alternatively, the statement could be refering to impure FunctionKs, although I'd kind of expect analogies to category theory breaking down in the presence of impurity to be a given; and not need explicitly stating?

CodePudding user response：

I think the main difference is that you can write down FunctionK-instances for things that aren't functors at all, neither covariant nor contravariant.

For example, given

type F[X] = X => X

you could implement a FunctionK[F, F] by

new FunctionK[F, F] {
  def apply[X](f: F[X]): F[X] = f andThen f
}

Here, the F cannot be considered to be a functor, because X appears with both variances. Thus, you get something that's certainly a FunctionK, but the question whether it's a natural transformation isn't even valid to begin with.

CodePudding user response：

When you have some objects (from CT) in one category and some objects in another category, and you are able to come up with a way show that each object and arrow between objects has a correspondence in later then you can say that there is a functor from one to another. In less strict language: you can say that there is a functor from A to B if you can find a "subgraph" in B that has the same shape as A.

In such case you can "zoom out": draw a point, call it object representing category A, draw another, call it object representing B, and draw an arrow and call it functor.

If there are many ways you can do it, you can have multiple functors. And with more categories you can combine these functors like you compose arrows. Which in this "zoomed out" world look like normal objects and arrows. And you can form categories with them. If you can find a mapping between these categories, a functor on functors, then this is a natural transformation.

When it comes to functional programming you don't work in such generic framework. Usually, you assume that:

• object is a type
• arrow is a function
• to define a category you almost always would have to use a generic type, or else it would be too specific to be useful as a general purpose library (isomorphism between e.g. possible transitions of one enum into transition states of another enum could be a functor, but that wouldn't necessarily fit some generic interface)
• since programming languages cannot let you define a generic mapping between two arbitrary types, functors that you'll see will be almost exclusively Id ~> F: you can lift a function A => B into List[A] => List[B], Future[A] => Future[B] and so one easily (this proves existence of F[A] -> F[B] arrow for given A -> B arrow, and if A and B are generic you provided a proof for all arrows from Id), but try finding something more complex than "given A, add a wrapper around it to get F[A]" and it's a challenge
• similarly the only natural transformations you'll see will be from Id ~> F into Id ~> G that is "given A, change the wrapper type from F[A] to G[A]", because you have a guarantee that there is the same A hidden somehow in both F and G and you don't have to deal with modifying it (only with modifying the wrapper)

The latter being exactly a FunctionK or just a polymorphic function in Scala 3: [A] => F[A] => G[A]. A concept from type theory rather than from CT (although in mathematics a lot of concepts map into each other, like here it FunctionK maps to natural transformation where objects represent types and arrows functions between them).

Category theory isn't so restrictive. As a matter of the fact, isn't even rooted in computer science and was not created with functional programmers in mind. Let's create non-FunctionK natural transformation which models some operation on "state machines" implementation:

• object is a state in state machine of sort (let's say enum value)
• arrow is a legal transition from one state to another (let say you can model it as a pair of enum values, and it somehow incorporates transitivity)
• when you have 2 models of state machines with different enums, BUT you can take one model: one enum and allowed pairs and translate it to another model: another enum and its pair, you have a functor. one that doesn't implement cats.Functor but still
• let's say you would model it with some class Translate[Enum1, Enum2] {...} interface
• let's say that this translation also extends the model with some functionality, so it's actually Translate[Enum1, Enum2 | ExtensionX]
• now, build another extension Translate[Enum1, Enum2 | ExtensionY]
• if you can somehow convert Translate[A, B | ExtensionX] into Translate[A, B | ExtensionY] for a whole category of enums (described as A and B) then this would be a natural transformation
• notice that it would not fit FunctionK just like Translate doesn't fit Functor

It's a bit stretched example, also hardly anyone implementing an isomorphisms between state machines would reach for functor as a way to describe it, but it should show that natural transformation is not FunctionK. And why it's so rare to see functors and natural transformations different than Id ~> F lifts and (Id ~> F) ~> (Id ~> G) rewrappings.

PS. When it comes to Scala, you can also meet CT used as: object is a type, arrow is a subtyping relationship, thus covariant functors and contravariant functors appear in type parameters. Since "A is a subtype of B" translates to "A can be always upcasted to B", then these 2 interpretations of functors will often be mashed together - something along "don't define map if you cannot upcast and don't define contramap if you cannot downcast parameter" (see also narrow and widen operations in Cats).