#001 多相再帰

OCaml では，違う型で再帰する多相関数を書くことが難しい．

以下のデータ型 ('a,'b) twist を考える．

type ('a,'b) twist = Nil | Cons of 'a * 'b * ('b,'a) twist

例えば，次の値はデータ型 (int,bool) twist を持っている．

let twist_data = Cons(1,true,Cons(false,2,Nil))

このデータ型に対し，長さ（Consの個数）を求める関数を定義してみよう．

let rec length = function Nil -> 0 | Cons(a,b,rest) -> 1 + length rest

関数 length の定義は自然のように思えるが，実際には ('a,'a) twist -> int という型が推論されてしまい，上記の twist_data には適用できない．これは，上の再帰的定義の中に現れる length が，('a,'b) twist -> int と ('b,'a) twist -> int の2種類の型で使われているためで，これらを単一化した結果，型変数 'a と 'b が同一視されてしまう．

Haskell なら型宣言すればうまくいくが，OCaml ではそんなに簡単ではない．OCaml でこれを解決するには，多相型のフィールドを持つレコードを利用する．

type length = { run : 'a 'b. ('a,'b) twist -> int }
let length t =
  let rec f = { run = function Nil -> 0 | Cons(a,b,rest) -> 1 + f.run rest } in
  f.run t

しかし，毎回その型に対応したレコードを宣言するのも面倒だし， OCaml では別のレコードに対して同じフィールド名を使えないので，それぞれの型に対して run に相当する別の名前のフィールドを用意する必要がある．

そこで，単に，

let rec length : 'a 'b. ('a,'b) twist -> int = function
  Nil -> 0
| Cons(a,b,rest) -> 1 + length rest

とか書いたら，上のプログラムに変換してくれるような camlp4 のプログラムを暇なときにでも作ってみる予定．そして予定は未定．

ちなみに，OCaml では，レコードのフィールドの他に，オブジェクトのメソッドでも多相型を定義できるため，

let length t = (object (self)
  method run : 'a 'b. ('a,'b) twist -> int = function
    Nil -> 0
  | Cons(a,b,rest) -> 1 + self#run rest
end)#run t

と書くこともできる．こちらの場合は，レコードの時ように新たな型宣言をする必要はなく，メソッド名 run は別のオブジェクトで使っても問題ない．（OCaml でオブジェクトを使うのは，個人的には好きではないのだが…．）