Please wait... The interactive code snippets on this page take a moment to render.

All the code snippets on this page are live and interactive powered by the klipse plugin.

# ■ Partial Lenses Implementation ·   This document describes a simplified implementation of lenses and traversals using a similar approach as Partial Lenses. The implementation of Partial Lenses is far from simplified. It lifts strings, numbers, and arrays to optics for notational convenience, it has been manually tweaked for size, optimized for performance, and it also tries to handle a lot of corner cases induced by JavaScript. All of this makes the implementation difficult to understand on its own. The intention behind this document is to describe a simple implementation based on which it should be easier to look at the Partial Lenses source code and understand what is going on.

There are many approaches to optics. Partial Lenses is based on the ideas described by Twan van Laarhoven in CPS based functional references and further by Russell O'Connor in Polymorphic Update with van Laarhoven Lenses.

One way to think of lenses and traversals is as being an application of a single generalized `traverse` function. The `traverse` function of the `Traversable` constructor class

``traverse :: (Traversable t, Applicative f) => (x -> f y) -> t x -> f (t y)``

is a kind of mapping function. Indeed, if you specialize the `t` type constructor to list, `[]`, and `f` to identity, you get list map:

``traverse :: {-  t = []  and  f = identity  -} (x ->   y) -> [x] ->    [y]``

`traverse` takes some kind of traversable data structure of type `t x` containing values type `x`. It maps those values to operations of type `f y` in some applicative functor using the given mapping function of type `x -> f y`. Finally it returns an operation of type `f (t y)` that constructs a new data structure of type `t y`.

The optical version of `traverse` replaces the second class `Traversable` constructor class with a first class traversal function

``type Traversal s t x y = forall f. Applicative f => (x -> f y) -> s -> f t``

and `traverse` using an optic merely calls the given traversal function

``````traverse :: Applicative f => (x -> f y) -> Traversal s t x y -> s -> f t
traverse x2yF traversal = traversal x2yF``````

A traversal function of type `Traversal s t x y` is simply a function that knows how to locate elements of type `x` within a data structure of type `s` and then knows how to build a new data structure of type `t` where values of type `x` have been replaced with values of type `y`. In other words, the traversal function knows how to both take apart a data structure in a particular way to extract some values out of it and also how to put the data structure back together substituting some new values for the extracted values. Of course, it is often the case that the type `y` is the same type `x` and type `t` is the same as `s`.

We can translate the above `traverse` function to JavaScript in Static Land style by passing the method dictionary corresponding to the `Applicative` constraint as an explicit argument `F`:

``var traverse = F => x2yF => traversal => traversal(F)(x2yF)``

Innocent as it may seem, every operation in Partial Lenses is basically an application of a traversal function like that. The Partial Lenses version of `traverse` is only slightly different due to features such as currying, built-in indexing, and the lifting of strings, numbers, and arrays to optics.

Here is an example of an `elems` traversal over the elements of an array:

``````var elems = F => x2yF => xs =>
xs.reduce(
(ysF, x) => F.ap(F.map(ys => y => [...ys, y], ysF), x2yF(x)),
F.of([])
)``````

Above, `F` is a Static Land applicative functor, `x2yF` is the function mapping array elements to applicative operations, and `xs` is an array. `elems` maps each element of the array `xs` to an applicative operation using the mapping function `x2yF` and then combines those operations using the applicative combinators `F.of`, `F.ap` and `F.map` into a computation that builds an array of the results.

To actually use `elems` with `traverse` we need an applicative functor. Perhaps the most straightforward example is using the identity applicative:

``var Identity = {map: (x2y, x) => x2y(x), ap: (x2y, x) => x2y(x), of: x => x}``

The identity applicative performs no interesting computation by itself. Any value is taken as such by `of` and both `map` and `ap` simply apply their first argument to their second argument.

By supplying the `Identity` applicative to `traverse` we get a mapping function over a given traversal:

``var map = traverse(Identity)``

In Partial Lenses the above function is called `modify` and it takes its arguments in a different order, but otherwise it is the same.

Using `map` and `elems` we can now map over an array of elements:

``````map(x => x + 1)(elems)([3, 1, 4])
``````

At this point we basically have a horribly complex version of the map function for arrays. Notice, however, that `map` takes the optic, `elems` in the above case, as an argument. We can compose optics and get different behavior.

The following `o` function composes two optics `outer` and `inner`:

