# Digging into Lenses

In order to understand the haskell lens library better, I recently dug into some of the underlying types involved. The lens library is infamous for having a reputation of “works well, but the types are horrific”. So I decided to see how complicated they really were and whether I could make sense of them.

Crucially, I was very interested in how a lens could be *both* a
getter and a setter in one. How is this magic trick accomplished?

## Preliminary background

A lens is a thing that allows focusing on a part of a larger structure, and enables both getting and setting of values:

```
import Control.Lens (lens, Lens', view, set, over)
data Person = Person {
_name :: String
, _age :: Int
}
ageSetter :: Person -> Int -> Person
ageSetter p v = p { _age = v }
ageGetter :: Person -> Int
ageGetter = _age
age :: Lens' Person Int
age = lens ageGetter ageSetter
-- Pretend we're in ghci now...
>>> let roger = Person { _name = "Roger", _age = 63 }
>>> view age roger
63
>>> set age roger 23
Person { _name = "Roger", _age = 23 }
>>> over age (+1) roger
Person { _name = "Roger", _age = 64 }
```

As you can see, the `lens`

function created some object called `age`

that allows us to both set and get (or inspect and modify with `over`

)
the `_age`

field of the Person type.

This object is called a `Lens`

. How does it work?

## The Lens type

First, let’s look at the type of `Lens`

itself in Control.Lens.Type

`type Lens s t a b = forall f. Functor f => (a -> f b) -> s -> f t`

Some quick conventions on the type parameters for clarity:

`s`

is the input structure, it’s what the lens acts on`t`

is the output structure. When using`set`

or`over`

, it’s the return type`a`

is the input focus, it’s a part of`s`

`b`

is the output focus, it’s a part of`t`

There’s a simplified version of `Lens`

if you don’t actually want to change the types:

`type Lens' s a = Lens s s a a`

But we’ll look at the more complete one, because the whole point of this is to not shy away from the details of the types.

So there are a few things to notice about the `Lens`

definition above:

`forall f. Functor f`

this means your lens definition must work for*any*functor, not just some specific functor. This is really important, because different actions on the lens will make use of different functors to get your lens to do different things (more on this later).`(a -> f b)`

means that some way of injecting values into the functor will be provided to your lens. Additionally, note that it’s not necessarily equivalent to`pure`

/`return`

. It’s allowed to also do some kind of mapping from`a -> b`

as part of injecting the value into the functor. (If you don’t take advantage of this mapping, you are using a`Lens'`

)`s`

is the state coming that your lens is going to act on (no big surprise here)`f t`

is the final output. Note that:- It’s the same functor that’s given to you by the
`(a -> f b)`

function. Since we’re`forall f`

, there’s no other way to produce an instance of this functor without using that provided function. - Remember
`t`

is the modified version of`s`

so your lens must incorporate some way of going from`b -> t`

somewhere inside it (because the only way to get an`f`

is by using that function you’re given)

- It’s the same functor that’s given to you by the

## The lens function

Ok, so we know some constraints about how a Lens must work, now let’s see how to construct one.
The easiest way to make a basic lens is with the `lens`

function from Control.Lens.Lens.

The type of `lens`

is:

```
lens :: (s -> a) -> (s -> b -> t) -> Lens s t a b
-- Expanding the definition of Lens from above, we get
lens :: forall f. Functor f => (s -> a) -> (s -> b -> t) -> (a -> f b) -> s -> f t
```

Just for fun, let’s see if we can implement it just by following the types. It’s super polymorphic, so we should be able to get pretty far with that strategy:

```
lens :: forall f. Functor f =>
(s -> a) -- getter
-> (s -> b -> t) -- setter
-> (a -> f b) -- inject
-> s -- inputState
-> f t -- output
lens getter setter inject inputState = lensImpl converter injected
where
focusedValue :: a
-- (s -> a) applied to (s)
focusedValue = getter inputState -- nothing else to apply getter to!
converter :: b -> t -- we said we would need something like this
-- (s -> b -> t) applied to (s)
converter = setter inputState -- nothing else to apply setter to!
injected :: f b
-- (a -> f b) applied to (a)
injected = inject focusedValue -- again, out of options
```

