Lensとは

Lensとは、関数型プログラミングにおいて、構造体（直積型）に対する柔軟な操作を実現するためのデザインパターンです。
Haskellでの実装はControl.Lens.Combinatorsにあります。
Lensは、特にHaskellの利用において重要な概念である一方で、なかなかイカツイ定義をしており（型パラメータが4つもある！）、その動作原理の理解に苦しむ方もいるのではないでしょうか。

type Lens s t a b = forall f. Functor f => (a -> f b) -> s -> f t

この状況を反映してか、Lensについては、既に、Web上に多数の興味深い解説記事が存在します。

しかしながら、私がLensを理解している方法をストレートに解説している記事は見つけられなかったので、本記事では、私なりの方法でLensの原理についての解説を試みます。

特に、Lensは「lens関数はgetterやsetterの組と等価である」という文脈で説明されることが多いようですが、本記事では「lens関数(a -> f b) -> s -> f tそれ自体はどういう処理なのか？」という部分に焦点を当てます。

書いているうちに結構長い記事になってしまったのですが、もしかすると一番下の「まとめ」だけ読めば大体のことはわかるかもしれません。

なお、本記事中のソースコードは、私が開発しているプログラミング言語Fix（リポジトリ, 紹介記事）で記述します。
...ちょっとまってください。本記事の内容はHaskellのLensを理解する上でも役に立つはずです。
それに、Fixの文法は誰にとっても理解しやすいものだと自負しているので、Fixを知らなくてもコードは読めるはずです。後のセクションに、本記事を理解するために知っておくべきFixの文法をまとめてあります。

Fixの文法速習

関数の型シグネチャの書き方はHaskellとほぼ同じです。

関数は|{params}| {body}のように定義します。

increment : I64 -> I64;
increment = |x| x + 1;

multiply : I64 -> I64 -> I64;
multiply = |x, y| x * y;

I64は64ビット符号付き整数の型です。

Haskellと同様、あらゆる関数は一つの引数をとり、I64 -> I64 -> I64 は実は I64 -> (I64 -> I64) の括弧を省略したものです。
上記のmultiplyの定義は以下のように書くこともできます。

multiply : I64 -> (I64 -> I64);
multiply = |x| |y| x * y;

関数適用は括弧を使って行います。もちろん関数の部分適用も可能です。

let two = increment(1);
let six = multiply(3, 2);
let mul_three = multiply(3); // 部分適用。「3倍する」関数ができる。

ピリオド演算子.は、左にある値に右にある関数を適用するものです：x.f == f(x)。
ピリオド演算子による関数適用は、括弧による関数適用よりも優先度が低いので、y.g(x)と書いた場合、これはg(x)にyを渡すことになります：y.g(x) == g(x)(y) == g(x, y)。

let six = 2.multiply(3); // `multiply(3, 2)`と同じ

関数合成の演算子はg << fおよびf >> gです：(g << f)(x) = (f >> g)(x) == g(f(x))。

Haskellの型クラスは、Fixでは「トレイト」と呼ばれます。以下はFixにおけるFunctorトレイトの定義です。

trait [f : *->*] f : Functor {
    map : (a -> b) -> f a -> f b;
}

深いsetter問題

構造体Aが構造体B型のフィールドを持っている状況を考えます。

type A = struct { b : B };
type B = struct { v : I64 };

このとき、Fixのコンパイラは、構造体AとBのsetter関数とgetter関数を自動的に定義します。

// 構造体`A`に対して：
@b : A -> B; // フィールド`b`のgetter
set_b : B -> A -> A; // フィールド`b`のsetter

// 構造体`B`に対して：
@v : B -> I64; // フィールド`v`のgetter
set_v : I64 -> B -> B; // フィールド`v`のsetter

演算子.と括弧による関数適用をうまく使うと、オブジェクト指向言語の「メソッド」のように、

// `b : B`のとき
let v = b.@v; // getter関数`@v`の呼び出し
let new_b = b.set_v(42); // setter関数`set_v`の呼び出し

と呼び出すことができます。

さて、構造体A型の値a : Aを持っているとしましょう。このとき、「aのフィールドbのフィールドvの値」を取り出すことは容易にできます：

