2026-09-05
unify.c
typedef struct T { char tag; struct T *l, *r; } T;
static T *find(T *t) {
if (t->tag == 'v' && t->l) t = t->l;
return t;
}
static int unify(T *a, T *b) {
a = find(a);
b = find(b);
if (a == b) return 1;
if (a->tag == 'v') { a->l = b; return 1; }
if (b->tag == 'v') { b->l = a; return 1; }
return a->tag == b->tag;
}
型推論の単一化 unify です。2つの型を同じ型にできれば必要な束縛を作って 1 を、できなければ 0 を返します。型変数 x、y と基本型 i(int)、b(bool) について unify(&x, &y) && unify(&y, &i) && unify(&x, &b) を評価すると、いまは 1 になります。本来は 0 です。
Answer
Wrong
static T *find(T *t) {
if (t->tag == 'v' && t->l) t = t->l;
return t;
}
find は束縛を1段しかたどりません。1つ目の単一化で x は y に、2つ目で y は int に束縛され、x から y、y から int へと2段の鎖ができます。3つ目の find(&x) は1段進んだ y で止まり、y は型変数なので、unify は y->l = b と束縛を書き換えて 1 を返します。y が int だったことはこの代入で失われ、int と bool の食い違いが見逃されます。
Right
while (t->tag == 'v' && t->l) t = t->l;
while にすると、未束縛の型変数か、型変数でない型に着くまでたどります。3つ目の find(&x) は int を返し、int と bool のタグが違うので 0 になります。鎖は型変数どうしを単一化するたびに1段ずつ伸びるので、何段になるかに上限はありません1。
- 型変数の束縛は Union-Find と同じ形をしています。たどり終えたあとで、途中の型変数を終点へ直接つなぎ直す(経路圧縮)と、次からのたどりが短くなります。