入れ子構造を自由に拡張する – TypeScript版「Trees that Grow」

This is a Japanese translation of Flexiblly Extend Nested Structures – “Trees that Grow” in TypeScript.

抽象構文木（AST, Abstract Syntax Tree）の扱いに慣れた一部のHaskell開発者の間では、「Trees that Grow」というイディオムが一般的で、Haskellの最も有名なコンパイラ、GHCにおいても採用されています。今回は、この「Trees that Grow」をTypeScriptで実現するにはどうすれば良いかを共有しましょう。

あらまし

Haskellでは「Tree-Decoration問題」という問題を、open type familyという機能と基盤となる入れ子になった型を組み合わせることで解決します。一方、TypeScriptはopen type familyという機能を（少なくとも単純な方法では）サポートしていません。ところが、私は「Tree-Decoration問題」を解決する本当の鍵は、open type familyではなく、型引数を一つの構造体にまとめる手段にあることに気づきました。それは、TypeScriptではインデックスアクセス型によって実現できますが、現状知る限り、Haskellでは実現できません。

この記事に掲載する一部の重要なサンプルコードは、https://github.com/igrep/ts-that-grow にて利用できます。また、CodeSandboxにもプロジェクトを作ったので、ブラウザ上で直接実行することもできます。

問題

静的型付け言語で書かれたコンパイラは通常、コンパイル対象となる言語の抽象構文木を表す型を、ソースコードのどこかに含んでいます。大抵の抽象構文木型は再帰的に定義されているため、ノードを表す各種の型に追加の情報を加えるのが難しくなっています。

これからこの記事で最後まで使用する例として、次のような単純な抽象構文木型を用います:

// 数値リテラル、変数、変数への値のセット、関数式、関数呼び出し、
// だけが利用できる架空の言語の抽象構文木型
type Expression = Literal | Variable | SetVariable | Func | CallFunc;

type Literal = {
  type: "Literal";
  value: number;
};

type Variable = {
  type: "Variable";
  name: string;
};

type SetVariable = {
  type: "SetVariable";
  name: string;
  value: Expression;
};

type Func = {
  type: "Func";
  argumentName: string;
  body: Expression;
};

type CallFunc = {
  type: "CallFunc";
  function: Expression;
  argument: Expression;
};

例えば、ソースファイルのどこで各ノードが見つかったかを記録できるようにします:

type Expression = Literal | Variable | SetVariable | Func | CallFunc;

type Location = { row: number; column: number };

type Literal = {
  type: "Literal";
  value: number;
  location: Location;
};

type Variable = {
  type: "Variable";
  name: string;
  location: Location;
};

type SetVariable = {
  type: "SetVariable";
  name: string;
  value: Expression;
  location: Location;
};

type Func = {
  type: "Func";
  argumentName: string;
  body: Expression;
  location: Location;
};

type CallFunc = {
  type: "CallFunc";
  function: Expression;
  argument: Expression;
  location: Location;
};

type Expression = Literal | Variable | SetVariable | Func | CallFunc;

type Location = { row: number; column: number };

type Literal = {
  type: "Literal";
  value: number;
  location: Location;
};

type Variable = {
  type: "Variable";
  name: string;
  location: Location;
  namespace: { qualifier: string }
};

type SetVariable = {
  type: "SetVariable";
  name: string;
  value: Expression;
  location: Location;
  namespace: { qualifier: string }
};

type Func = {
  type: "Func";
  argumentName: string;
  body: Expression;
  location: Location;
};

type CallFunc = {
  type: "CallFunc";
  function: Expression;
  argument: Expression;
  location: Location;
};

まだまだ、他にも足りない情報を加えたくなるかも知れません。

しかしここで問題です。新しく加えたプロパティは、あらゆる利用シーンで必要なものではありませんし、またある段階ではそもそも取得できない情報かも知れません。なので上記のExpression型のような、一つの型にあらゆる拡張を加えていくと、やがて詰め込み過ぎになってしまいます。「関心の分離」という観点で考えて、型を分けるべきなのです。

