Lance Myers

I was looking through the recursion-schemes package documentation a few days ago, and was struck by the type signature of (co)elgot.

elgot :: Functor f => (f a -> a) -> (b -> Either a (f b)) -> b -> a
coelgot :: Functor f => ((a, f b) -> b) -> (a -> f a) -> a -> b

In particular, we can rewrite the coelgot signature as

coelgot :: Functor f => (a -> f a, (a, f b) -> b) -> (a -> b)

It takes a lens to a function! The a -> f a is the “getter” and (a, f b) -> b is our “setter”. Dually, we have elgot taking a prism to a function.

elgot :: Functor f => (b -> Either a (f b), f a -> a) -> (b -> a)

Let’s look at the implementation for elgot, with the arguments renamed to align with our lensy interpretation.

coelgot set get = h 
    where h = set . (id &&& fmap h . get)

If you squint at the recursive equation, you can see that it is h = over (fmap h). The same is true of elgot. We can rewrite both in a very profunctor optics way as follows.

elgot :: Functor f 
    => (forall p. Choice p => p (f a) (f b) -> p a b) 
    -> (a -> b)
elgot prism = soln where soln = prism (fmap soln)
coelgot :: Functor f 
    => (forall p. Strong p => p (f a) (f b) -> p a b) 
    -> (a -> b)
coelgot lens = soln where soln = lens (fmap soln)

So, these optics are specifying a recursive equation. What happens if we use a different kind of optic? Swapping out Strong/Choice for Traversing would produce a way of taking traversals to functions. Would that be useful? We can even go a bit further and not restrict ourselves to functions. For some profunctor constrant C, we could have

opticRecSol 
    :: (Functor f, Mapping p) 
    => (forall q. (Mapping q, C q) => q (f a) (f b) -> q a b)
    -> p a b
opticRecSol optic = soln 
    where soln = optic (map' soln)

How many different recursion schemes are just a special case of the above? Of course we shouldn’t get too carried away, we can write down recursive equations like that, but they may or may not have a meaningful solution.

I’m sure I’m not the first to notice this connection between (co)elgot and lenses/prisms, but I’ve never seen it mentioned and I’d love to see how far this idea can be pushed.