How can I push polymorphism into a data structure?

Question

A recent question led me to wonder how to convert a

forall f . Functor f => [LensLike f s t a b]

into a

[ReifiedLens s t a b]

There's an easy way to do it really slowly, by indexing into the list with !!, but it's quite incredibly inefficient. It feels like there should be enough parametricity to pull a trick similar to the one used in reflection, but I can't seem to figure anything out. Is it possible to do this efficiently at all?

Answer 1

Testing out my idea in the comments, you can in fact write this directly by passing through ALens:

convert :: (forall f. Functor f => [LensLike f s t a b]) -> [ReifiedLens s t a b]
convert ls = [Lens (cloneLens l) | l <- ls]

ALens is based on the Pretext functor:

type ALens s t a b = LensLike (Pretext (->) a b) s t a b

newtype Pretext p a b t = Pretext { runPretext :: forall f. Functor f => p a (f b) -> f t }

This allows using a single Functor to represent all of them, at least for lens usage.

I'm still wondering whether there's a method that works generally and not just for lenses.