当然この手の問題は、複合的な型を作っていると日常的に経験するものです。そうした場合にすぐ思いつく方法として、トップレベルのExpression型だけを直接拡張する、という方法があります:

type Expression = Literal | Variable | SetVariable | Func | CallFunc;

type Location = { row: number; column: number };

type ExpressionWithLocation = Expression & Location;

...

この方法は、対象の型が再帰的に定義されている場合はうまくいきません。Expression型の場合、いくつかのノード ―― 具体的にはSetVariable・Func・CallFunc ―― がExpression型を再帰的に含んでいるため、ExpressionWithLocation型における& Locationは、そうした再帰的に含まれるExpression型には適用されません。これが「Tree-Decoration問題」です。

不完全な方法1: 拡張を型引数にして、取り回す

読者のみなさんは前節の例を読んだ上で、「じゃあ、Locationを型引数にするのはどうだろう？」とまで考えつくかも知れません。

type Expression<Extension> =
  Literal<Extension> | Variable<Extension> | SetVariable<Extension> | Func<Extension> | CallFunc<Extension>;

type Location = { row: number; column: number };

type ExpressionWithLocation = Expression<Location>;

type Literal<Extension> = {
  type: "Literal";
  value: number;
} & Extension;

type Variable<Extension> = {
  type: "Variable";
  name: string;
} & Extension;

type SetVariable<Extension> = {
  type: "SetVariable";
  name: string;
  value: Expression<Extension>;
} & Extension;

type Func<Extension> = {
  type: "Func";
  argumentName: string;
  body: Expression<Extension>;
} & Extension;

type CallFunc<Extension> = {
  type: "CallFunc";
  function: Expression<Extension>;
  argument: Expression<Extension>;
} & Extension;

SetVariableやFunc、CallFuncも含めた、Expression型が現れる箇所をExpression<Extension>に置き換えることで、型引数として渡したExtensionがあらゆる型に&で適用されます。

確かにこの方法は、Locationを拡張として渡す場合は何の問題もありません。実際のところ、これで十分だというケースも珍しくないでしょう。余計な複雑さを避けるためにもその方が賢明かも知れません。ところがこの方法だと、ExpressionWithNamespace型はうまく作れません。前述のnamespaceというプロパティは、VariableとSetVariableノードにのみ追加すべきなのです。

この話を一般化すると、ノードの種類によって異なるプロパティを追加したい場合、拡張を単一の型引数で表現するのは不十分だ、ということです。

冒頭で紹介した「Trees that Grow」という論文曰く、GHCの開発者達もまさに同じ問題に直面していました。GHCの抽象構文木型「HsSyn」は、コンパイラがコンパイルする際の各フェーズで違う情報を抽象構文木型に加える必要があり、その上外部のライブラリーでも独自のカスタマイズを加えてHsSynを利用したい、という需要があったのです。「Trees that Grow」という手法が発明されるまでは、独立した抽象構文木型をそれぞれで作るといった、不完全な作戦で妥協するしかありませんでした。

解決策

オリジナルのアイディアに則り、type familyを用いる

件の「Trees that Grow」を紹介した論文では、「Tree-Decoration問題」を「open type family」というHaskellの機能で克服しました。残念なことに、TypeScriptは「open」な方のtype familyをサポートしていません。「typescript type family」で検索すると最初に見つかるページでは確かにTypeScriptでtype familyを実現する方法を紹介していますが、そこに出てくる例は「closed」なtype familyのみです。「open」なtype familyと「closed」なtype familyは、「条件と結果を後で追加できるか否か」という点で異なっています（「open」な方であれば後で追加できる）。詳しく知るために、TypeScriptがopen type familyを実装したと仮定して、比較してみましょう。

open type familyよりも先に、ひとまずclosedな方のtype familyが、TypeScriptでどのように実現できるか見てみましょう:

type CloseTypeFamily<SomeType> =
  SomeType extends number ? boolean : string;

