# Pointwise Lenses

Thu, 24 Apr 2014 13:54:12 GMT, by edsko.

Filed under coding.

## Pointwise Lenses

Lenses are a current hot topic in the Haskell community, with a bunch of packages providing implementations (data-accessor, fclabels, lens, amongst others). Although we will recall definitions, this post is not meant as an introduction to lenses. If you have not worked with lenses before, the talk from Simon Peyton Jones or the blog post by Sebastiaan Visser about fclabels are good starting points.

In this blog post we will propose a generalization to the lens representation used in `fclabels`

and in many other packages (with various minor variations); we will consider the relation to the representation used in `lens`

in a separate section.

If you wanted to follow along, this is the header I am using:

```
{-# LANGUAGE FlexibleInstances, RankNTypes, TupleSections #-}
import Prelude hiding ((.), id, const, curry, uncurry)
import Control.Arrow
import Control.Applicative
import Control.Category
import Control.Monad
import Control.Monad.Free
import Control.Monad.Trans.Class
import Data.Functor.Identity
import Data.Functor.Compose
import Data.Traversable
import qualified Data.Traversable as Traversable
-- We define some Show instances just for the examples
instance Show a => Show (Compose [] Identity a) where
show (Compose a) = show a
instance Show a => Show (Compose [] (Compose [] Identity) a) where
show (Compose a) = show a
instance Show a => Show (Identity a) where
show (Identity a) = show a
```

### Basics

A lens from *a* to *b* is a way to get a *b* from an *a*, and to modify an *a* given a modification of *b*:

```
data Lens a b = Lens {
lensGet :: a -> b
, lensModify :: (b -> b) -> (a -> a)
}
```

A simple example is a lens for the first component of a pair:

```
lensFst :: Lens (a, b) a
lensFst = Lens fst first
```

Importantly, lenses can be composed—they form a category:

```
instance Category Lens where
id = Lens id id
Lens g m . Lens g' m' = Lens (g . g') (m' . m)
```

### Motivation

Suppose we have a lens from somewhere to a list of pairs:

`lensFromSomewhere :: Lens Somewhere [(Int, Char)]`

We would like to be able to somehow compose `lensFromSomewhere`

with `lensFst`

to get a lens from `Somewhere`

to `[Int]`

. The obvious thing to do is to try and define

```
mapLens :: Lens a b -> Lens [a] [b]
mapLens (Lens g m) = Lens (map g) _
```

The getter is easy enough: we need to get a `[b]`

from a `[a]`

, and we have a function from `b -> a`

, so we can just map. We get stuck in the modifier, however: we need to give something of type

`([b] -> [b]) -> [a] -> [a]`

given only a modifier of type `(b -> b) -> (a -> a)`

, and there is simply no way to do that.

If you think about it, there is a conceptual problem here too. Suppose that we did somehow manage to define a lens of type

`weirdLens :: Lens [(Int, Char)] [Int]`

This means we would have a modifier of type

`weirdModify :: ([Int] -> [Int]) -> [(Int, Char)] -> [(Int, Char)]`

What would happen if we tried

`weirdModify (1 :)`

to insert one `Int`

into the list? Which `(Int, Char)`

pair would we insert into the original list?

### Pointwise lenses

What we wanted, really, is a lens that gave us a `[Int]`

from a `[(Int, Char)]`

, and that modified a `[(Int, Char)]`

given a modifier of type `Int -> Int`

: we want to apply the modifier pointwise at each element of the list. For this we need to generalize the lens datatype with a functor *f*:

```
data PLens f a b = PLens {
plensGet :: a -> f b
, plensModify :: (b -> b) -> (a -> a)
}
```

It is easy to see that `PLens`

is strictly more general than `Lens`

: every lens is also a Pointwise lens by choosing `Identity`

for *f*. Here’s a lens for the first component of a pair again:

```
plensFst :: PLens Identity (a, b) a
plensFst = PLens (Identity . fst) first
```

Note that the type of the modifier is precisely as it was before. As a simple but more interesting example, here is a lens from a list to its elements:

```
plensList :: PLens [] [a] a
plensList = PLens id map
```