// `a : A`のとき
let v = a.@b.@v;

しかし、aのフィールドbのフィールドvに42を設定しようとすると、困ってしまいます。スマートな書き方が直ぐには見つかりません。一つの書き方は以下のようになります。

// `a : A`のとき
let new_b = a.@b.set_v(42); // まず新しい「内側の値」を計算して、
let new_a = a.set_b(new_b); // それを外側に設定する。

「aのフィールドbのフィールドvに値を設定する」という非常によくやりそうな操作に対して、毎回これだけのコードを書くわけにはいかないですね。

これを「深いsetter問題」と呼ぶことにしましょう。

modifier関数

深いsetter問題の解決法は、構造体の各フィールドに対するmodifier関数を用意しておくことです。
構造体Aのフィールドbに対するmodifier関数とは、以下のような関数です。

mod_b : (B -> B) -> A -> A;
mod_b = |g, a| (
    let new_b = g(a.@b); // 内側の値に関数 `g` を作用させてから、
    a.set_b(new_b) // それを外側に設定する
);

要するに、フィールドの型に作用する関数g : B -> Bを受け取り、それを構造体に作用する関数mod_b(g) : A -> Aに延長する、という機能を持つのがmodifier関数です。

なお、modifier関数の動作を説明するために実装例を記載しましたが、実際にはFixのコンパイラはmodifier関数を自動実装する¹ので、ユーザが実装する必要はありません。

改めて深いsetter問題について考えます。構造体Aと構造体Bに対して、以下のようなmodifier関数が定義されています。

mod_v : (I64 -> I64) -> B -> B;
mod_b : (B -> B) -> A -> A;

これらの関数の型を並べて見ると、mod_vの出力の型であるB -> Bは、mod_bの入力の型に一致していることがわかります。よって、これらの関数を合成することができます。
また、その関数は「構造体Aのフィールドbのフィールドvに対するmodifier関数mod_bv」として期待される動作をすることが容易に理解できると思います。

mod_bv : (I64 -> I64) -> A -> A;
mod_bv = mod_b << mod_v;

つまり、setterの場合と異なり、「深いmodifier」を作ることは容易である、ということです。

さて、実はこのmodifierからsetterを作ることができます。
「値42をsetする」というのは、「「入力を無視して42を返す関数（定数関数）」を使ってmodifyする」ことに他ならないことに注意すると、

// a : A のとき
let new_a = a.mod_bv(|_| 42);

すなわち

let new_a = a.(mod_b << mod_v)(|_| 42);

と書くことができます。
なお、定数関数|_| 42の引数には、どのような文字を割り当てても構いません。Fixの慣習として「使われない値」に対しては、_という名称を使うことにしています。

これで、深いsetter問題を解決することができました。
他の言語において、単にa.b.v = 42等と書けることを考えると、まだまだ長いのは確かです。しかし、単純な規則で深いsetterを作れる方法が見つかった、という点が本質的な進展です。
これをより短く書けるようにしたいなら、演算子などをどう設計するか？という話になり、その部分は「Lensの動作原理を理解する」という目的からは離れるので、本記事では扱いません。

実は、modifier関数の時点で、既にLensの「一歩手前」です。modifierにある工夫を加えることで、Lensの定義に到達することができます。

modifier関数にはできないこと

modifier関数はsetter関数を生み出す力を持っていました。
しかし、modifier関数を使えば、構造体の更新操作が（容易に）実現できるのか、というとそうではありません。
modifier関数を使ってもうまく実現できない、構造体に対する更新操作の例を2つ紹介します。

副作用のある更新操作

引き続き、構造体Aにフィールドb : Bがある、という状況を考えます。
（ただし、しばらく、Bが構造体である必要はないので、単に「型B」と書きます。）

型Bの値にランダムなノイズを加える関数があるとします。

add_noise : Random -> B -> (Random, B);

ここで、Randomは乱数生成器の型です。
add_noise関数は、乱数生成器を受け取り、generate_I64 : Random -> (I64, Random)のような関数を使って乱数を生成し、与えられたB型の値にランダムなノイズを加えます。
そして、新しくなった乱数生成器の値と、ノイズが加わったB型の値をペアにして出力します。

