要約 抽象構文木のような再帰的データ構造に対して、再帰的に各ノードに付加情報を付けられるようにする、Tree decoration問題というのがある。Haskellでは開いた型族(open type family)を使ってこの問題を解決しており、TypeScriptではインタフェースを型パラメータに渡すことで解決できる(入れ子構造を自由に拡張する – TypeScript版「Trees that Grow」を参照)。OCamlでは多相バリアントとオブジェクト型を使うと、より拡張性を高めた形でこの問題を解決することができる。 問題設定 次のような、整数リテラル、変数参照、代入、関数式、関数呼び出しのある言語を考える。 type expr = | Literal of int | Variable of string | SetVariable of string * expr | Func
![Trees that Grow in OCaml - Qiita](https://cdn-ak-scissors.b.st-hatena.com/image/square/16f39ba3400b6e4c8fdf72f6cb8a0754847a91db/height=288;version=1;width=512/https%3A%2F%2Fqiita-user-contents.imgix.net%2Fhttps%253A%252F%252Fcdn.qiita.com%252Fassets%252Fpublic%252Farticle-ogp-background-9f5428127621718a910c8b63951390ad.png%3Fixlib%3Drb-4.0.0%26w%3D1200%26mark64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTkxNiZoPTMzNiZ0eHQ9VHJlZXMlMjB0aGF0JTIwR3JvdyUyMGluJTIwT0NhbWwmdHh0LWNvbG9yPSUyMzIxMjEyMSZ0eHQtZm9udD1IaXJhZ2lubyUyMFNhbnMlMjBXNiZ0eHQtc2l6ZT01NiZ0eHQtY2xpcD1lbGxpcHNpcyZ0eHQtYWxpZ249bGVmdCUyQ3RvcCZzPTcwNDIzODYxMDU1OTkyY2EzZjU4MjdhMmYwODQzM2Ni%26mark-x%3D142%26mark-y%3D112%26blend64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTcxNiZ0eHQ9JTQwZGljb19sZXF1ZSZ0eHQtY29sb3I9JTIzMjEyMTIxJnR4dC1mb250PUhpcmFnaW5vJTIwU2FucyUyMFc2JnR4dC1zaXplPTMyJnR4dC1hbGlnbj1sZWZ0JTJDdG9wJnM9ZTM1MjM2ZDBjYWY4MzUzZDlkYjc5ZGMwZDZjNGRiODQ%26blend-x%3D142%26blend-y%3D491%26blend-mode%3Dnormal%26s%3Dc82fa473298e41377243818321f110f7)