レコードとバリアントの双対性について

レコードがあればバリアントがが実装できる．

```hs
{-# LANGUAGE Rank2Types #-}
-- パターンマッチ自体をレコードとして表現する
data MatchEither a b c = MatchEither { whenLeft :: a -> c, whenRight :: b -> c }

-- レコードとして表現されたバリアント
newtype RecEither a b = RecEither { unRecEither :: forall c. MatchEither a b c -> c }

-- コンストラクタ
left :: a -> RecEither a b
left x = RecEither (\match -> whenLeft match x)

right :: b -> RecEither a b
right x = RecEither (\match -> whenRight match x)

instance (Show a, Show b) => Show (RecEither a b) where
  show m = unRecEither m (MatchEither {
                           whenLeft = \x -> "Left (" ++ show x ++ ")",
                           whenRight = \x -> "Right (" ++ show x ++ ")" })

instance Monad (RecEither a) where
  return = right
  (>>=) m k = unRecEither m (MatchEither { whenLeft = left, whenRight = \x -> k x })
```

レコードのそれぞれのフィールドを，パターンマッチのそれぞれの節だと考え，そこからひとつ選び取ることでバリアントを表現する．

## レコードなくてもλ式だけでいいんじゃない？

レコードがあればバリアントができると言うけれども，実際のところ，レコードはなくてもいい．
RecEither は `forall c. MatchEither a b c -> c` のように表現されているが，これは， `forall c. (a -> c, b -> c) -> c` のようにしても同じことであるし，カリー化して ``forall c. (a -> c) -> (b -> c) -> c`` としても，同じことである．すると `left x = \f g-> f x` となって，けっきょく，λ式だけでいいことになってしまう．

```hs
{-# LANGUAGE Rank2Types #-}
newtype LambdaEither a b = LambdaEither { unLambdaEither :: forall c. (a -> c) -> (b -> c) -> c }

-- コンストラクタ
left :: a -> LambdaEither a b
left x = LambdaEither (\whenLeft _ -> whenLeft x)

right :: b -> LambdaEither a b
right x = LambdaEither (\_ whenRight -> whenRight x)

instance (Show a, Show b) => Show (LambdaEither a b) where
  show m = unLambdaEither m (\x -> "Left (" ++ show x ++ ")") (\x -> "Right (" ++ show x ++ ")")

instance Monad (LambdaEither a) where
  return = right
  (>>=) m k = unLambdaEither m left (\x -> k x)

```

## バリアントでレコードを実装する？

双対と言うからには，バリアントを使うことでレコードが実装できそうだが，このことについて触れている文献を，いまのところ知らない．
したがってわたしの独自研究になってしまうわけで，不正確かもしれないが，こういう方法もある．

```hs
{-# LANGUAGE Rank2Types #-}
{-# LANGUAGE LambdaCase #-}

data MatchPair a b c = Fst (a -> c) | Snd (b -> c)
newtype VarPair a b = VarPair { unVarPair :: forall c. MatchPair a b c -> c }

pair :: a -> b -> VarPair a b
pair x y = VarPair (\case { Fst f -> f x ; Snd f -> f y })

fst' :: VarPair a b -> a
fst' p = unVarPair p (Fst id)

snd' :: VarPair a b -> b
snd' p = unVarPair p (Snd id)
```

こっちのほうも，やはり，たとえばペアは `\x y z -> z x y`` と実装することができるし(Church pair)，バリアントをわざわざ使う必要はない．

## 多相レコードで多相バリアントを実装

レコードでバリアントができるなら，多相レコードで多相バリアントができる．

多相レコードで多相バリアントを実装する方法は， SML# のドキュメントに書かれている．

多相レコードは， Row Polymorphism や， Haskell なら OverloadedRecordFields と呼ばれるものである．

その理屈なら， OverloadedRecordFields を使えば，多相バリアントに当たるものがつくれるはずなのだが，まだちゃんと試していない．

SML# のコードであることに注意．

```sml
fun left x match = #whenLeft match x
fun right x match = #whenRight match x
val return = right
infix 1 >>=
fun op >>=(m, k) = m { whenLeft = left, whenRight = (fn x => k x) }
```

これで left と right は多相バリアントになっている．

例としては，たとえば， left/right/middle というみっつのラベルを持つバリアントがあったとする．

```sml
fun left x match = #whenLeft match x
fun right x match = #whenRight match x
val return = right
infix 1 >>=
fun op >>=(m, k) = m { whenLeft = left, whenRight = (fn x => k x) }

fun middle x match = #whenMiddle match x
(*
 * Haskell で書くと
 * bind m k = case m of
 *              Left x -> Left x
 *              Middle x -> Middle x
 *              Right x -> k x
 *)
fun bind(m, k) = m { whenLeft = left, whenMiddle = middle, whenRight = (fn x => k x) }

(* left 1 は >>= に対しても bind に対しても使える！！ *)
val l1 = left 1
val it = l1 >>= (fn x => right x)
val it = bind(l1, (fn x => middle x))

```

## 多相バリアントで多相レコードを実装

多相バリアントで多相レコードを実装するには，次のようにすればいい．

```ocaml
let id x = x
let pair x y = function `Fst f -> f x | `Snd f -> f y
let fst p = p (`Fst id)
let snd p = p (`Snd id)

let triple x y z = function `Fst f -> f x | `Snd f -> f y | `Third f -> f z
let third p = p (`Third id)
```

```ocaml
(* fst は pair/triple のどちらに対しても使える *)
let i = fst (pair 1 2)
let j = fst (triple 1 2 3)
```

## 参考文献

[Chapter 7. SML#の拡張機能：レコード多相性 § 7.7. 多相バリアントの表現](http://www.pllab.riec.tohoku.ac.jp/smlsharp/docs/2.0/ja/Ch7.S7.xhtml)
[多相レコードで多相バリアントを表現する](http://qiita.com/dico_leque/items/db4f48f29ff863f0eb3c)