こちらはTypeScriptで書いた最も単純な形のtype familyです。type familyは型についての関数で、型を引数として受け取って、また別の型を返します。上記のClosedTypeFamilyはSomeTypeという名前の引数を受け取り、SomeTypeがnumber型であれば（あるいはnumberのサブタイプであれば）booleanを返し、そうでなければstringを返すclosedなtype familyとなっています。

closedなtype familyについての説明は以上です。closedなtype familyは単なる、型を受け取って型を返す、それだけの関数です。TypeScriptはtype familyのために特別なキーワードを用意しているわけでもないし、上記のようにConditional Typesを使って簡単に書けてしまうので、TypeScriptを書く人達がtype familyに言及することは希でしょう。

では次はopen type familyの番です。実際のTypeScriptとしてはエラーになりますが、擬似的なTypeScriptで再現してみましょう:

type OpenTypeFamily<SomeType extends number> = boolean;
type OpenTypeFamily<SomeType extends string> = object[];
type OpenTypeFamily<SomeType extends any[]> = { another: "case", youCan: "add" };

OpenTypeFamilyという名前でのtype宣言が複数あることに注目してください。本来のTypeScriptでは禁止されています。これがopen type familyの重要な特徴です。open type familyは、引数となる型についての条件と、引数が条件を満たした際戻り値となる型を追加することに、開かれているのです。

OpenTypeFamilyは複数回宣言された際、どのように振る舞うのでしょうか？もし私がTypeScriptにおけるopen type familyの設計をしていたら、以下のように作るでしょう:

type OpenTypeFamily<number>   // boolean を返す。
type OpenTypeFamily<string>   // object[] を返す。
type OpenTypeFamily<number[]> // { another: "case", youCan: "add" } を返す。
type OpenTypeFamily<boolean>  // マッチする引数がないので、型エラー。

この記事にとって重要なことではないので割愛しますが、簡単に言うと、open type familyは、宣言された条件をすべて探索し、与えられた型引数に最も合致する型が見つかったら、対応する型を返します。

グローバルなインタフェースをopen type familyの代わりに使う

前節の冒頭でお話ししたとおり、TypeScriptはopen type familyを提供していません。しかし実を言うと、「Trees that Grow」をTypeScriptで再現するだけならば、open type familyの完全な機能は必要ありません。TypeScriptはopenなtype familyに似た機能をすでに備えていて、なおかつその機能で「Trees that Grow」の要件を満たすことができます。

その機能はinterfaceです。TypeScriptのインタフェースは、文字列のリテラル型¹を受け取って、型を返すtype familyのように使うことができます:

interface TypeFamily {
  foo: boolean;
  bar: object[];
  baz: { another: "type"; };
}

TypeFamily["foo"] // boolean を返す
TypeFamily["bar"] // object[] を返す
TypeFamily["baz"] // { another: "type"; } を返す

プレイグラウンドで試す

インデックスアクセス型のおかげでインタフェースは、インデックス演算子を通じてキーとなる型を受け取るtype familyだと見なすことができます。

キーとなる型は型引数として渡すこともできます:

interface TypeFamily {
  foo: boolean;
  bar: object[];
  baz: { another: "type"; };
}

type GetTheValueType<Key extends keyof TypeFamily> = TypeFamily[Key];

GetTheValueType<"foo"> // boolean を返す
GetTheValueType<"bar"> // object[] を返す
GetTheValueType<"baz"> // { another: "type"; } を返す

プレイグラウンドで試す
以上が、インタフェースがtype familyになれる理由です。では、その「openさ」、すなわち、定義を後から追加できるという特性についてはいかがでしょうか？実は、インタフェースは元から拡張に対して開かれているよう設計されています:

// 先ほどの例の後にこちらを追記してみてください
interface TypeFamily {
  anotherProperty: string;
}

GetTheValueType<"anotherProperty"> // string を返す

プレイグラウンドで試す
モジュールが同じ名前でのinterface宣言を複数含んでいた場合、TypeScriptはそうした宣言を、一つのまとまったinterface宣言として解釈します（詳細はTypeScriptのドキュメント、「Merging Interfaces」の節を参照）。