さて、構造体Aのフィールドbにノイズを加えたいとします。以下のような関数になるでしょう。

add_noise_b : Random -> A -> (Random, A);
add_noise_b = |rng, a| (...);

この「...」の部分をどう実装するかが問題です。

mod_bはB -> B型の関数を受理します。しかし、add_noiseにrngを渡したものはadd_noise(rng) : B -> (Random, B)となりますが、mod_bの入力の型とうまくマッチしません。

このように、add_noiseのような「Bを変化させ、副作用とともに出力する」ような作用をmod_bを使ってA型の作用に延長することはできません。

では、mod_bをどのように変えれば、この状況に適用できそうか考えてみましょう。
入力したいのは add_noise(rng) : B -> (Random, B) で、出力としてほしいものは A -> (Random, A) です。ということで、

what_we_want_b : (B -> (Random, B)) -> A -> (Random, A);

があれば、

add_noise_b : Random -> A -> (Random, A);
add_noise_b = |rng| what_we_want_b(add_noise(rng));

のようにadd_noise_bを実装することができそうです。

what_we_want_bの型はmodifier関数と良く似ていますが、入力関数・出力関数ともに「Randomによる副作用付き」となっている点が異なります。

失敗し得る更新操作

もう一つ、mod_bがうまく使えない状況を紹介します。

「Bの値を更新しようとするが、失敗することがある」ような関数があるとしましょう。

update_or_fail : B -> Option B;

ここで、Option bは、HaskellのMaybe bのように、有効なb型の値を含むか、無効値であるか、どちらかの状態を取りえる型です。

構造体A型の値を持っていて、フィールドbをupdate_or_failで更新したいとします。この際、もしフィールドbの更新に失敗した場合は、A型の値の更新操作としても失敗扱いにしたいとします。

update_b_or_fail : A -> Option A;
update_b_or_fail = |a| (...);

やはり、この「...」の部分をどう実装するかが問題です。mod_bはB -> B型の関数を受理しますが、update_or_failの型B -> Option Bはうまくマッチしません。

再び、mod_bをどのように変えれば、この状況に適用できそうか考えてみます。
入力したいのは update_or_fail : B -> Option B で、出力としてほしいものは A -> Option A なので、

what_we_want_b : (B -> Option B) -> A -> Option A;

があれば、

update_b_or_fail : A -> Option A;
update_b_or_fail = what_we_want_b(update_or_fail);

と実装できることになります。

what_we_want_bの型はmodifier関数と良く似ていますが、入力関数・出力関数ともに「Optionによる失敗表現付き」となっている点が異なります。

Lensの発見

いよいよLensの定義に到達します！

前セクションで登場した(Random, a)やOption aはどちらもFunctorです。
念のため、実装（インスタンス化）のコードを記載しておきます²。

impl Tuple2 Random : Functor {
    // `Tuple2 : * -> * -> *`は2要素タプル型の型コンストラクタ。 
    // `Tuple2 Random` のkindは`* -> *`なのでFunctorになれる。
    map = |f, (rng, x)| (rng, f(x));
}

impl Option : Functor {
    map = |f, opt| if opt.is_none { none() } else { some(f(opt.as_some)) };
}

前セクションで登場した2つのwhat_we_want_bの型を見比べましょう。

what_we_want_b : (B -> (Random, B)) -> A -> (Random, A);

what_we_want_b : (B -> Option B) -> A -> Option A;

これらを統一する方法は明らかですね。Fixではこれにact_{field_name}という名前を付けています。

act_b : [f : Functor] (B -> f B) -> A -> f A;

上記で、fは型パラメータであって、Functorを実装した任意の（kindが* -> *の）型を受け取り、act_bをインスタンス化することができます。
f = Tuple2 Randomでインスタンス化するか、f = Optionでインスタンス化するかに応じて、act_bはどちらのwhat_we_want_bにもなることができます。

次に、act_bがどのような動作になっているべきかを考えましょう。
「副作用のある更新操作」や「失敗し得る更新操作」を実現するためには、act_bはmod_bの自然な一般化となっているべきです。そこで、まずmod_bの動作を見直します。

