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:
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 functions.
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.