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]))([[[1]], [[2, 3], [4]]])

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.

Here is a playground with all of the code from this document.

        document.querySelector('.loading-message').className = "loading-hidden";
        ga('send', 'event', 'completed', 'load', Math.round((Date.now() - startTime)/1000));
        accelerate_klipse();