``var o = (outer, inner) => F => x2yF => outer(F)(inner(F)(x2yF))``

If you look closely, you'll notice that the above function really is just a variation of ordinary function composition. Consider what we get if we drop the `F` argument:

``var o = (outer, inner) => x2yF => outer(inner(x2yF))``

That is exactly the same as ordinary single argument function composition.

We can also define an identity optic function:

``var identity = F => x2yF => x => x2yF(x)``

And a function to compose any number of optics:

``var compose = optics => optics.reduce(o, identity)``

Using `compose` we can now conveniently map over nested arrays:

``````map(x => x + 1)(compose([elems, elems, elems]))([[], [[2, 3], ]])
``````

Let's then divert our attention to lenses for a moment. One could say that lenses are just traversals that focus on exactly one element. Let's build lenses for accessing array elements and object properties. We can do so in a generalized manner by introducing `Ix` modules with `get` and `set` functions for both arrays and objects:

``````var ArrayIx = {
set: (i, v, a) => [...a.slice(0, i), v, ...a.slice(i + 1)],
get: (i, a) => a[i]
}

var ObjectIx = {
set: (n, v, o) => ({...o, [n]: v}),
get: (n, o) => o[n]
}``````

The `atOf` function then takes an `Ix` module and a key and returns a lens:

``````var atOf = Ix => k => F => x2yF => x =>
F.map(y => Ix.set(k, y, x), x2yF(Ix.get(k, x)))``````

Notice that we only use the `map` function from the functor argument `F`. In other words, lenses do not require an applicative functor. Lenses only require a functor. Otherwise lens functions are just like traversal functions.

As a convenience the `at` function dispatches to `atOf` so that when the key is a number it uses array indexing and otherwise object indexing:

``var at = k => atOf(typeof k === 'number' ? ArrayIx : ObjectIx)(k)``

We can now map over e.g. an object property:

``````map(x => -x)(at('b'))({a: 1, b: 2, c: 3})
``````

We can also compose lens and traversal functions. For example:

``````map(x => -x)(compose([elems, at('x')]))([{x: 1}, {x: 2}])
``````
``````map(x => x.toUpperCase())(compose([at('xs'), elems]))({xs: ['a', 'b']})
``````

Composing two lenses gives a lens. Composing a lens and a traversal gives a traversal. And composing two traversals gives a traversal.

We have so far only used the identity applicative. By using other algebras we get different operations. One suitable algebra is the constant functor:

``var Constant = {map: (x2y, c) => c}``

The constant functor is a somewhat strange beast. The `map` function of the constant functor simply ignores the first argument and returns the second argument as is. This basically means that after a value is injected into the constant functor it never changes. We can use that to create a `get` function

``var get = traverse(Constant)(x => x)``

that extracts the element targeted by a lens without building a new data structure during the traversal. Recall that the `map` function of the `Constant` functor actually does not use the given mapping function at all.

For example:

``````get(compose([at(1), at('x')]))([{x: 1}, {x: 2}, {x: 3}])
``````

The same lens, e.g. `compose([at(1), at('x')])`, can now be used to both `get` and `map` over the targeted element.

The constant functor cannot be used with traversal functions, because traversal functions like `elems` require an applicative functor with not just the `map` function, but also the `ap` and `of` functions. We can build applicatives similar to the constant functor from monoids and use those to fold over the elements targeted by a traversal:

``var foldWith = M => traverse({...Constant, ap: M.concat, of: _ => M.empty()})``

The above `foldWith` function takes a Static Land monoid and creates an applicative whose `ap` and `of` methods essentially ignore their arguments and use the monoid.

Using different monoids we get different operations. For example, we can define an operation to collect all the elements targeted by a traversal:

``````var collect = foldWith({empty: () => [], concat: (l, r) => [...l, ...r]})(
x => [x]
)``````
``````collect(compose([at('xs'), elems, at('x')]))({xs: [{x: 3}, {x: 1}, {x: 4}]})
``````

And we can define an operation to sum all the elements targeted by a traversal:

``var sum = foldWith({empty: () => 0, concat: (x, y) => x + y})(x => x)``
``````sum(compose([at('xs'), elems, at('x')]))({xs: [{x: 3}, {x: 1}, {x: 4}]})
``````

This pretty much covers the basics of lenses and traversals. The Partial Lenses library simply provides you with a large number of predefined lens and traversal functions and operations, such as folds, over optics.

``````