Namaran

Code daily. Without assist.

2026-10-19

index.rs

fn to_index(binders: &[&str], name: &str) -> Option<usize> {
    binders.iter().rposition(|b| *b == name)
}

fn main() {
    let binders = ["f", "x", "y", "x"];
    for name in ["x", "f", "z"] {
        println!("{name} {:?}", to_index(&binders, name));
    }
}

λ計算(lambda calculus)の項で、変数の名前を番号に置き換えます。番号は、その変数を囲む λ を内側から数えたとき、その変数を束縛している λ が何番目か(いちばん内側を0とする)で、これを De Bruijn インデックス(de Bruijn index)といいます。同じ名前を束縛する λ が複数あれば、いちばん内側のものが束縛します。to_index は、変数を囲む λ が束縛する名前を外側から順に並べた binders と変数名 name を受け取り、この番号を返すつもりの関数で、束縛する λ がなければ None を返します。main は λf. λx. λy. λx. の内側にある変数 x、f、z を調べています。いまの出力は x Some(3)、f Some(0)、z None の3行です。本来の出力は x Some(0)、f Some(3)、z None です。

Answer

Wrong

binders.iter().rposition(|b| *b == name)

rposition は列を末尾から探し、最初に条件を満たした要素の位置を返します。探す向きは末尾からですが、返す位置は先頭から数えた添字です。x では末尾の "x" が見つかり、いちばん内側の λx を選ぶところまでは正しく動きますが、返るのはその添字の3です。f も先頭の添字0が返り、内側から数えた番号とは逆向きになります。

Right

binders.iter().rev().position(|b| *b == name)

rev() で列を逆順にしてから position で探すと、探す向きも数える向きも末尾からになります。逆順の列の先頭はいちばん内側の λ なので、返る位置がそのまま内側から数えた番号で、x は0、f は3になります1。

  1. バグのある版が返していた、外側から数えた番号は De Bruijn レベル(de Bruijn level)と呼ばれ、これも使われる表し方です。λ の内側へ進んでも同じ変数の番号が変わらない代わりに、番号の意味が項の外側にいくつ λ があるかに左右されます。