Lenses

A tool borrowed from functional programming. While lenses are used extensively in Lager for zooming on cursors, they are also useful on their own for manipulating immutable data.

Making a lens

Lenses are, conceptually, a pair of functions for focusing on a part of a whole. You use a lens with the following interface:

// pseudocode for the lens interface:
part view(lens<whole, part>, whole); // get part of a whole
whole set(lens<whole, part>, whole, part); // set the part of a whole
whole over(lens<whole, part>, whole, std::function<part(part)>); // update the part of a whole
lens<A, C> compose(lens<A, B>, lens<B, C>); // compose two lenses into another lens

Let’s use this mouse as our model:

_images/mouse.svg
struct Mouse {
    Mouth mouth;
    pair<Eye, Eye> eyes;
    vector<Leg> legs;
    vector<Whisker> whiskers;
    Tail tail;
};

So, how do we make a lens, say, to access the eyes of a mouse?

auto eyes = [](auto f) {
    return [f](Mouse mouse) {
        return f(mouse.eyes)([&](pair<Eye, Eye> eyes) {
            mouse.eyes = eyes;
            return mouse;
        });
    };
};

This is a van Laarhoven lens, which is a bit difficult to understand at first glance. Thankfully, we provide a way to generate this kind of construct with a pair of functions:

auto eyes = lager::lenses::getset(
    // the getter (Mouse -> Eyes)
    [](Mouse mouse) { return mouse.eyes; },
    // the setter (Mouse, Eyes -> Mouse)
    [](Mouse mouse, pair<Eye, Eye> eyes) {
        mouse.eyes = eyes;
        return mouse;
    });

Now, anyone can make their own lenses without knowing all the gritty metaprogramming details. Of course, writing all of these by hand is kind of a pain, so we also provide a set of lens generators for a few common patterns:

#include <lager/lenses/attr.hpp>
auto eyes = lager::lenses::attr(&Mouse::eyes);

attr will generate a lens from a pointer to member. We will go over the rest of these generators later on.

Note

The main takeaway from this is that lenses are just pure funtions.

Composition

Lenses are a fairly “new” (2007) concept, even in functional programming. One of the main struggles functional programmers faced with them is composition: back when lenses were known as Accessors, lens composition was a mess to write… Thankfully, functional programmers have since found increasingly clean ways of doing lens composition, starting with Twan van Laarhoven’s implementation, and many more to come. If you’re curious about the canonical way of doing “Optics” (a superset of lenses), I invite you to read about Profunctor Optics.

So how does all of this affect us? Simple: lens composition with VLLs (van Laarhoven lenses) is function composition!

#include <lager/lenses/attr.hpp>
auto eyes = lager::lenses::attr(&Mouse::eyes);
auto first = lager::lenses::attr(&pair<Eye, Eye>::first);
auto first_eye = [=](auto f){ return eyes(first(f)); };

Now, because doing function composition in C++ is unfortunately a bit verbose, we provide syntactic sugar for function composition through zug::comp:

#include <lager/lenses.hpp>
// all of these are equivalent:
auto first_eye = [=](auto f){ return eyes(first(f)); };
auto first_eye = zug::comp(eyes, first);
auto first_eye = eyes | first;

Zug

Zug is a C++ transducer implementation. It is used behind the scenes in Lager, but you can also use it for writing cursor transformations. It also has a few utilities you might find useful. zug::comp is one of those.

zug::comp does two things: it is able to compose any number of functions, and it wraps them so that you can use the pipe operator to compose them with any other function. All the lens generators in lager (including getset) wrap their results in a zug::comp, so you can use the pipe operator to compose lenses together.

Let’s look at an example of this in action: our mouse’s mouth has four incisors!

struct Mouth {
    using ToothPair = pair<Tooth, Tooth>;
    // lower pair and upper pair!
    pair<ToothPair, ToothPair> incisors;
};

Say our mouse has a bad tooth, and we need to replace it.

Mouse replace_tooth(Mouse mouse, Tooth tooth) {
    auto tooth_lens = attr(&Mouse::mouth)
        | attr(&decltype(Mouth::incisors)::first)
        | attr(&Mouth::ToothPair::first);
    return set(tooth_lens, mouse, tooth);
}

