8

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?

Community
  • 1
  • 1
dfeuer
  • 48,079
  • 5
  • 63
  • 167
  • 2
    I don't think this is even possible. We'd have to go (operationally) from `Functor f -> [LensLike f s t a b]` to `[Functor f -> LensLike f s t a b]`. We need to pass in a `Functor f` to pull out a list to begin with, and there isn't one around. – András Kovács Oct 12 '15 at 21:33
  • 2
    @AndrásKovács Perhaps we can use a parametricity argument to convince ourselves that functions of type `Functor f -> [LensLike f s t a b]` must choose the length of their result list without inspecting the `Functor f` argument in a meaningful way. Then it's easy to get the rest of the way from there. (Of course this claim is clearly not true of functions of type `Functor F -> [LensLike F s t a b]` for some particular `F`.) – Daniel Wagner Oct 12 '15 at 21:35
  • @AndrásKovacs, that was my fear. We'd need some kind of "superfunctor" dictionary we could pass in that would magically be able to take on the identity of any other `Functor` dictionary. – dfeuer Oct 12 '15 at 21:36
  • @DanielWagner, those were the vague outlines of my thinking. – dfeuer Oct 12 '15 at 21:38
  • Still doesn't seem good to me. The returned lenslikes certainly depend on the functor instance. If we passed some dummy functor instance, they wouldn't work, and anyway we can only abstract over `Functor f` in `ReifiedLens` if we ignore the input instances, which again results in nonsense. – András Kovács Oct 12 '15 at 21:58
  • 1
    I'd like to point out for the specific case of lenses, you can use `ALens` instead of `ReifiedLens`. I'm wondering if there's a similar trick that works generally... – Ørjan Johansen Oct 12 '15 at 22:29
  • @DanielWagner Assuming we do have such a parametricity guarantee, how to perform the conversion in Haskell? unsafe coercion? Would that be type-safe at runtime, in this case? – chi Oct 12 '15 at 22:30
  • In fact, `ALens` is based on [`Pretext`](http://hackage.haskell.org/package/lens-4.13/docs/Control-Lens-Internal-Context.html#t:Pretext), which looks very much like a kind of "superfunctor". – Ørjan Johansen Oct 12 '15 at 22:41
  • 2
    @chi, something like [this](http://lpaste.net/142876) perhaps. – effectfully Oct 12 '15 at 23:35
  • @user3237465, that's a really neat trick, at least for lists. I can't tell if there's a way to generalize it. – dfeuer Oct 12 '15 at 23:59
  • I guess we can do the same for any polynomial functor and its least fixpoint. And when the shape is known statically (e.g. `Vec`) or fixpoint is the greatest (e.g. `Stream`), it's [easier](http://stackoverflow.com/a/27343524/3237465) (just take `m = (->) (Functor f)`). – effectfully Oct 13 '15 at 01:01

1 Answers1

5

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.

Ørjan Johansen
  • 18,119
  • 3
  • 43
  • 53
  • I still find `Pretext` baffling. As applied to `(->)`, I can sort of see it as a partially applied lens, but its utility and generality still confuse me. – dfeuer Oct 13 '15 at 15:54