ただし、まだ一つ障害があります。TypeScriptが複数のinterface宣言をまとめて一つのinterfaceと見なせるのは、一つのモジュールの中に限られているのです。これではインタフェースが「Trees that Grow」に相応しくないことになってしまいます。というのも、「Trees that Grow」ではtype familyがモジュールをまたいで拡張できなければならないからです（後で例をお見せします）。

この問題を回避するには、インタフェースをdeclare globalブロックの中で宣言しなければなりません。

declare global {
  interface TypeFamily {
    foo: boolean;
    bar: object[];
    baz: { another: "type"; };
  }
}

// ... 他のファイルにて ...
declare global {
  interface TypeFamily {
    anotherProperty: string;
  }
}

declare globalを使うと、上記のTypeFamilyは文字通りグローバルに利用可能になります²。これによって、TypeFamilyに新しい定義をいつでもどこでも追記できるようになりました。

グローバルなインタフェースでExpressionを拡張可能にする

前節では、ついに「Trees that Grow」を実現するのに必要なパーツを全て揃えることができました。いよいよグローバルなインタフェースでopen type familyを真似ることによって、「Tree-Decoration問題」を解決する方法を提案いたしましょう。

手始めに、最初に紹介した、拡張できないExpression型を再掲します:

type Expression = Literal | Variable | SetVariable | Func | CallFunc;

type Literal = {
  type: "Literal";
  value: number;
};

type Variable = {
  type: "Variable";
  name: string;
};

type SetVariable = {
  type: "SetVariable";
  name: string;
  value: Expression;
};

type Func = {
  type: "Func";
  argumentName: string;
  body: Expression;
};

type CallFunc = {
  type: "CallFunc";
  function: Expression;
  argument: Expression;
};

最初に、Expression型と、Expression型の各ノードを表す型に、型引数を一つ追加します:

type Expression<Descriptor> =
  | Literal<Descriptor>
  | Variable<Descriptor>
  | SetVariable<Descriptor>
  | Func<Descriptor>
  | CallFunc<Descriptor>;

type Literal<Descriptor> = {
  type: "Literal";
  value: number;
};

type Variable<Descriptor> = {
  type: "Variable";
  name: string;
};

type SetVariable<Descriptor> =
  {
    type: "SetVariable";
    name: string;
    value: Expression<Descriptor>;
  };

type Func<Descriptor> = {
  type: "Func";
  argumentName: string;
  body: Expression<Descriptor>;
};

type CallFunc<Descriptor> = {
  type: "CallFunc";
  function: Expression<Descriptor>;
  argument: Expression<Descriptor>;
};

declare global {
  interface ExtendExpression {
    plain: object;
  }
  interface ExtendLiteral {
    plain: object;
  }
  interface ExtendVariable {
    plain: object;
  }
  interface ExtendSetVariable {
    plain: object;
  }
  interface ExtendFunc {
    plain: object;
  }
  interface ExtendCallFunc {
    plain: object;
  }
}

それから、keyof演算子を使って、Expressionと各ノードに渡す型引数を、それぞれのExtendで始まる名前のインタフェースにおける、keyに絞ります:

type Expression<Descriptor extends keyof ExtendExpression> =
  | Literal<Descriptor>
  | Variable<Descriptor>
  | SetVariable<Descriptor>
  | Func<Descriptor>
  | CallFunc<Descriptor>;

type Literal<Descriptor extends keyof ExtendLiteral> = {
  type: "Literal";
  value: number;
};

type Variable<Descriptor extends keyof ExtendVariable> = {
  type: "Variable";
  name: string;
};

type SetVariable<Descriptor extends keyof ExtendSetVariable> =
  {
    type: "SetVariable";
    name: string;
    value: Expression<Descriptor>;
  };

type Func<Descriptor extends keyof ExtendFunc> = {
  type: "Func";
  argumentName: string;
  body: Expression<Descriptor>;
};