Another thing you might notice, is that the identity for lens composition is the identity function!

auto add4 = [](int x) { return x + 4; };
over([](auto f) { return f; }, 11, add4) // using our own identity function
over(zug::indentity, 11, add4) // using zug's identity function

struct Foo { int value; };
view(zug::identity | attr(&Foo::value), Foo{42});
view(attr(&Foo::value) | zug::identity, Foo{42});

Lens generators

Let’s look at the different lens generators that are available to us. Assume the following is available:

#include <lager/lenses.hpp>
using namespace lager;
using namespace lager::lenses;

Mouse mouse; // our instance of a mouse

We’ve already seen attr:

#include <lager/lenses/attr.hpp>
auto first_eye = attr(&Mouse::eyes)
        | attr(&pair<Eye, Eye>::first);

Eye eye = view(first_eye, mouse);

at is an accessor for an element of a collection at an index (integers for sequences like vector, keys for associative collections like map):

#include <lager/lenses/at.hpp>
auto first_whisker = attr(&Mouse::whiskers) | at(0);

optional<Whisker> maybe_whisker = view(first_whisker, mouse);

Note that the focus (part) of at is an optional. That’s because the focused element might be absent (out of bounds, no value at key, etc). We’ll go over handling optionals later. If you don’t want to handle optionals and you’re ok with using default constructed values as a representation of the absence of focus, you can use at_or:

#include <lager/lenses/at_or.hpp>

// default constructing a value if none is present:
auto with_default = attr(&Mouse::whiskers) | at_or(0);

// using a fallback value:
Whisker fallback_whisker;
auto with_fallback = attr(&Mouse::whiskers)
        | at_or(0, fallback_whisker);

auto first_whisker = with_default;
Whisker whisker = view(first_whisker, mouse);

This is usually not recommended, please use at and handle optionals properly.

Then there’s handling variants:

#include <lager/lenses/variant.hpp>

variant<Mouse, Rat> rodent;
auto the_mouse = alternative<Mouse>;

optional<Mouse> maybe_mouse = view(the_mouse, rodent);

Similarly to at, alternative’s focus is an optional.

Finally because recursive types should be implemented with boxes, we provide unbox:

#include <lager/lenses/unbox.hpp>

// a tail node has a position and maybe another tail node
struct Tail {
    int position;
    box<optional<Tail>> tail;
};

auto tail = attr(&Mouse::tail)
        | attr(&Tail::tail)
        | unbox;

optional<Tail> maybe_tail = view(tail, mouse);

Note that tail really should be of type optional<box<Tail>>, but for that we’d need to handle composing with optionals.

Handling optionals

So many optionals everywhere! How do we compose lenses that focus on optionals?

This is the part that gets slightly tricky: you can’t compose a lens that focuses on an optional with a lens that expects a value. But you can turn a lens that expects a value into a lens that expects an optional!

We provide three ways of doing this. Assume the following is available:

#include <lager/lenses.hpp>
#include <lager/lenses/optional.hpp>
#include <lager/lenses/at.hpp>
#include <lager/lenses/attr.hpp>
using namespace lager;
using namespace lager::lenses;

struct Mouse; // from earlier
struct Digit { int position; };
struct Leg {
    int position;
    vector<Digit> digits;
};

Mouse mouse; // our instance of a mouse

The first one is map_opt:

auto leg_position = attr(&Leg::position);
auto first = at(0);
auto first_leg_position = attr(&Mouse::legs) // vector<Leg>
        | first                              // optional<Leg>
        | map_opt(leg_position);             // optional<int>

optional<int> position = view(first_leg_position, mouse);

map_opt turned our lens<Leg, int> into a lens<optional<Leg>, optional<int>>. This is one way to lift lenses to handle optionals.

Now, what happens if we try to do the same thing to get the first Digit of the first Leg?

auto digits = attr(&Leg::digits);
auto first = at(0);
auto first_digit = attr(&Mouse::legs) // vector<Leg>
        | first                       // optional<Leg>
        | map_opt(digits)             // optional<vector<Digit>>
        | map_opt(first);             // optional<optional<Digit>>

optional<optional<Digit>> digit = view(first_digit, mouse);

