makeTraverse for non-last type-argument

[phadej]

Take some data Foo a b c, and i'd like to derive traverse like function for second argument. How hard would it be to parametrise makeTraverse to do that, i.e.

traverseFooB :: Applicative f => (b -> f b') -> Foo a b c -> f (Foo a b' c)
traverseFooB = $(makeTraverse ...)

Even more generally, would be even greater to have unified deriving mechanism for Bitraversable and futher kind-variations. (I had uses for tritraverse), maybe something like

traverseFooAB f g = makeTraversal ''Foo [Use 'f, Use 'g, Skip]

[RyanGlScott]

I'll answer your second question first: in principle, it's not hard to generalize the TH machinery to work on classes of higher arities. In fact, we're already doing so for Eq{1,2} and friends. The only reason that deriving-compat limits itself to Traversable and not Bitraversable is because the bifunctors library already included a way to derive Bitraversable with TH before deriving-compat was created, so I decided that Bitraversable was out of scope for deriving-compat. (Not by coincidence, the code in deriving-compat and bifunctors share many similarities.)

As for the first question, it may be possible to derive traversals for arbitrary type variables, but it would likely need to work in a rather different way than deriving-compat currently works. Here is a first example to set the stage:

data T1 a = MkT1 (T2 a)
$(deriveTraversable ''T1)

When deriving a Traversable instance for T1, we have to "recurse" into T2 in some fashion. The way that deriving-compat does this is by assuming T2 has a Traversable instance and traverse-ing into it. As a result, you'd end up with this code:

instance Traversable T1 where
  traverse f (MkT1 x) = MkT1 <$> traverse f x

Now let's consider a modified example where we only want to traverse over a single type parameter:

data S1 a b = MkS1 (S2 a b)

traverseFirstParamOfS1 :: Applicative f => (a -> f a') -> S1 a b -> f (S1 a' b)
traverseFirstParamOfS1 = $(makeTraverseForFirstParam ...) -- I'm not yet sure what the API would be for this

Similarly, we must also "recurse" into S2 when generating code. However, the situation is a bit different this time, since a simple traverse won't suffice. I can think of two ways to make this work:

1. Assume S2 is an instance of Bitraversable:

   traverseFirstParamOfS1 = \f (MkS1 x) -> MkS1 <$> bitraverse f id x

   The problem with this approach is that it's limited to the last two type variables in a data type. If we wanted to traverse over, say, the third-to-last type variable, we'd have to invent a new type class like Tritraversable. Similarly if we wanted the fourth-to-last type variable (Quadrifunctor), or the fifth-to-last type variable (Quinquefunctor), etc.

2. In the implementation of traverseFirstParamOfS1, pattern-match on the value of type S1 and recurse into its fields. I didn't define what S2 is above, but for the sake of this example, let's assume S2 is defined like so:

   data S2 a b = MkS2A a | MkS2B b

   Then one could generate code for traverseFirstParamOfS1 like this:

   traverseFirstParamOfS1 = \f (MkS1 x) -> MkS1 <$> (case x of { MkS2A y -> MkS2A <$> f y ; MkS2B z -> MkS2B z })

   This also works, but it breaks abstraction a little bit, as it requires knowing what the definition of S2 is. This isn't technically a problem for Template Haskell, as it can always reify the definition of a data type, even if the data type is abstract. Still, it's a rather different approach than what deriving-compat uses, and I'm somewhat hesistant to go down this route.

   By the way, if this option is what you want, you might consider using the genifunctors library, as it uses exactly this approach to define traversals for arity-3-or-greater data types.

[RyanGlScott]

One other downside of option (2) that I forgot to mention above is that it assumes you can case on the value on the first place. If you have something like this, however:

data V1 f a b c = MkV1 (f a b c)

Then you're out of luck, since case-ing on something of type f a b c isn't possible in general.

[phadej]

I think it's fine to give up when recursion is needed and there is no class for that kind-pattern. That's what DeriveFunctor etc does anyway when it encounters an argument in non-last position. That makes machinery less general, and would be nice to have a solution, but it can be found later.

[RyanGlScott]

OK. What API would you propose for this new functionality? Presumably, all of the existing make*2 functions would need variants that allow controlling which type variable(s) you care about. I'm not sure how many variants we'd need or what to name them, however.

Also, there's still an annoying hiccup in that deriving-compat has no knowledge of Bitraversable and friends. I suppose we could put similar functionality in the bifunctors library as well if we wanted to. I'm not sure.

[phadej]

possible options are from top of my head:

• kind-generic traversable class (difficult)
• type's Name kind argument -> Name of that traversal
• generating "full-traversals" (needs naming still)

the second would work with

data S1 a b = MkS1 (S2 a b)

by generating

traverseS1a f (MkS1 s2) = MkS2 <$> traverseS2a f s2

where the naming scheme could be provided by a user.

This won't work with

data V1 f a b c = MkV1 (f a b c)

as there we could only generate "full-traversals", i.e.

traverseAll
    :: Applicative m
    => (forall a1 a2 b1 b2 c1 c2. (a1 -> m a2) -> (b1 -> m b2) -> (c1 -> m c2) -> f a1 b1 c1 -> m (f a2 b2 c2))
    -> (a -> m a')
    -> (b -> m b')
    -> (c -> m c')
    -> V1 f a b c
    -> m (V1 f a' b' c')
traverseAll f a b c (V1 x) = V1 <$> f a b c x

---

EDIT: thanks for prompt reply. i will try to implement the latter thing. even if it doesn't end up in deriving-compat, i'm curious if it can be made work.