多相レコードで多相バリアントを表現する

SML# のマニュアルには、多相レコードで多相バリアントを表現する方法が説明されているがどうもわかりにくいらしい。もう少し単純な例から始めてみよう。

レコードでバリアントを表現する

まず、多相でないレコードでバリアントを表現することを考える。

datatype t = Int of int | String of string

この型の値について、 Int であればその値を、 String であれば文字列の長さを返す関数を考える。

fun f (Int i) = i
  | f (String s) = String.size s

case を使って書くとこうなる。

fun f x = case x of
              Int i => i
            | String s => String.size s

これを一般化して、各場合の処理を関数として受け取るようにしよう。

fun tCase x caseInt caseString =
    case x of
        Int i => caseInt i
      | String s => caseString s

fun f x = tCase x (fn x => x) String.size

さらに、 caseInt, caseString の組をレコードで受け取るようにする。

type 'a tcont = { caseInt : int -> 'a, caseString : string -> 'a }

fun tCase x cases =
    case x of
        Int i => #caseInt cases i
      | String s => #caseString cases s

fun f x = tCase x { caseInt = (fn x => x),  caseString = String.size }

もとあった t の内部表現はどうでもいいのでバリアントタグ自体を関数で表現することにする。

fun Int i = fn (cases : 'a tcont) => #caseInt cases i
fun String s = fn (cases : 'a tcont) => #caseString cases s

fun tCase x cases = x cases
fun f x = tCase x { caseInt = (fn x => x),  caseString = String.size }

という感じで、バリアント型の値は、「各場合を扱う関数（各場合の継続）の組」を受け取り「継続を選択して値を引き渡す」関数として表現できる。

同様に、 ('a, 'b) either のような型パラメータを取るバリアント型も表現できる。

type ('a, 'b, 'c) eitherCont = { inLeft : 'a -> 'c, inRight : 'b -> 'c }
fun Left x = fn (cases : ('a, 'b, 'c) eitherCont) => #inLeft cases x
fun Right x = fn (cases : ('a, 'b, 'c) eitherCont) => #inRight cases x
fun eitherToOption x = x { inLeft = SOME, inRight = fn _ => NONE }

多相レコードで多相バリアントを表現する

OCaml の多相バリアントは、通常のバリアントと異なり、同一のバリアントタグを複数の型の値として使うことができる。

let f = function `A -> "A";;
let g = function `A -> "A" | `B -> "B";;

この `A や `B が多相バリアントのタグで、型を見ると、 f は [< `A ] -> string、 g は [< `A | `B ] -> string と、 `A が [< `A ] や [< `A | `B ] という異なる型の値として使われているのがわかる。

これと同様のことが、多相レコードでも表現できる。

fun A () = fn cases => #caseA cases ()
fun B () = fn cases => #caseB cases ()

fun f x = x { caseA = fn () => "A" }
fun g x = x { caseA = fn () => "A", caseB = fn () => "B" }

先程の場合と同様に、バリアントタグ相当の関数は、バリアント引数と、継続の組（SML# のマニュアルの言葉で言うとメソッド集合もしくはメソッドスイート）を受け取る関数として定義し、場合分けをレコードで表現して渡してやる。

多相バリアントではタグが複数の型で使えていたのに対して、多相レコードではレコードのフィールド名が複数の型で使える。

これらの関数の型は次のようになっている。

val A = fn : unit -> ['a#{caseA: unit -> 'b}, 'b. 'a -> 'b]
val B = fn : unit -> ['a#{caseB: unit -> 'b}, 'b. 'a -> 'b]
val f = fn : ['a. ({caseA: unit -> string} -> 'a) -> 'a]
val g = fn
  : ['a.
       ({caseA: unit -> string, caseB: unit -> string} -> 'a) -> 'a]

A の型の ['a#{caseA: unit -> 'b}, 'b. 'a -> 'b] は SML# の拡張で、「caseA: unit -> 'b なるフィールドを持つ任意のレコード 'a と、任意の 'b に対して 'a -> 'b」と読む。

f (A ()) はこの型の関数に {caseA: unit -> string} なる値を渡すので型検査に通る。対して f (B ()) は {caseA: unit -> string} が 'a#{caseB: unit -> 'b} と合わないので型エラーになる。 g の方は、 {caseA: unit -> string, caseB: unit -> string} で A の場合の継続も B の場合の継続も含まれるので g (A ()) も g (B ()) も呼び出せる。

OCaml の場合、 g を拡張してさらにバリアントタグ `C も受け付けるようにした関数 h は、バリアント略記パターンを使って次のように書ける。

type t = [`A | `B]

let h = function
 | #t as x -> g x
 | `C -> "C"

SML# の場合は次のようにすべての場合を書き下さないといけない。

fun C () = fn cases => #caseC cases ()

fun h x = x { caseA = fn () => g (A ())
            , caseB = fn () => g (B ())
            , caseC = fn () => "C"
            }

caseA の場合でも x が A () であるというのは型情報からはわからないので g (A ()) と値を作り直す必要がある。 OCaml の方は #t as x で型を詳細化しているので問題ない。

オブジェクトでバリアントを表現する

ここまでは SML# で説明したが、 Java 等のオブジェクト指向言語でもレコードの代わりにオブジェクトを使えば同様のことができる。後述の fold の例を心の目で見ると、 Visitor パターンの仲間のようにも見える。さらに、オブジェクトはそれ自体が型パラメータを取ることもできるし、各場合を表すメソッドで個別に型パラメータを取ることさえもできる。

また、（レコードから話は逸れるが） x { inLeft = SOME, inRight = fn _ => NONE } も、 Smalltalk の Boolean>>ifTrue:ifFalse: に似ているような気がしないでもない。

まとまらない

多相でないバリアントを表現する時点でランク１多相性拡張が必要？ → 結果型を型パラメータで外に出すだけで十分 (2014-12-29)

A の定義を fun A x = fn cases => #caseA cases x のようにすると、 `A だけでなく `A 42 や `A "foo" としても使えるタグを表現できる。

以前、 SML# の PCRE バインディング（中断中）を書こうとしたときに今回の表現法を使った（https://github.com/mzp/space_tab_bot/blob/pcre/lib/pcre/pcre.sml ）。型がひどく禍々しくなるといった問題はあったもののそれほど使いにくくはない。

多相バリアントについては 『プログラミング in OCaml』の14章も参照のこと。

圏論的には、積（product）と和（coproduct）が双対であることから攻めていくとよい？（例えば Declarative Continuations and Categorical Duality とか）

再帰的な多相バリアント？

OCaml で再帰的な多相バリアントをオブジェクトを使って表現すると次のようになる。

let nil () = fun cases -> cases#caseNil ()
let cons a b = fun cases -> cases#caseCons a b

let rec fold x knil kons =
  x (object
    method caseNil () = knil
    method caseCons a b = kons a (fold b knil kons)
  end)

let to_list x = fold x [] (fun a b -> a::b)

ここで、 to_list の型には

val to_list :
  (< caseCons : 'b -> 'a -> 'b list;
     caseNil : unit -> 'c list
   > -> 'b list
   as 'a) -> 'b list

と、 ... as 'a な同値再帰型（equi-recursive type）が現れている（OCaml ではオブジェクトや多相バリアントのからむ部分では -rectypes オプションなしでも同値再帰型が使える）。

SML# では datatype 経由で同型再帰型（iso-recursive type）しか使えないが、生粋の SML#er であるところのよんたさん（@keita44_f4）によれば「たぶん SML# でも書けるはず」ということなのでいつかよんたさんが記事を書いてくれるだろう。