mod_b : (B -> B) -> A -> A;
mod_b = |g, a| (
    let new_b = g(a.@b); // 「内側の値」に関数 `g` を作用させてから、
    a.set_b(new_b) // それを外側に設定する
);

全く同じ実装のまま型宣言をact_bのものにすると、以下のコード中のコメントのような理由で型エラーとなります。

act_b : [f : Functor] (B -> f B) -> A -> f A;
act_b = |g, a| (
    let new_b = g(a.@b); // `f B`型の値ができる。
    a.set_b(new_b) // 型エラー。なぜなら：
    // `a.set_b(*)`は
    // (1) 「*」として`B`型の値を要求するが、実際には`new_b`は`f B`型の値である。
    // (2) 全体として`A`型の値を返すが、実際に作りたいのは`f A`型の値である。
);

型チェックを通すためにどのような修正が必要か考えます。
a.set_b(*)という式は、*を引数としてみるとき、B -> A型の関数となっていますが、いま欲しいのはf B -> f Aという関数です。
よって、fのFunctorとしてのmapにa.set_b(*)を渡すことでf B -> f A型の関数を作り、それにnew_bを適用すれば良さそうです。

act_b : [f : Functor] (B -> f B) -> A -> f A;
act_b = |g, a| (
    let new_b = g(a.@b); // `f B`型
    new_b.map(|star| a.set_b(star)) // `f A`型
);

（Fixらしく、map(f)(x)やmap(f, x)の代わりにx.map(f)と書いています。）

こうしてみると、act_bの動作はmod_bの動作とほぼ同じあって、単に「ファンクター版」となるようにコードを修正しただけ、ということが理解できるのではないでしょうか。

なお、modifier関数の場合と同様、Fixのコンパイラはlens関数（構造体の各フィールドに対するact_{field_name}関数たち）を自動実装する³ので、ユーザが実装する必要はありません。

act_bを実装し、例に挙げた2つのFunctorでの動作をテストするコードは以下のリンクから実行できます。
Playgroundで実行

HaskellのLens

act_bの型とHaskellのLensを見比べてみましょう。

act_b : [f : Functor] (B -> f B) -> A -> f A;

type Lens s t a b = forall f. Functor f => (a -> f b) -> s -> f t

まだ少し異なりますね。

HaskellのLens'において、

type Lens' s a = Lens s s a a

すなわち

type Lens' s a = forall f. Functor f => (a -> f a) -> s -> f s

と定義されているので、Lens'の型がact_bの型と一致していることがわかります。

では、Lensという型は一体何であるのかというと、これは、

フィールドに作用する関数gは、値だけではなく型すらも変えてしまう。
結果として、構造体の型も変わる。

という状況を扱うため、より一般化された型です。

例えば、「関数g : b -> cをタプル（ペア）型(b, a)の値の第0成分に作用させて、別のタプル型(c, a)の値を作る」というような関数の型は、以下のようになり、

act_on_pair_0 : [f : Functor] (b -> f c) -> (b, a) -> f (c, a);

この型はLens (b, a) (c, a) b cであると見なすことができます。

`f`がMonadのときの解釈

fがMonadであるようなケースでは、lens関数の動作について別の説明をすることができます。

lens関数act_b : [m : Monad] (B -> m B) -> A -> m A は、

B型の値からB型の値を作り出すMonadアクションg : B -> m Bを受けとり、
それをフィールドbに作用させるMonadアクションact_b(g) : A -> m Aを作り出す

と記述することができます。

実際、fがMonadのときに限ると、act_bは以下のような実装をすることができます。

act_b : [m : Monad] (B -> m B) -> A -> m A;
act_b = |g, a| (
    let new_b = *g(a.@b); // `g(a.@b) : m B`を実行して結果を`new_b : B`とする。
    // `g`の直前のアスタリスクに注意（後述）。
    let new_a = a.set_b(new_b); // それをフィールド`b`に設定して、新しい`A`型の値を作る。
    pure(new_a) // Monadに包む。`pure`はHaskellの`return`と同じ。
);

Playgroundで実行

ここで、Fixにおいてlet x = *action;と書くことは、Haskellにおいてdo構文の中でx <- actionとすることとほぼ同じです。

