多相バリアントと木構造

多相バリアントでも、木構造のデータ型を定義してしまうと拡張が大変だよね、というお話。

ツリー構造じゃない場合

適当にデータ型を定義するよ！

type value = [ `Var of string | `String of string ]

多相バリアントだから簡単に拡張できるね、やった！

type value2 = [value | `Int of bool]

ツリー構造

じゃあ、次は木構造を定義してみる。

type expr =  [ `Var of string | `String of string | `Lambda of string * expr]

拡張してみる。

type expr2 =  [ expr | `Int of int ]

じゃあ、さっそく使ってみよう。

# (`Lambda ("x",`Int 42) : expr2);;
Characters 1-22:
  (`Lambda ("x",`Int 42) : expr2);;
   ^^^^^^^^^^^^^^^^^^^^^
This expression has type [> `Lambda of string * ([> `Int of int ] as 'a) ]
but is here used with type
  expr2 =
    [ `Int of int
    | `Lambda of string * expr
    | `String of string
    | `Var of string ]
Type 'a is not compatible with type
  expr = [ `Lambda of string * expr | `String of string | `Var of string ]
The second variant type does not allow tag(s) `Int

`Lambdaのパラメータはexpr2じゃなくてexprだから、ちゃんと拡張できてないよ ><。

いちおう解決策

再帰的になっている部分を型変数に逃がしてやれば、いちおう回避できるよ！ ホントにこれでいいのかは、はなはだ疑問だけど。(これでいいらしいです。コメント欄参照)

type 'a expr_type = [ `Var of string | `String of string | `Lambda of string * 'a]
type expr = expr expr_type

type 'a expr_type2 = ['a expr_type | `Int of int]
type expr2 = expr2 expr_type2

(`Lambda ("x",`Int 42) : expr2);;
- : expr2 = `Lambda ("x", `Int 42)