Indexed Profunctor optics

Posted on 2017-04-26 by Oleg Grenrus lens

This post is a response to the Edward's tweet:

Now try to fit all of the indexed and index-preserving variants. ;) Edward Kmett

Which in turn is a reply to my previous post: Glassery.

First I'll show how we can implement indexed optics using a newtype Indexed, as purescricpt-profunctor-lenses (version 3.2.0) does. This approach is already mentioned in Glassery, but I'll also compare it to the lens encoding.

The rest of the post is novel, at least I haven't seen such tehnicque applied to lenses before. By indexing a profunctor itself (p i a b), we regain the flexibility of lens approach (Section: Indexed profunctor). This approach also scales to so called "coindexing", so it's possible to extract "coindexes", e.g. reason why or where Prism failed (Section: Coindexed).

This blog post introduces a type alias with 9 (nine) variables:

type IndexedOpticJ p i j k l s t a b =
    p i j a b -> p k l s t

#Contents

This work is licensed under a “CC BY SA 4.0” license.

#Newtype

The current way to do indexed optics in profunctor encoding is to use a newtype

That's the approach taken by purescricpt-profunctor-lenses (version 3.2.0).

Definition of indexed traversal if not complicated, we don't need new type-classes: the old friend Traversing is enough:

We'll use itoListOf in the examples.

The definition is similar to regular toListOf

We can combine indexed and regular optics, without problems, using function composition:

Combining two indexed optics directly won't work.

itoListOf (itraversed . itraversed) ["foo", "bar"]

<interactive>:77:10: error:
    • Couldn't match type ‘p’ with ‘Indexed p Int’

That's because the type of the result optics has two Indexed, but definition of itoListOf requires only single one!

So we need to define a special combinator for the optic composition:

Alternatively we can use an OpticLike, which let us combine the indices in the optic building "pipeline":

#Comparison to lens

In lens, if we combine two indexed optics we'll get the latter index: (profunctor: type-error).

We should use icompose (or <.>) to combine indices:

On the other hand, in lens indexed optics degrade to regular one when used by a regular operation:

Profunctor version fails with a type error:

toListOf itraversed [1,2,3]

<interactive>:274:25: error:
    • Couldn't match type ‘Forget [a] a a’
                     with ‘Indexed (Forget [a]) Int Integer Integer’

We must remove the index explicitly:

So the Profunctor encoding using newtype Indexed is more rigid. We have to be explicit about the index (or indices). Whether this is good or bad: depends.

Some might think that being explicit is good. On the other hand, the implicitness of lens is not a problem. If we have type redundancy, forcing a type of the result; you'll get a type-error if lenses are combined with wrong combinator. A bit later than when building up the optic (and not annotating it with a type-signature) though.

The print (itoListOf o s) examples doesn't have such redundancy, so the issue may seem bigger than it is.

#Indexed profunctor

In lens, we can get away with having indexed optics because we have two type parameters, and when you go to compose two optics with (.), the profunctor part automatically selects p = (->) by unification, for the optics that supply indices, as composing a couple things of the form Edward Kmett

Or as Matthew Pickering put it: there are two parameters in lens encoding, p and f. By varying the f, we can change the lens type (Lens, Getter, Fold or Traversal) and by varying p we can vary between indexed and regular variants.

That's a good insight. We can add an additional degree of freedom to the profunctor encoding:

The idea is to have index variable on both side of the arrow! Instead of stacking up Indexed, we'll stack up something on top of o. The example will make this more concrete. Let's make an indexed traversal.

We have to introduce a new class TraversingWithIndex.

Note that indexes of IndexedOptics are related: (i, o) and o. Every IndexedTraversal in the chain would add an additional index. There's an engineering problem: what kind relation would be the most convenient for a practical usage (should we use DataKinds and type-level lists?). For now we'll use tuples, and keep used language extensions to the minimum.

The next step is to define a profunctor implementing that class. The Star is good template, we only need to add an index:

another one is a variant of Forget which forgets the index as well:

and the one which doesn't:

Using ForgetI we can define normal operations,

and using IndexedForget the indexed variants:

