Namaran

Code daily. Without assist.

2026-10-19

closed.rs

enum Term { Var(usize), Lam(Box<Term>), App(Box<Term>, Box<Term>) }

fn closed(t: &Term, depth: usize) -> bool {
}

Term は λ計算(lambda calculus)の項を、変数名の代わりに番号で表したものです。Lam(body) は変数を1つ束縛する λ、App(f, a) は f に a を適用する項で、Var(i) の i は、その変数を囲む λ を内側から数えたとき、その変数を束縛している λ が何番目か(いちばん内側を0とする)を表します。この番号を De Bruijn インデックス(de Bruijn index)といいます。囲む λ が i 個以下しかない Var(i) には、束縛する λ が項の中にありません。このような変数を自由変数(free variable)といいます。t が depth 個の λ に囲まれた位置にあるとして、t の中に自由変数が1つもなければ true を返す closed を書いてください。項全体を調べるときは depth に0を渡し、λ に囲まれていない Var だけの項は false です。

入力例 1

closed(&Lam(Box::new(Lam(Box::new(Var(1))))), 0)

出力例 1

true

入力例 2

closed(&Lam(Box::new(App(Box::new(Var(0)), Box::new(Var(1))))), 0)

出力例 2

false

入力例 3

closed(&Var(0), 0)

出力例 3

false
Reference
fn closed(t: &Term, depth: usize) -> bool {
    match t {
        Term::Var(i) => *i < depth,
        Term::Lam(body) => closed(body, depth + 1),
        Term::App(f, a) => closed(f, depth) && closed(a, depth),
    }
}

depth は、いま見ている位置を囲む λ の数です。Lam の本体はもう1つ λ に囲まれるので depth + 1 で調べ、App の両側は同じ λ に囲まれているので depth のまま調べます。Var(i) を束縛する λ があるのは、囲む λ が i 番目(0から数える)まで届いているときで、式にすると i < depth です。

変数名を使う表し方では、同じ判定に「いま見えている名前の集合」を持ち回る必要があります。De Bruijn インデックスでは束縛が番号の大きさで決まるので、持ち回るのは整数1つで済みます。入力例 1 の Var(1) は2つの λ に囲まれて外側の λ を指し、入力例 2 の Var(1) は1つの λ にしか囲まれていないので自由変数です。

掲載したのは参考実装で、唯一の正解ではありません。depth を持ち回らずに、部分の項ごとに「中の変数をすべて束縛するには外側に λ がいくつ要るか」を内側から求め、項全体でそれが0かを調べる方法もあります。