Affine Traversal

Posted on 2017-03-20 by Oleg Grenrus lens

Thanks to Matthew Pickering, I learned about affine traversals. Affine traversal is an optic that has 0 or 1 target; the fact which you can check by using specialised view function! While playing with them, you have to use Pointed in the van Laarhoven formulation; profunctor one doesn't suffer from this (subjective) unelegancy!

Behold, profunctors ahead:

Affine traversal is an optic that has 0 or 1 target (see e.g. failing)

The simplest example would be:

The problem is that in lens (var Laarhoven encoding) a Prism is:

here, Applicative is too restrictive, forcing combination with

to be full

To define prism, the disputed Pointed class would be enough. In lens usage it won't be as bad, as library writer controls how they will instantiate f in the optic!

If we had

then we could define

The "nice" consequence, is that

used on a AffTraversalVL

would give Default values on non-match (and not mempty):

because Pointed (Const r) is defined in terms of Default r.

#Profunctor approach

If we'd use profunctor optics, Lens and Prism are defined more uniformly:

It turns out that their combination is the affine traversal!

We can repeat the above example, if we define Choice (Forget r) using Default (instances are at the end):

used on an optic

seems to work:

Another approach is to define

And as ForgetM isn't (cannot be?) Traversing, this won't type-check:

but the viewP does fold:

We could define Traversing instance for ForgetM, but we deliberately don't, as we want that type-check failure to occur.

The profunctor approach is more elegant, as we don't need to rely on Pointed, the point is baked into affviewP formulation!

I think the AffTraversal can be useful in practice. There are situations where you know that there is at most one value, hidden inside your big structure. By using firstOf, we don't enforce that fact, but we could!

#Equivalence

We can show that the definitions are equivalent. We start by specifying the constructors:

Then to go from profunctor to van Laarhoven, we'll need a profunctor kiosk:

Then conversion is simple, as Kiosk characterizes affine traversal, we can run the profunctor optic to get getters and setters, which in turn are used to construct van Laarhoven variant:

To go in other direction we need a functor kiask:

And the conversion functions follows the same principle as previous one:

And those seem to work!

#Traversing

The traversal in profunctor optics is defined using Traversing or Wander class:

It's trivial to define Wander1 for non-empty traversals: replace Applicative with Apply and postfix 1 to the symbol names:

So let's go for affine traversal as well:

where AffTraversable has obvious definition, and Maybe is a canonical instance:

Using the conversion functions from the previous section, we can show that

are isomorphic! It's 10 at the morning, so I don't try to conclude from that AffTraversing p is equivalent to (Strong p, Choice p), but they are close. And what that means to the Default & Pointed story?

Class Functor Container Example Cat
Default Pointed AffTraversable Maybe ?
Semigroup Apply Traversable1 NonEmpty Semigroupoid
Monoid Applicative Traversable [] Category

#Lens with Maybe

AffTraversal isn't equaivalent to Lens s t (Maybe a) (Maybe b) as the latter let you remove values from the structure (e.g. at).

The Lens s t (Maybe a) b is closer:

but doesn't seem practical (and needs differently specified lens laws!)

#Appendix

Simple van Laarhoven optics:

#Forgotten instances


See discussion in r/haskell


You can run this file with

fetch the source from https://gist.github.com/phadej/0280d0748c7f3205daf7de07cc4dd7d0

Site proudly generated by Hakyll