Lenses and Traversals as Composable Immutable Accessors

Immutable data has one recurring ergonomic problem. Reading a field nested three levels deep is a chain of projections; writing one requires rebuilding every structure on the path, and the rebuild is written out by hand at each call site. A lens packages the read and the write into one value so that the path can be named once, composed with other paths, and reused. The interesting part is that the packaged value is an ordinary function, and the composition of lenses is ordinary function composition.

The naive pair, and why it is not enough

The obvious encoding of a field accessor is a getter and a setter:

data Lens s a = Lens { get :: s -> a, set :: a -> s -> s }

This works for a flat record and composes awkwardly. Composing two such pairs requires writing the composition by hand, and the composition of a getter with a getter is easy while the composition of a setter with a setter requires the outer setter to rebuild the outer structure around the inner setter’s result. The result is correct and the code is longer than the projection it replaces.

The pair also cannot express a traversal: an accessor that focuses on zero or more targets, such as every element of a list. A traversal’s getter must collect the targets into some structure, and its setter must accept that structure and distribute the elements back over the original, which is a different pair of types for each accumulation, so the two cannot share one combinator.

The van Laarhoven encoding solves both problems by generalizing over the functor that carries the result.

The encoding

A lens from s to a is a function that, given a way to modify a inside a functor f, produces a modified s inside the same functor:

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

view :: Lens s a -> s -> a
view l = runIdentity . l Identity

over :: Lens s a -> (a -> a) -> s -> s
over l g = runIdentity . l (Identity . g)

The type is the whole definition. The caller supplies a function a -> f a that both transforms the target and wraps it in an effect; the lens applies that function at the focus and rebuilds the structure, using fmap to carry the effect through the rebuilt parts. view chooses f = Identity so the effect is trivial; over chooses the same functor with a transformation inside it.

For a pair, the lens is two lines:

_1 :: Lens (a, b) a
_1 f (x, y) = (\x' -> (x', y)) <$> f x

_2 :: Lens (a, b) b
_2 f (x, y) = (\y' -> (x, y')) <$> f y

The <$> is where the rebuilding happens, and it is the only place the structure is touched. For a record with named fields the same shape applies, with the constructor applied to the transformed field and the other fields unchanged.

Composition is function composition

Two lenses compose with (.), and the types line up because the encoding is a function type:

_1_2 :: Lens ((a, b), c) b
_1_2 = _1 . _2

Read the composition operationally: _1 . _2 first takes the first component of the outer pair, which is the inner (a, b), and then takes the second component of that, which is the b. The modifier is applied at the b, and the rebuilding happens on the way out: the inner pair is rebuilt around the new b, then the outer pair is rebuilt around the new inner pair. The result is a lens whose focus is the nested field, and it was built without any knowledge of the record’s shape beyond the two component lenses. Composition is associative and has an identity (id is the lens that focuses on the whole value), so lenses form a category, and that is the formal reason composition works.

The practical consequence is that a deep path can be named once and used for reading, writing, and modifying:

data Config = Config { server :: Server, name :: String }
data Server = Server { host :: String, port :: Int }

serverL :: Lens Config Server
serverL f (Config s n) = (\s' -> Config s' n) <$> f s

portL :: Lens Server Int
portL f (Server h p) = (\p' -> Server h p') <$> f p

portOf :: Lens Config Int
portOf = serverL . portL

view portOf cfg reads the port, over portOf (+1) cfg increments it and returns a new Config, and set portOf 8080 cfg replaces it, where set l v = over l (const v). Each of the three allocates the Config and Server nodes on the path, which is the same cost as the hand-written update, and the code at the call site does not mention the intermediate structures.

The functor is the effect

The f in the type is not incidental. Different choices of functor give different accessors from the same combinator.

Identity gives a plain read or update, as above.

Const gives a read-only accessor. Const a is a functor whose fmap discards the function and keeps the accumulated value, so l Const walks to the focus and returns the value without rebuilding anything. This is how view is implemented in practice: the functor carries the answer and the rebuild is dead code that the optimizer removes.

Const with a monoid gives a fold. If the functor accumulates a monoid, l visits every focus and combines the results, which is the traversal’s read.

A state or IO functor gives an effectful update: the modifier can perform effects while transforming the focus, and the lens rebuilds the structure around the results.