You can think of `plensList`

as shifting the focus from the set as a whole to the elements of the set, not unlike a zipper.

### Composition

How does composition work for pointwise lenses?

```
compose :: Functor f => PLens g b c -> PLens f a b -> PLens (Compose f g) a c
compose (PLens g m) (PLens g' m') = PLens (Compose . fmap g . g') (m' . m)
```

The modifier is unchanged. For the getter we have a getter from `a -> f b`

and a getter from `b -> g c`

, and we can compose them to get a getter from `a -> f (g c)`

.

As a simple example, suppose we have

```
exampleList :: [[(Int, Char)]]
exampleList = [[(1, 'a'), (2, 'b')], [(3, 'c'), (4, 'd')]]
```

Then we can define a lens from a list of list of pairs to their first coordinate:

```
exampleLens :: PLens (Compose [] (Compose [] Identity)) [[(a, b)]] a
exampleLens = plensFst `compose` plensList `compose` plensList
```

Note that we apply the `plensList`

lens twice and then compose with `plensFst`

. If we `get`

with this lens we get a list of lists of `Int`

s, as expected:

```
> plensGet exampleLens exampleList
[[1,2],[3,4]]
```

and we modify pointwise:

```
> plensModify exampleLens (+1) exampleList
[[(2,'a'),(3,'b')],[(4,'c'),(5,'d')]]
```

### Category Instance

As we saw in the previous section, in general the type of the lens changes as we compose. We can see from the type of a lens where the focus is: shifting our focus from a list of list, to the inner lists, to the elements of the inner lists:

```
PLens Identity [[a]] [[a]]
PLens (Compose [] Identity) [[a]] [a]
PLens (Compose [] (Compose [] Identity)) [[a]] a
```

However, if we want to give a `Category`

instance then we need to be able to keep *f* constant. This means that we need to be able to define a getter of type `a -> f c`

from two getters of type `a -> f b`

and `b -> f c`

; in other words, we need *f* to be a monad:

```
instance Monad f => Category (PLens f) where
id = PLens return id
PLens g m . PLens g' m' = PLens (g <=< g') (m' . m)
```

This is however less of a restriction that it might at first sight seem. For our examples, we can pick the free monad on the list functor (using `Control.Monad.Free`

from the `free`

package):

```
plensFst' :: PLens (Free []) (a, b) a
plensFst' = PLens (Pure . fst) first
plensList' :: PLens (Free []) [a] a
plensList' = PLens lift map
```

We can use these as before:

```
> plensGet id exampleList :: Free [] [[(Int, Char)]]
Pure [[(1,'a'),(2,'b')],[(3,'c'),(4,'d')]]
> plensGet plensList' exampleList
Free [Pure [(1,'a'),(2,'b')],Pure [(3,'c'),(4,'d')]]
> plensGet (plensList' . plensList') exampleList
Free [Free [Pure (1,'a'),Pure (2,'b')],Free [Pure (3,'c'),Pure (4,'d')]]
> plensGet (plensFst' . plensList' . plensList') exampleList
Free [Free [Pure 1,Pure 2],Free [Pure 3,Pure 4]]
```

Note that the structure of the original list is still visible, as is the focus of the lens. (If we had chosen [] for *f* instead of *Free []*, the original list of lists would have been flattened.) Of course we can still modify the list, too:

```
> plensModify (plensFst' . plensList' . plensList') (+1) exampleList
[[(2,'a'),(3,'b')],[(4,'c'),(5,'d')]]
```

### Comparison to Traversal

An alternative representation of a lens is the so-called *van Laarhoven* lens, made popular by the lens package:

`type LaarLens a b = forall f. Functor f => (b -> f b) -> (a -> f a)`

(this is the representation Simon Peyton-Jones mentions in his talk). `Lens`

and `LaarLens`

are isomorphic: we can translate from `Lens`

to `LaarLens`

and back. This isomorphism is a neat result, and not at all obvious. If you haven’t seen it before, you should do the proof. It is illuminating.

A `Traversal`

is like a van Laarhoven lens, but using `Applicative`

instead of `Functor`

:

`type Traversal a b = forall f. Applicative f => (b -> f b) -> (a -> f a)`

Traversals have a similar purpose to pointwise lenses. In particular, we can define

```
tget :: Traversal a b -> a -> [b]
tget t = getConst . t (Const . (:[]))
tmodify :: Traversal a b -> (b -> b) -> (a -> a)
tmodify t f = runIdentity . t (Identity . f)
```

Note that the types of `tget`

and `tmodify`

are similar to types of the getter and modifier of a pointwise lens, and we can use them in a similar fashion:

```
travFst :: LaarLens (a, b) a
travFst f (a, b) = (, b) <$> f a
travList :: Traversal [a] a
travList = traverse
exampleTrav :: Traversal [[(Int, Char)]] Int
exampleTrav = travList . travList . travFst
```

As before, we can use this traversal to modify a list of list of pairs:

```
> tmodify exampleTrav (+1) exampleList
[[(2,'a'),(3,'b')],[(4,'c'),(5,'d')]]
```

However, Traversals and pointwise lenses are not the same thing. It is tempting to compare the *f* parameter of the pointwise lens to the universally quantified *f* in the type of the Traversal, but they don’t play the same role at all. With pointwise lenses it is possible to define a lens from a list of list of pairs to a list of list of ints, as we saw; similarly, it would be possible to define a lens from a tree of pairs to a tree of ints, etc. However, the getter from a traversal only ever returns a single, flat, list:

```
> tget exampleTrav exampleList
[1,2,3,4]
```

Note that we have lost the structure of the original list. This behaviour is inherent in how Traversals work: every element of the structure is wrapped in a `Const`

constructor and are then combined in the `Applicative`

instance for `Const`

.

On the other hand, the `Traversal`

type is much more general than a pointwise lens. For instance, we can easily define

```
mapM :: Applicative m => (a -> m a) -> [a] -> m [a]
mapM = travList
```

and it is not hard to see that we will never be able to define `mapM`

using a pointwise lens. Traversals and pointwise lenses are thus incomparable: neither is more general than the other.

In a sense the generality of the `Traversal`

type is somewhat accidental, however: it’s purpose is similar to a pointwise lens, but it’s type also allows to introduce effectful modifiers. For pointwise lenses (or “normal” lenses) this ability is entirely orthogonal, as we shall see in the next section.

(PS: Yes, `traverse`

, `travList`

and `mapM`

are all just synonyms, with specialized types. This is typical of using the `lens`

package: it defines 14 synonyms for `id`

alone! What you take away from that is up to you :)

### Generalizing further

So far we have only considered pure getters and modifiers; what about effectful ones? For instance, we might want to define lenses into a database, so that our getter and modifier live in the IO monad.

If you look at the actual definition of a lens in `fclabels`

you will see that it generalises `Lens`

to use arrows:

```
data GLens cat a b = GLens {
glensGet :: cat a b
, glensModify :: cat (cat b b, a) a
}
```

(Actually, the type is slightly more general still, and allows for polymorphic lenses. Polymorphism is orthogonal to what we are discussing here and we will ignore it for the sake of simplicity.) `GLens`

too forms a category, provided that `cat`

satisfies `ArrowApply`

:

```
instance ArrowApply cat => Category (GLens cat) where
id = GLens id app
(GLens g m) . (GLens g' m') = GLens (g . g') (uncurry (curry m' . curry m))
const :: Arrow arr => c -> arr b c
const a = arr (\_ -> a)
curry :: Arrow cat => cat (a, b) c -> (a -> cat b c)
curry m i = m . (const i &&& id)
uncurry :: ArrowApply cat => (a -> cat b c) -> cat (a, b) c
uncurry a = app . arr (first a)
```

The `ArrowApply`

constraint effectively means we have only two choices: we can instantiate `cat`

with `->`

, to get back to `Lens`

, or we can instantiate it with `Kleisli m`

, for some monad *m*, to get “monadic” functions; i.e. the getter would have type (isomorphic to) `a -> m b`

and the modifier would have type (isomorphic to) `(b -> m b) -> (a -> m a)`

.

