RowToListで型プログラミングをやってみた話

さいきんC#でgenericの再帰定義を使った型遊びをしていたのですが、これって型レベルプログラミングの一種なのでは？と気づいてそろそろ型レベルの概念をちゃんと覚えたくなってきたところに、@hiruberutoさんの「[RowToListであそぼう！（苦悶）](https://qiita.com/hiruberuto/items/9880beeae40d693da06d)」というたのしい記事を見て「こんなことまでできるのか！」と興味を持ったのでぼくもRowToListで遊んでみることにしました。

# propsってFFI使わないで定義できるのでは？
元記事のpropsはかなり使えそうな形をしていますが、対象が`Aff`固定なのと、実装がJavaScriptのFFIなのが気になりました。ぼくはJavaScriptを1行も書いたことがないのでこれからも1行も書かないまま生きていたいのです。
それは置いといて、要するに`{ x :: m a, y :: m b }`を`m { x :: a, y :: b }`にできればいいわけです。この形ってなんか見覚えがあるような？`sequence :: t (m a) -> m (t a)`ですね。つまりRecordに対するTraversableみたいなものをつくればいいということだ！

一筋縄ではいかなかったですが、なんか、できました。
ついでにいろいろな知見を得られたので最後に書いています。

## まずは全てのコードから

```haskell
class RowTraversable list xs ys m f | list -> ys m where
  traverseRow :: (RLProxy list) -> (m ~> f) -> { | xs } -> f { | ys }

instance rowTraversableNil :: Applicative f => RowTraversable RL.Nil xs () m f where
  traverseRow _ _ _ = pure {}

instance rowTraversableCons ::
  ( IsSymbol key
  , Row.Cons key (m a) xs' xs
  , Row.Cons key a ys' ys
  , Row.Lacks key ys'
  , RowTraversable tail xs ys' m f
  , Applicative f
  ) => RowTraversable (RL.Cons key (m a) tail) xs ys m f where
  traverseRow _ f obj = Record.insert key <$> f (Record.get key obj) <*> traverseRow tail f obj
    where
    key = SProxy :: SProxy key
    tail = RLProxy :: RLProxy tail

sequenceRow
  :: forall rowList mr r m
  .  RL.RowToList mr rowList
  => RowTraversable rowList mr r m m
  => { | mr } -> m { | r }
sequenceRow = traverseRow (RLProxy :: RLProxy rowList) identity

props
  :: forall rowList mr r m f
  .  RL.RowToList mr rowList
  => RowTraversable rowList mr r m f
  => Parallel f m
  => { | mr } -> m { | r }
props = sequential <<< traverseRow (RLProxy :: RLProxy rowList) parallel
```

とりあえず解説は後にして、

## 使ってみる

```haskell
 -- {x :: Maybe Int, y :: Maybe String } -> Maybe { x :: Int, y :: String }
> sequenceRow { x: Just 123, y: Just "abc" }
Just { x: 123, y: "abc" }

> sequenceRow { x: Just 123, y: Nothing :: Maybe String }
Nothing -- 1個でもNothingがあればNothingになる

-- Arrayの場合でも……？
> sequenceRow { x: [1, 2, 3], y: ["a", "b"] }
[{ x: 1, y: "a" },{ x: 1, y: "b" },{ x: 2, y: "a" },{ x: 2, y: "b" },{ x: 3, y: "a" },{ x: 3, y: "b" }]
```

`props`くんは元記事と同じ動きをします。`Parallel`に一般化してるのでAff以外も入ります！

## classの定義

```haskell
class RowTraversable list xs ys m f | list -> ys m where
  traverseRow :: (RLProxy list) -> (m ~> f) -> { | xs } -> f { | ys }
```

`list`はRecordの`RowList`、`xs`と`ys`は変換元/変換先のrow、`m`と`f`はコンテナの型です。
ふつうの`traverse`は`a -> m b`の関数を取って全ての要素を変換できるんですが、Recordの場合は`a`の型が一つにならないので、代わりに`m ~> f`を置いてみました。わりと便利。かも。
`list -> ys m`はFunctional Dependenciesの定義で、型のinputとoutputを区別します。今回は`list`が決まれば残りが一意に定まるという意味で、つまり、classのパラメータのうち`ys` `m`は「出力変数」ってことになりますね。これを「型の関数」と見なして悪用するのが型レベルプログラミング……ということなのかしら？

## インスタンスの定義

```haskell
instance rowTraversableNil :: Applicative f => RowTraversable RL.Nil xs () m f where
  traverseRow _ _ _ = pure {}

instance rowTraversableCons ::
  ( IsSymbol key
  , Row.Cons key (m a) xs' xs
  , Row.Cons key a ys' ys
  , Row.Lacks key ys'
  , RowTraversable tail xs ys' m f
  , Applicative f
  ) => RowTraversable (RL.Cons key (m a) tail) xs ys m f where
  traverseRow _ f obj = Record.insert key <$> f (Record.get key obj) <*> traverseRow tail f obj
    where
    key = SProxy :: SProxy key
    tail = RLProxy :: RLProxy tail
```

