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)

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:

  1. Reader.asks is just id for the MonadReader instance for ((->) s) so let’s get rid of it
  2. 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).