2026-09-05
occurs.c
typedef struct T { char tag; struct T *l, *r; } T;
bool occurs(const T *v, const T *t) {
}
型を表す木 t の中に型変数 v が現れるかを返す occurs を書いてください。tag は 'v' が型変数、'f' が関数型 l -> r、それ以外は int などの基本型です。型変数の l は束縛先を指し、未束縛なら NULL です。t の中の束縛済みの型変数は束縛先までたどって調べ、v は未束縛とします。t が v そのものなら true です。例では型を int -> a のように書きます。
入力例 1
occurs(a, int -> a)
出力例 1
true
入力例 2
occurs(a, b -> int)
出力例 2
false
入力例 3
occurs(a, a)
出力例 3
true
Reference
bool occurs(const T *v, const T *t) {
while (t->tag == 'v' && t->l) t = t->l;
if (t == v) return true;
return t->tag == 'f' && (occurs(v, t->l) || occurs(v, t->r));
}
束縛済みの型変数は、先に束縛先までたどってから調べます。たどらずに型変数のまま扱うと、b が int -> a に束縛されているとき、b -> int の中にある a を見落とします。たどり着いた先が v そのものなら v は現れていて、関数型なら左右のどちらかに現れるかを再帰で調べます。基本型や、v ではない未束縛の型変数には v は現れません。
単一化では、型変数 a を型 t に束縛する前にこの検査をします。a を int -> a に束縛すると、a をたどった先にまた a がある循環した型ができ、束縛をたどるループや型を表示する再帰が止まらなくなるからです。
掲載したのは参考実装で、唯一の正解ではありません。束縛をたどる部分を別の関数に分けても構いません。