うわーすごい。わけがわからん。一つずつ追っていきます。

### 再帰的定義

#### Nil

まず`RowList`は`key :: Symbol`と`value :: Type`のペアを1要素とした再帰リストとなっているので、これを`RL.Cons`を使ったパターンマッチで型定義のところで分解しています。そうすると、再帰定義の終端があるわけで、それが、

```haskell
RowTraversable RL.Nil xs () m f
```

です。
`RL.Nil`が「空のRowList」で、これにマッチしたとき`ys`が`()`になる、という定義です。
関数の実装は、

```haskell
traverseRow _ _ _ = pure {}
```

で、RowListが空なんだから空のRecordを返せばよいということですね。後々このnewobjを元にRecordを構築することになります。

#### Cons

Cons側のインスタンス定義は、

```haskell
instance rowTraversableCons ::
  ( IsSymbol key
  , Row.Cons key (m a) xs' xs
  , Row.Cons key a ys' ys
  , Row.Lacks key ys'
  , RowTraversable tail xs ys' m f
  , Applicative f
  ) => RowTraversable (RL.Cons key (m a) tail) xs ys m f
```

constraint多すぎてわけがわからない……一つずつ追います。

まずは`IsSymbol key`ですが、これは`key`が`Symbol`であることを表していて、`Symbol`を用いる関数を呼ぶために必要となる制約です。直接の仕組みには関係ないものです。

次の`Row.Cons`については、2つの役割があります。一つは「分解」で、`Row.Cons key (m a) xs' xs`の行は「`xs`と`key`が定まっている時に、`(m a)`と`xs'`が取り出せる」という意味になります。`xs'`には`xs`から`key`の要素を取り除いたものが入ります。Listのパターンマッチで使う場合のconsですね。

もう一つの役割は「結合」で、`Row.Cons key a ys' ys`の行では結合の用途で使っています。「`ys'`があるときに`key`と`a`を渡すと、`ys`を取得できる」というもので、これはListを結合するときのconsに相当します。

と、ここでようやくRowListの使い道に気づいたんですが、`Row.Cons`はあくまで「`key`があらかじめ分かっている場合」に使えるもので、rowから「`key`を取り出すことはできない」のです。そこで、`RowToList`でrowをRowListに変換することで初めて未知の`key`を取り出すことができるようになるのです。これは便利。

次の`Row.Lacks key row`は、rowに対して`key`の項目が存在しないことを保証する制約です。こちらも実装側の関数を呼ぶために必要になっています。

最後の`RowTraversable tail xs ys' m f`が再帰的なパターンマッチです。`tail`はRowListから1つ目の要素を取り出した残り(この後に書いてます)で、これを`xs`といっしょに渡すと`ys'`が返ってくるということを宣言しています。マッチする度にtailが減っていくので、最終的には`RL.Nil`にマッチします。そのときに`ys'`が`()`となるので、そこから戻ってくるときに`Row.Cons key a ys' ys`で1個ずつ結合していくことになります。

そしてインスタンスの定義ですが、

```haskell
RowTraversable (RL.Cons key (m a) tail) xs ys m f
```

これは、与えられた`list`を`RL.Cons`でその場で分解しています。ここで未知の`key`と`m a`を取得し、さらに`key`を取り除いた後の`tail`が手に入ります。すごい！定義に書かれた通り、要素の型が`m a`であるときだけマッチするので、この再帰定義は全てのrow要素が`m なんとか`であるときだけ成立します。それ以外ではコンパイルエラーになる！すごいすごい！`m`は定義中で固定していますが、`a`にはどの型が入っていても成り立ちます。

ここでいったん型変数を整理しましょう。
パターンマッチ時に最初から与えられている型は`key` `m` `a` `tail` `xs`の5つです。前の4つは事前に`xs`から作られる`list :: RowList`を`RL.Cons`で分割するだけで得られるので、実質の型情報の大本は`xs`になりますね。`RL.Cons`のパワーがすごい。ここから`ys`の型を確定させなければなりません。
次に、`RowTraversable tail xs ys' m f`の制約によって`tail`から`ys'` `m`が取得できます。わからなかったら上に書いてあるfundepの定義をもう一度見てみてください。
最後に、`Row.Cons key a ys' ys`の制約によって`ys`が決まります。
これで定義に必要な型情報が手元に揃いました。

* input: `key` `m` `a` `tail` `xs`
* output: `xs'(使用しない)` `ys'` `ys`

`f`に関しては、`traverseRow`の引数によって指定されるためunknownのままで良いようです。わからない……。

ここから関数の定義ですが、