上記のact_bの実装は、アスタリスクとpureを除きほぼmod_bと同じですので、act_bは「Monadicなmod_b」であると言えることが納得できるかと思います。

念のため、上記のact_bの実装が、より前に示したFunctor版のact_bの実装と一致することを確認しておきましょう。
Fixにおいては、Monadは以下のように定義されています。

trait [m : *->*] m : Monad {
    bind : (a -> m b) -> m a -> m b;
    pure : a -> m a;
}

まず、上記のact_bの実装において、糖衣構文*を展開すると、以下のようになります。

act_b : [m : Monad] (B -> m B) -> A -> m A;
act_b = |g, a| (
    g(a.@b).bind(|new_b|
        let new_a = a.set_b(new_b);
        pure(new_a)
    )
);

Monadの構造を忘却してFunctorとみなすときは、map : (a -> b) -> m a -> m bの定義として、map(f) = bind(f >> pure)すなわちmap(f) = bind(|x| let y = f(x); pure(y))とします。
そこで、f = |star| a.set_b(star)とすれば、上のコードからbindとpureが消えて、mapだけを使った実装にすることができます。

act_b : [m : Monad] (B -> m B) -> A -> m A;
act_b = |g, a| (
    let f = |star| a.set_b(star);
    g(a.@b).map(f)
);

これは、Functor版のact_bの実装と一致しています。

よって、lens関数とは、

フィールドに対するMonadアクションを構造体全体に延長する関数であるが、
Functorの構造だけを使って実装できるので、f : Functorとしたものである。

という理解をすることもできます。

合成可能性

構造体Aが構造体B型のフィールドを持っている状況に戻りましょう。

type A = struct { b : B };
type B = struct { v : I64 };

modifier関数の重要な性質は、基本的なmodifier関数を合成することで「深いmodifier関数」を作り出すことができる点にありました。

mod_b : (B -> B) -> A -> A; // 自動定義
mod_v : (I64 -> I64) -> B -> B; // 自動定義

mod_bv : (I64 -> I64) -> (A -> A);
mod_bv = mod_b << mod_v;

この「合成可能性」とも呼ぶべき性質は、Lensになっても保たれています。

act_b : (B -> f B) -> A -> f A; // 自動定義
act_v : (I64 -> f I64) -> B -> f B; // 自動定義

act_bv : (I64 -> f I64) -> (A -> f A);
act_bv = act_b << act_v;

「Lensはgetterとsetterのペア」との関係

「Lensはgetterとsetterのペア（と等価である）」という主張は他の解説でよく言及されているので、本当に成立しているか確認しておきましょう。
具体的には、

構造体Aのフィールドbに対して、getter関数@bとsetter関数set_bが定義されていれば、そこからact_bが作れる。
構造体Aのフィールドbに対して、lens関数act_bが定義されていれば、そこからgetter関数@bとsetter関数set_bが作れる。

ということを確認します。

前半の主張は、既に示したact_bの実装例（以下に再掲します）において、構造体を操作する関数としては@bとset_bしか使っていないことから分かります。

act_b : [f : Functor] (B -> f B) -> A -> f A;
act_b = |g, a| (
    let new_b = g(a.@b); // `f B`型
    new_b.map(|star| a.set_b(star)) // `f A`型
);

lens関数からsetter関数が作れることは、直感的には明らかかもしれません。modifier関数からsetter関数を作れることは既に見ましたし、lens関数はmodifier関数の一般化であるためです。
実際、任意の型aに対してf a = a、map(g) = gとなるようなFunctor fでact_bをインスタンス化すれば、act_b : (B -> B) -> A -> Aとなり、これはmodifier関数と全く同じ動作をします。
ただし、実際には、型システムの制約上、このようなFunctorを定義することはできません。そこで、目的のものと自然に同型なFunctorであるIdentityを定義して使います。同型を与える自然変換は @data : Identity a -> a です。

// Identityファンクターを作る
type Identity a = struct { data : a };
impl Identity : Functor {
    map = |f, Identity { data : x }| ( Identity { data : f(x) } );
}

// `@data : Identity a -> a`の逆変換
eta : a -> Identity a;
eta = |x| Identity { data : x };

