Namaran

Code daily. Without assist.

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 がある循環した型ができ、束縛をたどるループや型を表示する再帰が止まらなくなるからです。

掲載したのは参考実装で、唯一の正解ではありません。束縛をたどる部分を別の関数に分けても構いません。