lens.lhs

レンズは余状態余モナドの余代数だった
===================================

余余余〜！別名`関数的参照`とも呼ばれる[レンズ](https://hackage.haskell.org/package/lens)はJavaのGetter, Setterと同等と[言われる](https://twitter.com/plt_borat/status/228009057670291456)関数型プログラミングのデザインパターンの一つです。
レンズは余状態余モナドの余代数だと[聞いて](https://twitter.com/hiratara/status/317602743219003392)そうなのかーと思ってたのですが、ふと自分で実装してみたくなったので **余状態余モナドの余代数** として実装してみることにしました。

ちなみにこの文章は`literate Haskell`という形式で書かれているのでダウンロードしてghciでロードすればすぐにでも自分で試すことができます。
まず最初におまじない

> {-# LANGUAGE RankNTypes #-}

コモナド(余モナド)
------------------

> class Functor w => Comonad w where
>   extract :: w a -> a
>   duplicate :: w a -> w (w a)

コモナドは圏論的にはモナドの双対の概念になっていて上の場合だと`extract`が`return`, `duplicate`が`join`と対応しています。
よく見るとそれぞれ型のドメインとコドメインがひっくり返った形になっているのがわかると思います。

余状態コモナド
--------------

> data Store b a = Store (b -> a) b
> 
> instance Functor (Store b) where
>   fmap f (Store v b) = Store (f . v) b
> 
> instance Comonad (Store b) where
>   extract   (Store v b) = v b
>   duplicate (Store v b) = Store (Store v) b

いわゆるStoreコモナドで、型だけみると値(`b`)とそれに対する処理(`b -> a`)を組み合わせたようなものになっているのがわかります。
これが余状態モナド、すなわち状態モナドの双対だというのは[この記事](http://kagamilove0707.hatenablog.com/entry/2014/11/02/210400)がとてもわかり易いです。

余代数
------

> -- Simple Lens
> type Lens' a b = a -> Store b a

代数は[F代数](https://www.wikiwand.com/ja/F%E4%BB%A3%E6%95%B0)とも言って自己関手Fに対して対象Aと射α: FA -> A の組(A, α)のことを言います。
余代数はその双対なので自己関手Fに対して対象Aと射α: A -> FAの組(A, α)のことであり`Store b`は自己関手であるので上の`Lens'`は余代数の射の型になっていることがわかると思います。
実はこれがレンズそのものではないのですがこれだけでも関数的参照の片鱗は試すことができます

> lens' :: (a -> b) -> (a -> b -> a) -> Lens' a b
> lens' get set a = Store (\b -> set a b) (get a)
> 
> get' :: Lens' a b -> a -> b
> get' l a = let Store _ b = l a
>            in  b
> 
> set' :: Lens' a b -> a -> b -> a
> set' l a = let Store v _ = l a
>            in  v

レンズを組み立てる`lens'`, 値を取り出す`get'`, 値を代入する`set'`を定義しました。
実際にタプルを例にしてレンズを作ってみましょう。

> -- Example
> _fst' :: Lens' (a, b) a
> _fst' = lens' fst setFst
>   where setFst (_, x) y = (y, x)
> 
> _snd' :: Lens' (a, b) b
> _snd' = lens' snd setSnd
>   where setSnd (x, _) y = (x, y)

```
ghci> get' _fst' (1,2)
1
```

しかしこれだとレンズを合成して使うことができず、より複雑なデータ構造に対してはまだまだ扱いづらいです。

余状態余モナドの余代数
----------------------

> -- Lens
> type Lens s t a b = forall r. (a -> Store r b) -> (s -> Store r t)

F代数全体は`(FA -> A) -> (FB -> B)`のような型を持つF代数準同型を射として圏を成します。
F余代数も同様で上の`Lens`の型はまさにF余代数準同型になっています。
これがレンズです。

> lens :: (s -> a) -> (s -> b -> t) -> Lens s t a b
> lens get set f s = let Store v r = f (get s)
>                    in  Store (\_ -> set s (v r)) r
> 
> get :: Lens s s a a -> s -> a
> get f s = let Store _ a = f (\a -> Store undefined a) s
>           in  a
> 
> set :: Lens s t a b -> s -> b -> t
> set f s b = let Store v r = f (Store (const b)) s
>             in  v r

さっきの`Lens'`に対する関数を`Lens`用に書き換えました。
実際にタプルを例に使ってみましょう。

> _fst :: Lens (a, x) (b, x) a b
> _fst = lens fst setFst
>   where setFst (_, x) y = (y, x)
> 
> _snd :: Lens (x, a) (x, b) a b
> _snd = lens snd setSnd
>   where setSnd (x, _) y = (x, y)

```
ghci> get _fst (1,2)
1
ghci> get (_fst._snd) ((1,2),3)
2
ghci> set (_fst._snd) ((1,2),3) 100
((1,100),3)
```

レンズの合成までバッチリですね！
というわけでレンズは余状態余モナドの余代数としてあらわされることがわかりました。
もしかしたら余状態余モナドの余代数準同型の方が正確かもしれませんね。
この実装はCPSのLensの実装を大いに参考にしたので[そちら](http://lpaste.net/128137)も是非のぞいてみてください。