Now we can use toListOfI on the indexed optic!

or itoListOf, though we get very ugly indexes:

It's possible to write a variant itoListOf with a type signature requiring single index:

As with the newtype variant, it's possible to flatten indices. In fact ilmap is a general index mapping function.

We can compose indexed and regular optics using function composition dot, .:

Graceful degradation from indexed to regular optics is possible with profunctor optics too. The key idea is to make every optic indexed (kind of)!

The engineering challenge here, is to design an algebra for indices. With DataKinds and type-level lists and type-families to tuples, the API can be made quite nice (I guess, hopefully there aren't some nastiness for type-inference).

#A CPS note

One option to make IndexedOpticI elegant, is instead of nesting tuples, we could use (->) version:

The combination has a nice type:

Defining operations is not complicated, we have to be just a bit more clever in the instantiation:

The double-index example may clarify better: the first index of the optic is instantiated to the "joint" index type, and the latter to the function to produce the joint index from the actual two.

And we can fuse the two function arguments above;

To write the examples will use a flattenIndicesC. Note: Now we have to precompose with it.

And the example:

or using ifoldMapOfC2':

Thanks to Tom Ellis for mentioning this idea. and correcting me further.

#Coindexed

Also, there is a notion we don't currently explore in lens (it is incompatible with the notion of indexed optics) of what I call 'coindexed' optics. You can think of it as allowing information back in the failing match case. e.g a prism that returns an error message on failure. When you combine the two features the problem gets even worse, as one wants to push information from the left side of the (.) towards the right and the other wants to push information from the right side of the (.) towards the left and they need to conspire to produce the right types now with 2-3 sources of information about what it should be! Edward Kmett

That's easy.

"We can solve any problem by introducing an extra level of indirection." David J. Wheeler

In our case: type variables. In this section we'll use a monstrous type mentioned in the introduction:

one index pair for the contravariant argument (as previously), and one more pair for covariant.

Writing operations using this encoding isn't different than previously. We make some concrete profunctor, use optic to transform it, and then use the result:

That's not exactly a ifoldMapOf variant, as it can fail with a description!

Let's define few constructors to play with examples. We will use bare String for errors, in real library you probably want something more structured.

To define prisms we need a variant of Choice, not that we

And a Traversing variant. Let's make examples interesting by making IndexedFOrgetJ instance "fail", if the Traversal is empty:

We have to define auxiliary type to select the right error when traversing:

#Examples

It's time for examples. The "good" cases work as before:

Note if traverse' zooms into empty Traversable, it won't be an error. But we can make a variant which would make that erroneous as well.

The erroneous cases work as we want: looking at wrong value through Prism gives Prism error, Looking through Traversal at empty list gives an empty fold error:

If we combine a Traversal and a Prism we'll see how different erroneous cases work. If all elements of the list are Right, we get them. If some is Left, but there's at least one Right; we still get Right. If all values are Left we get prism error; and if the list is empty we get an empty fold error. Here we could use idimapJ to flatten errors, but it's good to see on which "level" error occurred.

#Conclusion

In this blog post a presented some ideas for indexed profunctor optics, there's still a lot to design and engineer. The current approach is quite good IMHO. But maybe using indexed profunctor encoding we can make it even better. The Coindexed example is made with a tongue-in-cheek, but maybe there would be practical use cases for it too. After all, it degrades into indexed case nicely.

#Appendix: Test runner

#Appendix: Instances

#Indexed

#Forget

haskell ignore instance Monoid r => Traversing (Forget r) where wander f (Forget p) = Forget (getConst . f (Const . p))

#ForgetI

#StarI

#IndexedForget

#IndexedForgetJ

#Appendix: Changes

Added a note about CPS version of IndexedOpticI, thanks to Tom Ellis.


Leave comments in /r/haskell thread

You can run this file with

stack --resolver=nightly-2017-03-01 ghci --ghci-options='-pgmL markdown-unlit'
λ> :l IndexedPoptics.lhs

fetch the source from https://gist.github.com/phadej/638733a00ccf2c69bff66ad419902ff0

Site proudly generated by Hakyll