Ok, at this point we’ve run out of simple functions to apply, we’re stuck with these unused parts:

`converter :: b -> t`

`injected :: f b`

There’s only one thing we can do, since we need to work for all Functors f, and the functor typeclass only gives you one function to work with:

```
fmap :: Functor f => (a -> b) -> f a -> f b
-- alias
(<$>) :: Functor f => (a -> b) -> f a -> f b
```

So lets use it:

```
lensImpl :: forall f. Functor f => (b -> t) -> f b -> f t
lensImpl converter injected = converter <$> injected
```

Ok, so let’s inline everything using equational reasoning:

```
lens getter setter inject inputState =
lensImpl converter injected
= converter <$> injected
= setter inputState <$> injected
= setter inputState <$> inject (focusedValue)
= setter inputState <$> inject (getter inputState)
```

Turns out this is the implementation in the library, just with more terse names:

```
lens :: (s -> a) -> (s -> b -> t) -> Lens s t a b
lens sa sbt afb s = sbt s <$> afb (sa s)
```

## Implementation of view

Now that we know how a lens glues together the getter and setter,
let’s look at how an action like `view`

is implemented. View allows us
to use the getter portion of the lens and is defined
in Control.Lens.Getter

`view :: MonadReader s m => Getting a s a -> m a`

Oh no, this is terrible. Now there’s monads, and some new type alias… ugh.
Alright, let’s do this one thing at a time. What’s a `Getting`

? It’s defined
in Control.Lens.Getter as well:

`type Getting r s a = (a -> Const r a) -> s -> Const r s`

Let’s inline it into our view type signature:

`view :: MonadReader s m => ((a -> Const a a) -> s -> Const a s) -> m a`

Now, in order to get rid of the `MonadReader`

thing, we’ll need to
know a trick. MonadReader is a typeclass that generalizes the
`Reader`

monad’s interface. There are lots of implementations of
`MonadReader`

, but the simplest implementation is just the partially
applied function definition `((->) e)`

. That probably sounds
confusing, but the long and the short of it is that while `view`

is
made much more flexible by being able to use anything implementing
`MonadReader`

we probably usually care about the `((->) s)`

instance. So we can simplify a bit by restricting `view`

like this:

`view :: ((a -> Const a a) -> s -> Const a s) -> s -> a`

Ok! That doesn’t look so bad after all. Now we just need to know what
the heck is going on with these `Const`

things.

In case you aren’t familiar with Const it’s defined in Data.Functor.Const and looks like this:

`newtype Const a b = Const { runConst :: a }`

Yep, it’s just got a fake second type parameter. It only stores things of type a.
Accordingly, its Functor instance declares a pretty weird `fmap`

:

```
instance Functor (Const m) where
fmap _ (Const v) = Const v
```

You might be wondering why it wasn’t defined like this:

```
fmap _ c = c
-- equivalently:
fmap _ = id
```

And the reason is because while the underlying data isn’t changed, the little phantom type parameter changes. That means you need to reconstruct the type. It’s clearer if we explicitly denote the type:

```
-- only m is actually referring to real data! a and b are ignored
fmap :: (a -> b) -> Const m a -> Const m b
```

So back to `view`

, we’ll see that this weird `fmap`

implementation is going to
be helpful to us. Let’s look at the implementation of `view`

now:

`view l = Reader.asks (getConst #. l Const)`

This is a little funky, but I’ll make two simplifications to make it easier:

`Reader.asks`

is just`id`

for the`MonadReader`

instance for`((->) s)`

so let’s get rid of it- If you look up #. after squinting at it for a bit, it’s
basically a generalization and an optimization of composition (
`.`

), so let’s pretend it’s actually`.`

for now.

`view l = getConst . l Const`