This is the same trick as the free monad’s interpreter and the same as the continuation encoding: one type, several meanings selected by the type argument. The difference is that the lens’s meaning is selected by the functor instance rather than by a handler, which is why the lens has no interpreter and why the laws are the only thing that constrains it.

Traversals, and the difference from a lens

A traversal focuses on zero or more targets and is defined with Applicative rather than Functor:

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

each :: Traversal [a] a
each f []     = pure []
each f (x:xs) = (:) <$> f x <*> each f xs

The Applicative constraint is what allows the effects to be combined in order: <$> sequences the head’s effect and <*> sequences the tail’s, and the Applicative instance decides whether the combination is a list of results (non-determinism), an accumulated log, a short-circuit, or a plain rebuild. The traversal therefore does the work of mapM, filterM, and a fold in one combinator.

A lens is a traversal that focuses on exactly one target, and the type reflects it: Functor is enough when the number of targets is fixed at one, and Applicative is required when it is not. Composition of a lens with a traversal is a traversal, and composition of two traversals is a traversal, so the general type is the traversal and the lens is the special case.

The cost of the traversal is the Applicative dictionary and the allocation of the intermediate applicative structure. For a list of n elements, the naive definition builds a chain of n applicative computations and the instance combines them, which is work a hand-written map does not do. The optimizer removes most of it for the common instances, and a traversal over a large structure can cost more than a hand-written loop when it does not.

The laws, and the fact that nothing checks them

A lens is lawful when it satisfies three equations, stated in terms of view, set, and over:

view l (set l v s)      = v
set l (view l s) s      = s
set l v (set l w s)     = set l v s

The first says the getter and setter agree. The second says setting the current value changes nothing. The third says the last write wins. Together they say the lens is a well-behaved accessor: it focuses on a location, and the location is stable under writes. The laws are stated for total values; a lens over a partial structure, such as a field of a Maybe, is lawful only with respect to the inputs on which both sides are defined.

Nothing in the type enforces them, and a violation is not a compile error. A lens whose setter writes the field it is given but silently drops a second field fails the second law, because setting the value read back produces a different structure from the one it started from, and the failure shows up only at the call site that composes it. The laws are a specification the programmer must check, and the consequence of a violation is that a composition of optics behaves unexpectedly at a distance.

The van Laarhoven encoding makes the laws harder to violate than the pair encoding, because a single function must serve as both getter and setter, and the getter’s behaviour is derived from the setter’s by choosing Const. That is a real advantage, and it is not a proof: the constraint is only that the two views of the value agree, and a function that satisfies the type can still be a lens in form and not in law.

Performance, and the representation change

A composed lens is a chain of function calls, one per component, and each call rebuilds one layer of the structure. For a path of depth d, an update allocates d nodes, which is the same as the hand-written version, and the call overhead is d indirect calls that the optimizer inlines when the lens is a top-level definition with a visible unfolding. A lens stored in a data structure or passed through a function boundary may not inline, and the cost becomes a real indirect call per level.

The Const-based read has a subtler cost. view walks the whole path with a functor whose fmap discards the function, so the rebuild is dead code; a compiler that inlines the lens and simplifies removes it entirely. A compiler that does not leaves the rebuild in place, and the read allocates the structure it then discards. This is why the same lens can be free in one module and expensive in another.

The profunctor encoding addresses a different problem: a single value composes with optics of another kind without the Functor/Applicative constraint selected at each use site, because the composition operator is the same for a lens, a traversal, a getter, or a setter. The cost is a more complicated type and a heavier dependence on the compiler’s ability to resolve the profunctor constraints. The two encodings are equivalent in expressive power, which is the content of the Pickering–Gibbons–Wu result, and the choice between them is a choice of which constraints the compiler handles better.

The final point is the same one that applies to every abstraction in this cluster. A lens is a naming device for a path through immutable data, and it pays when the path is used more than once and composed with other paths. For a single update in a single function, the record syntax is shorter and allocates the same nodes. For a library that exposes an interface over data it does not own, the lens is the interface: it lets a caller focus on a field without knowing the surrounding type, and that is the same separation of concerns that higher-order functions provide for traversal. The monadic version of the same idea is the effectful update, where the modifier performs actions while the lens rebuilds the structure around their results.