Monoidal vs Traversing

Posted on 2017-10-05 by Oleg Grenrus lens

In the reddit thread about Don't Fear The Profunctor Optics there is discussion about Monoidal.

Discussion is about what's Monoidal?

Monoidal is used to implement traversals. As a concrete example we can pick lists:

When [a] comes in, we pattern match it with out to convert it into Either () (a, [a]) (and use inn to convert back). We let a unit () pass-through by using right (note: we need Choice). And using Monoidal's par we can combine k :: p a b and recursive application of listTraversing to get p (a, [a]) (b, [b]).

Another example: both for a homogenic pair. Here we don't need Choice!

My point: Monoidal (by itself) is only powerful enough to express traversals over Representable containers, and only where Rep f is finite! The idea is that, as Rep f is finite we have a bijection between f a and Vec n a. for some static n :: Nat.

At this point point it starts to be clear that Traversing

is more powerful than Monoidal alone.

It can do Choice (it can also do Strong, which Monoidal cannot without arr :: p a a!). Quite importantly Traversing can handle infinite structures. I don't have a good argument for or against whether Traversals should consider only finite structures, yet traversals over infinite structures are useful in practice.

On the other hand, as davemenendez mentions, we cannot define Monoidal using Traversing! Informally we could say that the relative power is something like:

It's a very good question, if there is practical difference.

On the other hand, and to conclude: there is a Indexed Containers paper discussing containers. And I think that something like that is needed so we can have three classes of optics:

  • Lenses for products
  • Prisms for sums
  • ??? for containers

Then we'll have solid theoretical foundation for optics (IMHO), though probably not expressable in Haskell.

Site proudly generated by Hakyll