type CallFunc<Descriptor extends keyof ExtendCallFunc> = {
  type: "CallFunc";
  function: Expression<Descriptor>;
  argument: Expression<Descriptor>;
};

それぞれのノードを表す型が、異なるインタフェースのキーで制限された型引数を取っている点に着目してください。例えばExtendLiteralがLiteral型の型引数を制限し、ExtendVariableがVariable型の型引数を制限していますね。これは各ノードの型に対して異なるプロパティを加える上で、重要な点です。

最後のステップとして、全てのノードの型を、対応するExtendで始まる名前のインタフェースで拡張しましょう。交差型を作る、&演算子を使うのが簡単です。そして、各ノード型に渡したDescriptor型引数によって、Extendで始まる名前のインタフェースのキーを指定します:

type Literal<Descriptor extends keyof ExtendLiteral> = {
  type: "Literal";
  value: number;
} & ExtendLiteral[Descriptor]; // <- ここを追記する

type Variable<Descriptor extends keyof ExtendVariable> = {
  type: "Variable";
  name: string;
} & ExtendVariable[Descriptor]; // <- ここを追記する

type SetVariable<Descriptor extends keyof ExtendSetVariable> =
  {
    type: "SetVariable";
    name: string;
    value: Expression<Descriptor>;
  } & ExtendSetVariable[Descriptor]; // <- ここを追記する

type Func<Descriptor extends keyof ExtendFunc> = {
  type: "Func";
  argumentName: string;
  body: Expression<Descriptor>;
} & ExtendFunc[Descriptor]; // <- ここを追記する

type CallFunc<Descriptor extends keyof ExtendCallFunc> = {
  type: "CallFunc";
  function: Expression<Descriptor>;
  argument: Expression<Descriptor>;
} & ExtendCallFunc[Descriptor]; // <- ここを追記する

declare global {
  interface ExtendExpression {
    namespace: object;
  }
  interface ExtendLiteral {
    namespace: object;
  }
  interface ExtendVariable {
    namespace: { qualifier: string };
  }
  interface ExtendSetVariable {
    namespace: { qualifier: string };
  }
  interface ExtendFunc {
    namespace: object;
  }
  interface ExtendCallFunc {
    namespace: object;
  }
}

他の型のノードは拡張しないでおくために、namespaceプロパティを「あらゆるオブジェクト」を表すobject型にしておいてください。typescript-eslintパッケージが推奨するとおり、この記事では{}の代わりにobjectを&演算子の単位元（何を一緒に適用しても結果が変わらないもの）として使用しています。

いよいよ、実際に新しいプロパティの名前を渡したExpression型を使ってみて、どんな結果となるのか見てみましょう。

type MyExpression = Expression<"namespace">;

type宣言によるエイリアスを一段階ずつ展開して、Expression型がどう拡張されたのか確認します:

// (1) `Expression`型の定義に従って、
//     型引数`Descriptor`を`"namespace"`で置き換える:
type Expression<"namespace"> =
  | Literal<"namespace">
  | Variable<"namespace">
  | SetVariable<"namespace">
  | Func<"namespace">
  | CallFunc<"namespace">;

// (2A) `Literal`型の定義に従って、
//      型引数`Descriptor`を`"namespace"`で置き換える:
type Literal<"namespace"> = {
  type: "Literal";
  value: number;
} & ExtendLiteral["namespace"];

// (3A) `ExtendLiteral`型の定義によると、
//      `ExtendLiteral["namespace"]`は`object`となる:
type Literal<"namespace"> = {
  type: "Literal";
  value: number;
} & object;

// (4A) `object`に`&`を適用しても結果は変わらない:
type Literal<"namespace"> = {
  type: "Literal";
  value: number;
};

/* (上記の(1)からの続き) */

// (2B) `Variable`型の定義に従って、
//      型引数`Descriptor`を`"namespace"`で置き換える:
type Variable<"namespace"> = {
  type: "Variable";
  name: string;
} & ExtendVariable["namespace"];

