多相バリアントでopen recursion

OCamlでも（オブジェクトもrefも使わずに）Open Recursionしたい！！・・・したい？？ - Arantium Maestum に刺激を受けたので、多相バリアントでopen recursionする方法をメモ。

問題設定としては、よくある感じの整数の和と積がある言語の評価器を拡張可能にする。

type t =
  | Lit of int
  | Add of t * t
  | Mul of t * t

let rec eval = function
  | Lit i -> i
  | Add (l, r) -> eval l + eval r
  | Mul (l, r) -> eval l * eval r

まずは個々のバリアントタグを多相バリアントにばらして型を定義し、それぞれの評価関数を定義する。

リテラルに関しては何も考えずに定義するだけ。

type lit = [`Lit of int]

let eval_lit = function
  | `Lit i -> i

加算については、型定義で自分自身を参照すると再帰が閉じてしまうため、再帰部分は型パラメータで穴にしておく。うっかり再帰しないように nonrec をつけておいてみる。

type nonrec 't add = [`Add of 't * 't]

評価関数も同様に、 rec は付けず再帰的に部分木をたどる関数を外から与えるようにする。

let eval_add eval_rec = function
  | `Add (l, r) -> eval_rec l + eval_rec r

乗算も可算と同様に。

type nonrec 't mul = [`Mul of 't * 't]

let eval_mul eval_rec = function
  | `Mul (l, r) -> eval_rec l * eval_rec r

最後に let rec で再帰を閉じる。

type t = [ lit | t add | t mul ]

let rec eval : t -> int = function
  | `Mul _ as m -> eval_mul eval m
  | `Add _ as a -> eval_add eval a
  | `Lit _ as l -> eval_lit l

減算や除算を追加する場合もここまでと同様にすればよい。

ちなみに、この eval の型注釈は必要ない（というか、他の多相バリアント関連の型定義もすべて必要ない）。型注釈をつけなくても ([< `Add of 'a * 'a | `Lit of int | `Mul of 'a * 'a] as 'a) -> int のような型が推論される。

動かしてみる。

module M = struct
  let ( * ) x y = `Mul (x, y)
  let ( + ) x y = `Add (x, y)
  let i n = `Lit n
end

let () =
  Printf.printf "%d\n" @@ eval M.(i 3 + i 42 * i 5)
(* -| 213 *)

参考文献

• Code reuse through polymorphic variants. 元ネタ。多相バリアントをつかってラムダ計算の評価器を実装している