// lensからmodifierを作る
// 自動定義される`mod_b`と名前が衝突しないように`my_mod_b`とする
my_mod_b : (B -> B) -> A -> A;
my_mod_b = |g, a| (
    // `act_b`を`f = Identity`でインスタンス化すると、
    // `act_b : (B -> Identity B) -> A -> Identity A`となる。
    // これに`g`を渡すため、`eta : B -> Identity B`を合成
    let h = g >> eta;
    let id_a = a.act_b(h); // lens関数の呼び出し。結果は`Identity A`型
    id_a.@data // `@data`を使って`Identity`から取り出す
);

// modifierからsetterを作る
my_set_b : B -> A -> A;
my_set_b = |b| my_mod_b(|_| b);

Playgroundで実行

次に、lens関数からgetter関数を作る方法を考えます。

act_b : [f : Functor] (B -> f B) -> A -> f Aを使って最後にB型の値が欲しいので、f A = Bとなるようなファンクターfでact_bをインスタンス化するとよさそうです。
そこで、任意の型aに対してf a = B、map(g) = id_BとしたFunctor fでact_bをインスタンス化すると、act_b : (B -> B) -> A -> B となります。
この関数の動作はact_b(g) = |a| g(a.@b)であるため、act_bに恒等関数を渡すとgetter関数そのものになることがわかります。

実際には、型システムの制約上、任意の型aに対してf a = BとなるようなFunctorを定義することはできません。そこで、目的のものと自然に同型なFunctorであるConstantBを定義して使います。同型を与える自然変換は @data : ConstantB a -> B です。

// `ConstantB`ファンクターを作る
type ConstantB a = struct { data : B };
impl ConstantB : Functor {
    map = |f, cb| ConstantB { data : cb.@data }; // map(f)はすべて`ConstantB`上の恒等関数
}

// `@data : ConstantB a -> B`の逆変換
eta : B -> ConstantB a;
eta = |b| ( ConstantB { data : b } );

// lensからgetterを作る
my_get_b : A -> B;
my_get_b = |a| (
    // `act_b`を`f = ConstantB`でインスタンス化すると、
    // `act_b : (B -> ConstantB B) -> A -> Constant B` となる。
    // `eta`による同一視`ConstantB B = B`のもとで`id_B : B -> B`を渡したいので、
    // `eta`そのものを渡す。
    let b = a.act_b(eta); // lens関数の呼び出し。結果は`ConstantB A`型
    b.@data // `ConstantB A`から値を取り出す
);

Playgroundで実行

まとめ

構造体type A = struct { b : B };の各フィールドbに対して、lens関数act_b : [f : Functor] B -> f B -> (A -> f A)が定義される。
これは「フィールドへの作用を構造体への作用に延長する関数」mod_b : (B -> B) -> A -> AのFunctor版であると考えることができる。
特に、fがMonadのときは、lens関数は「フィールドへのMonad作用を構造体へのMonad作用に延長する関数」であると考えることができる。この動作を実装するにあたってFunctorとしての構造mapしか使わないので、f : Functorを要求するだけでよい。
lens関数は合成可能である：型Bも構造体でフィールドvを持つとき、フィールドbのフィールドvに対するlens関数act_bvは、act_vの後にact_bを合成すれば作り出すことができる。
getter関数A -> Bとsetter関数B -> A -> Aからlens関数を作り出すことができる。lens関数からgetter関数とsetter関数を作り出すこともできる。
HaskellのLensの定義type Lens s t a b = forall f. Functor f => (a -> f b) -> s -> f tは、フィールドに作用する関数gが値だけではなく型すらも変えてしまう（フィールドの型が変わるので、それを含む構造体の型も変わる）場合にも対応するためのもの。

Fixの宣伝

もしこの記事を読んで「Fixって悪くなさそうな言語だな」と思ったら、ぜひ使ってみてください。

また、Copy on write 最適化の観点で、記事中に挙げた実装例よりも効率の良いコードが生成されます。 ↩
これらの実装（あるいはより一般的な実装）はFixの標準ライブラリの中ですでに行われているので、実際にユーザ自身がこの実装を書くことはできません。 ↩
また、modifier関数の場合と同様に、記事中に挙げた実装例よりも効率の良いコードが生成されます。 ↩