// (3B) `ExtendVariable`型の定義によると,
//      `ExtendVariable["namespace"]`は`{ qualifier: string }`という型となる:
type Variable<"namespace"> = {
  type: "Variable";
  name: string;
} & { qualifier: string };

// (4B) `&`演算子を適用する:
type Variable<"namespace"> = {
  type: "Variable";
  name: string;
  qualifier: string;
}

ここまで展開してきた結果から分かるとおり、Variable型とSetVariable型のみがExpandで始まる名前のインタフェースで拡張されました。このことから、グローバルに宣言したインタフェースをそれぞれ拡張することで、「Tree-Decoration問題」を解決できたことが分かります。

新たな問題: もっとシンプルにできないか？

前節までに解説した方法は、Haskellによる「Trees that Grow」を元の手法に近い形でTypeScriptに移植したものです。この方法は確かに、open type family（TypeScriptではグローバルに追記可能なインタフェース）を応用することで、入れ子になった再帰型をアプリケーションで必要なプロパティの分だけ自由に拡張できるようにしてくれます。

ところが、今度は新しい問題が生まれてしまいました。declare globalなインタフェースを使うというのは、とても遠回しなやり方なのです。コードを読んでいて初めてグローバルなインタフェースを見かけた人は、恐らく拡張する型との間にどんな関係があるのかを見いだすのに苦労するでしょう。既存のグローバル変数と似た問題を孕んでいるのです。

ここまでこの記事を読まれたあなたも、もっと簡単に理解できる方法を望んでいらっしゃるかも知れません。そこで私はTypeScriptでのもっと簡潔な解決策を編み出したので、以降で説明します。

不完全な方法2: すべての拡張を型引数にして、取り回す

まず始めに、「不完全な方法1: 拡張を型引数にして、取り回す」の節で紹介した方法を思い出してください:

type Expression<Extension> =
  Literal<Extension> | Variable<Extension> | SetVariable<Extension> | Func<Extension> | CallFunc<Extension>;

type Literal<Extension> = {
  type: "Literal";
  value: number;
} & Extension;

type Variable<Extension> = {
  type: "Variable";
  name: string;
} & Extension;

type SetVariable<Extension> = {
  type: "SetVariable";
  name: string;
  value: Expression<Extension>;
} & Extension;

type Func<Extension> = {
  type: "Func";
  argumentName: string;
  body: Expression<Extension>;
} & Extension;

type CallFunc<Extension> = {
  type: "CallFunc";
  function: Expression<Extension>;
  argument: Expression<Extension>;
} & Extension;

これは言い換えると、ノードの型の数だけ型引数を増やせば解決できる、ということでもあります:

type Expression<
  ExtendLiteral,
  ExtendVariable,
  ExtendSetVariable,
  ExtendFunc,
  ExtendCallFunc,
> =
  | Literal<ExtendLiteral>
  | Variable<ExtendVariable>
  | SetVariable<
      ExtendLiteral,
      ExtendVariable,
      ExtendSetVariable,
      ExtendFunc,
      ExtendCallFunc
    >
  | Func<
      ExtendLiteral,
      ExtendVariable,
      ExtendSetVariable,
      ExtendFunc,
      ExtendCallFunc
    >
  | CallFunc<
      ExtendLiteral,
      ExtendVariable,
      ExtendSetVariable,
      ExtendFunc,
      ExtendCallFunc
    >;

// ... 以下、ノードの型 ...

そして当然の成り行きとして、これらの型引数は、すべてそうした型の定義でも繰り返し渡すことになります。例えばCallFunc型は、次のような定義に変わります:

type CallFunc<
  ExtendLiteral,
  ExtendVariable,
  ExtendSetVariable,
  ExtendFunc,
  ExtendCallFunc,
> = {
  type: "CallFunc";
  function: Expression<
    ExtendLiteral,
    ExtendVariable,
    ExtendSetVariable,
    ExtendFunc,
    ExtendCallFunc
  >;
  argument: Expression<
    ExtendLiteral,
    ExtendVariable,
    ExtendSetVariable,
    ExtendFunc,
    ExtendCallFunc
  >;
} & ExtendCallFunc;