```haskell
traverseRow _ f obj = Record.insert key <$> f (Record.get key obj) <*> traverseRow tail f obj
  where
  key = SProxy :: SProxy key
  tail = RLProxy :: RLProxy tail
```

Applicativeで大分アレな見た目ですけど、単に「`tail`から作ったnewobjに対して、objから`Record.get`で手に入れた値を`f`にくぐらせて、`Record.insert`で挿入」というのをしているだけです。`traverseRow tail f obj`は最終的に`RL.Nil`にマッチして`{}`を返すので、再帰の戻り際に逆順で挿入を繰り返していることになります。
`SProxy`はSymbolのProxy、`RLProxy`はRowListのProxyです。Proxyは簡単に言うと型情報を関数の引数として渡すための入れ物ですね。例えば`Nothing :: Maybe a`を引数に渡すと、値はただの`Nothing`ですがこっそり型`a`の情報を渡せる、みたいなイメージです。

ここで、Record操作による構築を行っていますが、Record系の関数を扱うにはrowの挿入や要素の抽出を型安全に行うために`IsSymbol`や`Row.Cons`、`Row.Lacks`による制約を付ける必要があります。`obj :: Record xs`に対して`Record.get`を行うためには`Row.Cons key (m a) xs' xs`が必要なのはなんとなく分かるんじゃないでしょうか。そして、`newobj :: Record ys'`に対する`Record.insert`を行うには、`Row.Cons key a ys' ys`に加えて`Row.Lacks key ys'`が必要になります。`ys'`に`key`が存在しない場合に限り、`key a`の要素をinsertできて`ys`が得られる、という意味になります。

## 使える

まずは冒頭に書いた`sequence :: t (m a) -> m (t a)`に相当するものを作りました。

```haskell
sequenceRow
  :: forall rowList mr r m
  .  RL.RowToList mr rowList
  => RowTraversable rowList mr r m m
  => { | mr } -> m { | r }
sequenceRow = traverseRow (RLProxy :: RLProxy rowList) identity
```

ここでようやく`RowToList`が出てきました。関数の引数は`{ | mr }`で、これは「`mr`のrowで構成されたRecord型」を表していて、つまり普通のRecordです。ここから`mr`を手に入れることができて、それを`RL.RowToList mr rowList`で`rowList`に変換しています。`mr`は`# Type`で、`rowList`は`RowList`なので種類が違うのです。`rowList`が手に入ってしまえば、あとはさっき定義した`RowTraversable`に放り込むだけです。`traverseRow`の引数`m ~> f`は、この場合は`identity`を渡します。これで、`{ x :: m a, ... } -> m { x :: a, ... }`という面白関数を最初から最後まで型安全で実装することができました。わーい！

```haskell
props
  :: forall rowList mr r m f
  .  RL.RowToList mr rowList
  => RowTraversable rowList mr r m f
  => Parallel f m
  => { | mr } -> m { | r }
props = sequential <<< traverseRow (RLProxy :: RLProxy rowList) parallel
```

`props`のほうは、`m ~> f`に`parallel`を渡して、まとめた後に`sequential`で戻す、をやってるだけなのでほとんど一緒ですね。

# くるしい
これだけを書くのに何時間意味不明なエラーメッセージを見続けたのであたまがおかしくなってしまった。
でもこれを書いてから急にRowToList系の定義が読めるようになったので得られたものは思ったより多かった。MultiParamTypeClassが型の変換ルールを記述しているというのが見えるようになったのが大きい。
型でプログラミングするときに重要なのは、「どの型があらかじめ与えられていて、どの型が計算されるものか」を見極めることだということを理解するまでに時間を掛けすぎたのだ……。

# さんこう
PureScriptに関しては、@hiruberutoさんがちょう丁寧に解説してるので、記事全部読むのがいいと思います。型レベルの話だとJustin-san(@kimagure)が最先端でいつも何言ってるのか全然わからないんですけど、それ以前に英語よめないマンなのでむしろソースコード直読みがめちゃ参考になりました。[purescript-simple-json](https://github.com/justinwoo/purescript-simple-json)が素晴らしい。どうかしてる。

# おわり
* RowToListはrowから未知の`key`を取り出すための手段
* 「与えられた型」と「計算された型」を区別し、見極める
    * fundepの定義はinの型とoutの型を見分ける唯一の方法
* `Row.Cons`は分解と結合の両方に用いる
* Recordを操作するには`purescript-record`の関数を使おう
* 型安全なRecord操作をするには`Row.Cons`や`Row.Lacks`による正しい制約が必要
* Proxyは型の情報を渡したいけど値は別に要らないときに使うもの
    * kindの種類によって`Proxy`とか`SProxy`とか`RProxy`とか`RLProxy`とかいろいろある
* 型レベルプログラミングわからない。人間の書くものじゃない。

全体のコードは[ここに置いてます](https://gist.github.com/acple/72b27e9c143a861c7f3356a7664e30a9)