Oh no. We got an optional of optional, which is not what we wanted. We wanted to turn our lens<vector<Digit>, optional<Digit>> into a lens<optional<vector<Digit>>, optional<Digit>>.

For this, we have bind_opt:

auto first_digit = attr(&Mouse::legs) // vector<Leg>
        | first                       // optional<Leg>
        | map_opt(digits)             // optional<vector<Digit>>
        | bind_opt(first);            // optional<Digit>

optional<Digit> digit = view(first_digit, mouse);

Note that you can lift composed lenses too!

auto first_digit = attr(&Mouse::legs) // vector<Leg>
        | first                       // optional<Leg>
        | bind_opt(digits | first);   // optional<Digit>

bind_opt collapses two levels of optional into one, much like the monadic bind of the Maybe Monad (don’t think too much about it).

For convenience, we also provide with_opt, which will automatically attempt to collapse two levels of optionals if it finds any:

auto first_digit = attr(&Mouse::legs) // vector<Leg>
        | first                       // optional<Leg>
        | with_opt(digits | first);   // optional<Digit>
optional<Digit> digit = view(first_digit, mouse);

auto first_leg_position = attr(&Mouse::legs) // vector<Leg>
        | first                              // optional<Leg>
        | with_opt(leg_position);            // optional<int>
optional<int> position = view(first_leg_position, mouse);

This should be safe to use, but be weary of using it with models that have optionals as legitimate values. Using the less ambiguous map_opt and bind_opt is preffered.

Of course, we also provide a lens for falling back to either a default constructed value or a fallback value with value_or and or_default:

auto first_leg_position = attr(&Mouse::legs) // vector<Leg>
        | first                              // optional<Leg>
        | map_opt(leg_position);             // optional<int>

auto with_default = first_leg_position | or_default; // default constructed
// auto with_default = first_leg_position | value_or(); // equivalent
auto with_fallback = first_leg_position | value_or(-1); // fallback to -1

int position = view(with_fallback, mouse);

Dynamic lenses

You’ve probably noticed that all of our lenses have the type auto in the previous examples. This is because VLLs rely on compile-time type information to implement view, set and over, and the resulting types are somewhat cryptic… This is fine for composing lenses at compile time, but here’s the catch:

struct Tail {
    int position;
    optional<box<Tail>> tail;
};

auto tail = attr(&Tail::tail) | value_or() | unbox;
auto position = attr(&Tail::position);

auto lens1 = tail | position;        // lens<Tail, int>
auto lens2 = tail | tail | position; // lens<Tail, int>

static_assert(std::is_same_v<decltype(lens1), decltype(lens2)>,
              "Not the same types!");

This means that you can’t have this kind of pattern:

auto tail_position_at(int index) {
    auto result_lens = position;
    while(index-- > 0) {
        result_lens = tail | result_lens; // won't compile, the type changed!
    }
    return result_lens;
}

We need a way to store lens1 and lens2 in the same type, because they satisfy the same interface that we defined in Making a lens (they are both, conceptually, lens<Tail, int>).

This is where type erasure comes in:

#include <lager/lens.hpp> // type erased lenses

lens<Tail, int> tail_position_at(int index) {
    lens<Tail, int> result_lens = position;
    while (index-- > 0) {
        result_lens = tail | result_lens; // this works now
    }
    return result_lens;
}

The <lager/lens.hpp> header provides a type erased lens for this very purpose. This is achieved through the same technique used for implementing std::function.

Virtual dispatch overhead

Type erased lenses are less performant at runtime, because of virtual dispatch, and because we can’t take advantage of a number of optimizations done by VLLs. For this reason, do not use type erased lenses if you can express something equivalent at compile time. (std::function suffers from similar limitations, and as such follows the same recommendations)

Let’s reimplement that last function one last time, with proper handling of optionals this time:

auto tail = attr(&Tail::tail) | map_opt(unbox);
auto position = attr(&Tail::position) | force_opt;

lens<Tail, optional<int>> tail_position_at(int index) {
    lens<Tail, optional<int>> result_lens = position;
    while (index-- > 0) {
        result_lens = tail | bind_opt(result_lens);
    }
    return result_lens;
}

Notice that we introduced force_opt. This is so that we can keep the return type as lens<Tail, optional<int>>, even in the case of a single node tail.