And now, let’s use our definition of `lens`

from above to understand
how the getter and setter are being used:

```
lens getter setter inject = \inject s -> setter s <$> inject (getter s)
view l = getConst . l Const
= getConst . (\inject s -> setter s <$> inject (getter s)) Const
= getConst . (\s -> setter s <$> Const (getter s))
-- let's use Const's fmap implementation to get further
-- which just ignores the mapping function entirely
= getConst . (\s -> Const (getter s))
-- do a little point-free-ing (see pointfree.io)
= getConst . (Const . getter)
= getConst . Const . getter
-- getConst . Const is equivalent to id so:
= getter
```

Something to notice here is that the lens has sort of this built-in
path for the type of `s -> a -> f b -> f t`

. And using the `Const`

functor just short circuits everything halfway through. It allows
ignoring the part that builds the structure back up again.

Wow, ok so that’s how the getter falls out. Beautiful. Let’s move on to `over`

## Implementation of over

What, `over`

? Why not `set`

first?

The answer is that `set`

and `over`

have almost identical
implementations, except that `set`

just ignores what’s currently in
the structure, and `over`

lets you look at it. We can trivially
implement `set`

with `over`

like this:

`set l val = over l (const val)`

So in the interest of not making this post even longer than it already
is, let’s just look at `over`

as defined in Control.Lens.Setter

```
over :: ASetter s t a b -> (a -> b) -> s -> t
-- We know the routine, here's the definition of ASetter
type ASetter s t a b = (a -> Identity b) -> s -> Identity t
-- Alright, go ahead and get me Identity too
newtype Identity a = Identity { runIdentity :: a }
-- And `fmap` for Identity?
fmap'Identity :: (a -> b) -> Identity a -> Identity b
fmap'Identity f (Identity a) = Identity (f a)
```

(`Identity`

comes from Data.Functor.Identity)
Which is like the most straightforward implementation of fmap you’ll ever see.
(Seriously, it’s called Identity for a reason)

So with `ASetter`

let’s expand the definition of `over`

and give it’s
implementation:

```
over :: ((a -> Identity b) -> s -> Identity t) -> (a -> b) -> s -> t
over l f = runIdentity #. l (Identity #. f)
-- rewrite #. to . (trust me it's fine here)
= runIdentity . l (Identity . f) -- Note: Identity . f is our (a -> f b)
-- inline lens implementation
= runIdentity . (\inject s -> setter s <$> inject (getter s)) (Identity . f)
= runIdentity . (\s -> setter s <$> (Identity . f) (getter s))
= runIdentity . (\s -> setter s <$> Identity (f (getter s))
-- use fmap impl for Identity
= runIdentity . (\s -> Identity (setter s (f (getter s))))
-- use pointfree.io to save me here
= runIdentity . (Identity . ap setter (f . getter))
-- composition is associative
= (runIdentity . Identity) . ap setter (f . getter)
= ap setter (f . getter)
-- sub back in the definition above
= \s -> setter s (f (getter s))
```

So after all that, the final thing looks like:

`over l f s = setter s (f (getter s))`

Which I think makes a lot of sense. We’re getting our focus out of the data structure, applying f to that value, then setting it back into the data structure, exactly as you’d expect.

Unlike with `view`

, the using the `Identity`

functor allows the lens
to do the entire dance from `s -> a -> f b -> f t`

unmolested. It just
goes around in a circle.

## Conclusion

Well, I think I’ve learned that *understanding* what the types are
doing in lens is totally doable, but I still have no clue how one
might come up with the types for Lens, or their implementations. It’s
basically dark arts as far as I’m concerned.

It did sort of dawn on me though that the magic is kind of in swapping out different Functors to hand to the lens. It makes me curious what applying lenses to more exotic functors might look like. Maybe I’ll try that.

Additionally, shout out to Chris Penner’s Optics By Example which is an amazingly thorough and well written book that got me thinking about this stuff (I have not read it all yet, but it’s been great).