Compositional data manipulation using lenses

Vesa Karvonen

About Me

  • Senior programmer — as daily hobby 1990-, as work 1996-
  • Polyglot — Asm, C++, ML, Java, Scheme, C#, Swift, JS, ...
  • Multi-paradigm — OO, FP, concurrent, reactive, logic, ...
  • Multi-platform — 16-bit, PC, Dreamcast, Mobile, Web, ...

But really

My special interest: Programming languages and techniques

``it is possible to make the structure of the program match the structure of the problem being solved.´´ — Burge

Goals

  • Get you interested in the concept of lenses 😮
  • Understand the basic idea of lenses 🤔
  • Get a sense of how lenses are implemented 🤓
  • Get a sense of the range of applicability of lenses 🤑
  • Learn to demand more from "composable" abstractions 😎

What are "lenses"?

A lens is...

a bidirectional program than can be run

  • forwards to update, and
  • backwards to extract

an element in/from a data structure.

A two-for-one bargain!

Concretely

Forward


L.set(L.prop("x"), 2, {x: 1})
            

L.modify(L.prop("x"), x => x+1, {x: 1})

Backward


L.get(L.prop("x"), {x: 1})

Forward? (1/2)

Lenses are actually mapping functions:

map :: (a -> b) -> s -> t

Like list map:

map :: (a -> b) -> [a] -> [b]

Except lifted in some fashion, e.g.

map :: Functor f => (a -> f b) -> s -> f t
map :: Profunctor p => p a b -> p s t

Forward? (2/2)

Mapping functions:

mapList :: (a -> b) -> [a] -> [b]
mapLhs :: (a -> b) -> (a, c) -> (b, c)

compose:

mapListLhs :: (a -> b) -> [(a, c)] -> [(b, c)]
mapListLhs = mapList . mapLhs
mapLhsList :: (a -> b) -> ([a], c) -> ([b], c)
mapLhsList = mapLhs . mapList

And this is how we get the direction of lenses.

Lenses generalize to optics

  • Traversals — operate on multiple focuses
  • Lenses — operate on 1 focus
  • Isomorphisms — are invertible and focus on whole

And others such as prisms, folds, getters, setters, ...

They can all share the same type (*)

And compose with each other

Let's play with...

partial.lenses

which is my optics library and used in these slides:

But there are also many other optics libraries!

// Nest, Param, Organize, Removal, Traversal, Fold, Transform
const sampleTitles = {
  titles: [{ language: "en", text: "Title" },
           { language: "sv", text: "Rubrik" }]}





L.get([], sampleTitles)

So, when and why?

When might lenses help you?

You have a data structure that...

...is more complex than just a single object or array.

And you need to update parts of that data structure.

Example scenario

  1. GET a blob of JSON from a HTTP API
  2. present an UI to edit it — using lenses
  3. PUT it back

But why lenses?

  • Simplicity — just follow the structure
  • Flexibility — use arbitrary isomorphisms, use input as is
  • Immutability — get persistence for free

But why optics?

Optics decouple the operation to perform on element(s) of a data structure from the details of selecting the element(s) and the details of maintaining data structure invariants.

In other words, a selection algorithm and data structure invariant maintenance can be expressed as a composition of optics and used with many different operations.

Compare to e.g. containers, iterators, and algorithms in the C++ STL.

An application: Data Binding

Decomposable first-class state

Atom

  • Actually stores state
  • Can be get and set
  • First-class and observable

LensedAtom

  • Does not store state
  • View of an atom through a lens

Kefir.Atom and Karet.Util libs 

var state = U.atom({
  titles: [{ language: "en", text: "Title" },
           { language: "sv", text: "Rubrik" }]})

var titleIn = language => ["titles",
                           L.find(R.whereEq({language})),
                           "text"]

var enTitle = U.view(titleIn("en"), state)
var svTitle = U.view(titleIn("sv"), state)

enTitle.log("en")
svTitle.log("sv")

state.modify(L.set(["titles", 0, "text"], "The title"))

UI sans boilerplate

Composable?

The essence of composability

What is composable?

There is a/are composition operator(s).

(+) :: T -> T -> T

There are simple universal laws that specify how they work.

x + (y + z) = (x + y) + z
zero :: T

x + zero = x
zero + x = x

Monoid is just an example!

Composing optics

  • Nesting — L.compose(...os) — Monoid (unityped)
  • Recursing — L.lazy(o => o) — Fixed point
  • Adapting — L.choices(...ls) — Semigroup
  • Querying/1 — L.choice(...ls) — Monoid
  • Querying/2 — L.chain(x => o, o) — MonadPlus
  • Picking — L.pick({...p:l}) — Product
  • Branching — L.branch({...p:t}) — Coproduct
  • Sequencing — L.seq(...ts) — Monad

Lens laws ("well behaved")


const elem = 2
const data = {x: 1}
const lens = "x"
const eq = (a, e) => R.equals(a, e) || a
R.identity({
  GetSet: eq( L.set(lens, L.get(lens, data), data), data ),
  SetGet: eq( L.get(lens, L.set(lens, elem, data)), elem )
})
(It can sometimes be useful to break some laws)

Partial Behaviour

  • View is undefined if non-existent
  • View is undefined if type-mismatch
  • Setting to undefined removes element
  • Writing an empty object or array produces undefined
  • Setting can change type

Propagating removal

Optimistic queries and updates

Finishing

Why lenses?

Prerequisite: You have a data structure to update

Optics can make it...

Links

https://github.com/calmm-js/partial.lenses

Comprehensive documentation.

Links to other libraries and resources.

https://github.com/calmm-js/partial.lenses/wiki

Additional material and examples.

Questions?