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):

λ> viewVL ex1 (Right 42, True) :: Int
42
λ> viewVL ex1 (Left 'a', True) :: Int
0

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:

λ> viewP ex2 (Right 42, True) :: Int
42
λ> viewP ex2 (Left 'a', True) :: Int
0

Another approach is to define

λ> affviewP ex2 (Right 42, True) :: Maybe Int
Just 42
λ> affviewP ex2 (Left 'a', True) :: Maybe Int
Nothing

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

λ> affviewP traverse' ["foo", "bar"]

<interactive>:_:10: error:
    • No instance for (Traversing (ForgetM [Char]))

but the viewP does fold:

λ> viewP traverse' ["foo", "bar"]
"foobar"

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!

λ> viewVL (toVL ex2) (Right 42, True) :: Int
42
λ> viewVL (toVL ex2) (Left 'a', True) :: Int
0
λ> viewP (toP ex1) (Right 42, True) :: Int
42
λ> viewP (toP ex1) (Left 'a', True) :: Int
0

#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

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

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

Site proudly generated by Hakyll