Can we make a similar generalization to pointwise lenses? Defining the datatype is easy:

```
data GPLens cat f a b = GPLens {
gplensGet :: cat a (f b)
, gplensModify :: cat (cat b b, a) a
}
```

The question is if we can still define composition.

### Interlude: Working with ArrowApply

I personally find working with arrows horribly confusing. However, if we are working with `ArrowApply`

arrows then we are effectively working with a monad, or so Control.Arrow tells us. It doesn’t however *quite* tell us how. I find it very convenient to define the following two auxiliary functions:

```
toMonad :: ArrowApply arr => arr a b -> (a -> ArrowMonad arr b)
toMonad f a = ArrowMonad $ app . (const (f, a))
toArrow :: ArrowApply arr => (a -> ArrowMonad arr b) -> arr a b
toArrow act = app . arr (\a -> (unArrowMonad (act a), ()))
where
unArrowMonad (ArrowMonad a) = a
```

Now I can translate from an arrow to a monadic function and back, and I just write monadic code. Right, now we can continue :)

### Category instance for GPLens

Since the type of the modifier has not changed at all from `GLens`

we can concentrate on the getters. For the identity we need an arrow of type `cat a (f a)`

, but this is simply `arr return`

, so that is easy.

Composition is trickier. For the getter we have two getters of type `cat a (f b)`

and `cat b (f c)`

, and we need a getter of type `cat a (f c)`

. As before, it looks like we need some kind of monadic (Kleisli) composition, but now in an arbitrary category *cat*. If you’re like me at this stage you will search Hoogle for

`(ArrowApply cat, Monad f) => cat a (f b) -> cat b (f c) -> cat a (f c)`

… and find nothing. So you try Hayoo and again, find nothing. Fine, we’ll have to try it ourselves. Let’s concentrate on the monadic case:

```
compM :: (Monad m, Monad f)
=> (a -> m (f b)) -> (b -> m (f c)) -> a -> m (f c)
compM f g a = do fb <- f a
_
```

so far as good; `fb`

has type `f b`

. But now what? We can `fmap g`

over `fb`

to get something of type `f (m (f c))`

, but that’s no use; we want that `m`

on the outside. In general we cannot commute monads like this, but if you are a (very) seasoned Haskell programmer you will realize that if `f`

happens to be a traversable functor then we can flip `f`

and `m`

around to get something of type `m (f (f c))`

. In fact, instead of `fmap`

and then commute we can use `mapM`

from `Data.Traversable`

to do both in one go:

```
compM :: (Monad m, Monad f, Traversable f)
=> (a -> m (f b)) -> (b -> m (f c)) -> a -> m (f c)
compM f g a = do fb <- f a
ffc <- Traversable.mapM g fb
_
```

Now we’re almost there: `ffc`

has type `f (f c)`

, we need somthing of type `f c`

; since `f`

is a monad, we can just use `join`

:

```
compM :: (Monad m, Monad f, Traversable f)
=> (a -> m (f b)) -> (b -> m (f c)) -> a -> m (f c)
compM f g a = do fb <- f a
ffc <- Traversable.mapM g fb
return (join ffc)
```

We can use the two auxiliary functions from the previous section to define Kleisli composition on arrows:

```
compA :: (ArrowApply cat, Monad f, Traversable f)
=> cat a (f b) -> cat b (f c) -> cat a (f c)
compA f g = toArrow (compM (toMonad f) (toMonad g))
```

And now we can define our category instance:

```
instance (ArrowApply cat, Monad f, Traversable f)
=> Category (GPLens cat f) where
id = GPLens (arr return) app
GPLens g m . GPLens g' m' = GPLens (g' `compA` g)
(uncurry (curry m' . curry m))
```

Note that the `Traversable`

constraint comes up now because we need to commute the “effects” of two monads: the monad *f* from the structure that we are returning (be it a list or a tree or..) and the monad *m* implicit in the arrow. In a Traversal these two are somehow more closely coupled. In particular, if we lift a (pure) pointwise lens `PLens`

to the more general `GPLens`

, by picking `Identity`

for *f*, the `Traversable`

constraint is trivially satisfied.