Is the concept of an "interleaved homomorphism" a real thing?

Question

I am in need of the following class of functions:

class InterleavedHomomorphic x where
  interleaveHomomorphism :: (forall a . f a -> g a) -> x f -> x g

Obviously the name I invented for it is not in any way an official term for anything, and the type class above is not very elegant. Is this a concept that has a name, or even an implementation in some library? Is there some more reasonable way of doing this?

---

The purpose of this function would be that I have some context f that annotates some data (Foo and Bar are just random example data structures for the sake of this question):

data Foo f = One (f (Bar f)) | Product (f (Foo f)) (f (Foo f))
data Bar f = Zero | Succ (f (Bar f))

I would like to transform the context of the data in a polymorphic way; by only knowing the homomorphism between the contexts and not (necessarily) caring about the data itself. This would be done by providing instance InterleavedHomomorphic Foo and instance InterleavedHomomorphic Bar in the example above.

Kenji

Answer 1

So, assuming f and g are proper functors, forall a. f a -> g a is a natural transformation. We could make it a bit prettier:

type f ~> g = forall a. f a -> g a

Natural transformations like this let us form a category of Haskell Functors, so what you have is a functor from that to some other category.

Following the steps of normal Haskell Functors, it would perhaps make sense to have x be an endofunctor, mapping Functors to other Functors. This is similar, but not identical, to what you have:

class FFunctor x where
  ffmap :: (f ~> g) -> (x f ~> x g)

However, in your case x f and x g are not functors, and x f -> x g is a normal function rather than a natural transformation. Still, the pattern is close enough to be intriguing.

With this in mind, it seems that x is still an example of a functor, just between two different categories. It goes from the category of Functors to the category of xs with different structures. Each possible x, like Foo, forms a category with objects like Foo [] and Foo Maybe and transformations between them (Foo [] -> Foo Maybe). Your interleaveHomomorphism function "lifts" natural transformations into these x-morphisms, just like fmap "lifts" normal (a -> b) functions into functions in the image of the functor (f a -> f b).

So yeah: your typeclass is a functor just like Functor, except between two different categories. I don't know of a specific name for it, largely because I don't know a specific name for constructs like x.

More generally, I'm not even sure a specific name would make sense. At this point, we'd probably like a nice generic functor typeclass that go between any two categories. Maybe something like:

class (Category catA, Category catB) => GFunctor f catA catB where
  gfmap :: catA a b -> catB (f a) (f b)

This probably already exists in a library somewhere.

Unfortunately, this particular approach to defining different functors would require a bunch of extra newtype noise since (->) is already a category. In fact, getting all the types to line up properly is going to be a bit of a pain.

So it's probably easiest just to call it an XFunctor or something. Besides, just imagine the pun potential!

EDIT: It looks like categories provides a CFunctor type like this, but a bit cleverer:

class (Category r, Category s) => CFunctor f r s | f r -> s, f s -> r where
  cmap :: r a b -> s (f a) (f b)

However, I'm not certain that even this is general enough! I think that we might want it to be more polymorphic over kinds too.

Alpha

Sure enough something like GFunctor exists; indeed mathematicians would consider endofunctors like the ones we have in Hask very much a special case and usually deal with functors between different categories. Edward parameterises class (Category r, Category t) => Functor f r t | f r -> t, f t -> r where fmap :: r a b -> t (f a) (f b). – Trauma

@leftaroundabout: Thanks! I found the old version in category-extras, but it looks like categories is the newer, better package to use. – Alpha

I do not see how f and g need to be functors. However, it makes sense to treat x as a functor from some category of generic existentially quantified morphisms to another category. It is good to see that CFunctor exists, but a pity that it doesn't have a very rigorous and comprehensive framework built around it in order to be useful. I guess I will have to specialize for my use-case anyways. But this answer makes sense so I will accept it! – Kenji

I'm actually playing around with resurrecting the categories package here at ZuriHac. – Lilylilyan

@dflemstr: f and g need to be functors for forall a. f a -> g a to be a natural transformation, because that's how natural transformations are defined. Also, most simple types of that kind are functors, and I think you pretty much need fmap to do anything useful with Foo and Bar. – Alpha

Answer 2

Bar f looks like the Free Monad Free f ().

Then Foo is a do with one or two <-. Maybe continue from there...

Duran

As I said in the question, I just made up the data types Foo and Bar. In reality, I am dealing with very different data structures. – Kenji

Answer 3

For what it's worth, you can rephrase a simplified version of your example as

data Bar' r = Zero | Succ r
type Bar f = fix (Bar' . f)

For every pair of natural transformations eta1 :: f ~> g and eta2 :: Bar' ~> h we get a natural transformation (eta2 . eta1) :: (Bar' . f) ~> (h . g). And we can lift this natural transformation over the fixedpoint in the obvious way to get fixed (eta2 . eta1) :: Bar f -> fix (h . g). Thus, your "interleaved homomorphism" is just a special case of this construction for when we have eta2 = id.

Overall this is a rather standard construction (especially for the cases where f is a monad or comonad), though I'm not sure whether it has a particular name that's widely recognized.

Congelation