#002 存在型

あまり面白くない例だが，プリント可能なヘテロジニアス（異種混合）リストを考える． （但し，中身を直接見られないのでただの文字列のリストなのだが…）

type hetero = Nil | Cons of ∃'a. 'a * ('a -> string) * hetero

Cons の2つ目の引数は，要素を文字列にする関数である． 例えば，

Cons(1, string_of_int, Cons(true, string_of_bool, Nil))

などが hetero 型を持っている． と，なにげなく OCaml 風に書いているが， ∃ などと記述できないので当然このままでは実装できない．

OCaml では，∃α( T(α) ) が ∀β (∀α( T(α) → β ) → β ) と同等であることを利用して， 次のように擬似的に表現できる．

type hetero = Nil | Cons of cons
and cons = { f: 'b. 'b neg -> 'b }
and 'b neg = { k: 'a.  ('a * ('a -> string) * hetero) -> 'b }
let cons (e,to_s,next) = Cons { f = fun k -> k.k (e,to_s,next) }

関数 cons を利用して，上記の値は

cons(1, string_of_int, cons(true, string_of_bool, Nil))

と定義することができる． このリスト上の部分関数 head や tail は以下のように定義できる．

let head (Cons c) = c.f { k = fun (x,to_s,_) -> to_s x }
let tail (Cons c) = c.f { k = fun (_,_,next) -> next }

但し，head は string を返すものとしている．

下のプログラムから自動的に変換してくれるようなプログラムを camlp4 でそのうち書く予定．この予定も未定．

type hetero = Nil | Cons of ['a]. 'a * ('a -> string) * hetero
let head (Cons (x,to_s,_)) = to_s x
let tail (Cons (_,_,next)) = next

関数も変更する必要があるから，id:KeisukeNakano:20060720より面倒かな．