最後の方法: 型引数群を一つの構造にまとめる

普通の関数を扱うときの経験を思い出すに、こういう場合、全ての引数を一つの構造として扱えるようにして、中で呼び出す関数に渡して回る、というのが定石でしょう。例えば次の通りです:

type Arguments = {
  foo: string;
  bar: number;
  baz: boolean;
  qux: number | undefined;
  quux: string[];
};

function callee1(arguments: Arguments);
function callee2(arguments: Arguments);

function rootCaller(arguments: Arguments) {
  // ...
  callee1(arguments);
  // ...
  callee2(arguments);
  // ...
}

// v.s. 引数を一つの構造にまとめなかった場合:

function callee1(foo: string, bar: number, baz: boolean, qux: number | undefined, quux: string[]);
function callee2(foo: string, bar: number, baz: boolean, qux: number | undefined, quux: string[]);

function rootCaller(foo: string, bar: number, baz: boolean, qux: number | undefined, quux: string[]) {
  // ...
  callee1(foo, bar, baz, qux, quux);
  // ...
  callee2(foo, bar, baz, qux, quux);
  // ...
}

// それぞれノード型についてプロパティを一つ持ったインタフェース
interface ExtendExpression {
  Literal: object;
  Variable: object;
  SetVariable: object;
  Func: object;
  CallFunc: object;
}

// `Extend`型引数についてデフォルト値を設定することで、簡単に扱えるようにする
type Expression<Extend extends ExtendExpression = ExtendExpression> =
  | Literal<Extend>
  | Variable<Extend>
  | SetVariable<Extend>
  | Func<Extend>
  | CallFunc<Extend>;

type Literal<Extend extends ExtendExpression = ExtendExpression> = {
  type: "Literal";
  value: number;
} & Extend["Literal"];

type Variable<Extend extends ExtendExpression = ExtendExpression> = {
  type: "Variable";
  name: string;
} & Extend["Variable"];

type SetVariable<Extend extends ExtendExpression = ExtendExpression> = {
  type: "SetVariable";
  name: string;
  value: Expression<Extend>;
} & Extend["SetVariable"];

type Func<Extend extends ExtendExpression = ExtendExpression> = {
  type: "Func";
  argumentName: string;
  body: Expression<Extend>;
} & Extend["Func"];

type CallFunc<Extend extends ExtendExpression = ExtendExpression> = {
  type: "CallFunc";
  function: Expression<Extend>;
  argument: Expression<Extend>;
} & Extend["CallFunc"];

サンプルコード

サンプルコードとして、何も拡張していないExpression型の値にnamespaceを付けて変換する関数をこちらに作成しました:

https://github.com/igrep/ts-that-grow/blob/main/src/app.ts

是非試してみてください！

終わりに: 本当にHaskellでは不可能か？

最後に紹介した方法がその前の方法と比べてあまりにも単純なので、驚いている方もいらっしゃるかも知れません。一方元となった「Trees that Grow」の論文では、open type familyを使った比較的複雑な方法を要件として挙げています。その最も大きな理由は、TypeScriptにおける型引数を一つの構造に詰め込む機能を、Haskellが提供していないことにあるようです。

視点を変えると、このTypeScriptにおける「詰め込む」機能は、制限したバージョンの高階なtype family（高階関数のように、type familyを受け取るtype family）であるとも解釈できます。前述のExtend型引数は、インデックスアクセス型を通すことで、プロパティの名前を受け取って型を返す関数だと見なせるのです。

TypeScriptとは異なり、Haskellではそのtype familyの制限によって、高階なtype familyを（少なくとも直接的な方法では）サポートしていません（参考: Higher order type families in Haskell – Stack Overflow）。しかしながら、実は私は何かを見落としているかも知れません。もし新しい方法が見つかったら、その時は別途執筆する予定です。