クロージャを再帰呼び出しする方法を考えました。
追記 (2019/09/14): 結論しては、筆者はクロージャを使う再帰を諦めました。次の記事の「代替策」にあるように、struct + fn を使うのが妥当です。: static mutの危険性
概要
競技プログラミングではローカル変数を書き換えながら再帰する処理がよく出てきます。しかし Rust でそれを書こうとするとやや冗長になりがちです。
本稿では小さなヘルパーを用意して記述を簡略化することを試みました。
- 環境: Rust 1.15.1
- プログラミングコンテストのサイトAtCoder がサポートするバージョン
要約
- 競プロではよく再帰する
- 小さなアダプタを書くと再帰呼び出しできる
- イミュータブルなクロージャはローカル変数を書き換えられない
-
RefCellで対処する
-
- 成果:
用例1: 階乗
単純な例として、階乗の計算を再帰で書けるようにしましょう。内部で自身を参照するために、クロージャは引数に fact (階乗関数) を受け取るようにする方針でいきます。
let fact_5 = recurse(5, &|n, fact| {
if n <= 1 {
1_i64
} else {
n * fact(n - 1)
}
});
assert_eq!(1 * 2 * 3 * 4 * 5, fact_5);
ここで recurse(x, f) が f(x, f) の意味になるように後で定義するヘルパーです。
「なぜ作った関数を即座に起動するのか」という疑問があると思いますが、それは実際にそういう用途が多いからです。再帰関数がほしいときは |x| recurse(x, &|x, f| ..) のようにクロージャ化する運用でも大丈夫でしょう。
実装1: イミュータブル版
recurse の実装は簡単で、fn で定義した関数が再帰可能であることを利用します。
fn recurse<X, Y>(x: X, f: &Fn(X, &Fn(X) -> Y) -> Y) -> Y {
f(x, &|x: X| recurse(x, &f))
}
注意点は、クロージャの引数の型がまたそのクロージャの型で……という無限の循環を避けるため、関数を トレイトオブジェクト への参照という形で扱っていることです。
Fn(X) -> Y というのは「型 X の値を受け取って型 Y の値を返す関数」の型を表すトレイトで、ある種のクロージャは自動的に Fn を実装した型になります。参照: std::ops::Fn - Rust
&Fn(X, &Fn(X) -> Y) -> Y
^^^^^^^^^^ 再帰関数の型 (クロージャの引数)
^^^^^^^^^^^^^^^^^^^^^^^ 定義したクロージャのトレイトオブジェクトの型
用例2: DFSで連結成分分解
次に現実的な例として、グラフの連結成分分解を深さ優先探索で書いてみます。
//
// 0 -- 1
// | \
// | \
// 2 -- 3 4--5
//
let graph =
vec![
vec![1, 2, 3],
vec![0],
vec![0, 3],
vec![0, 2],
vec![5],
vec![4],
];
let n = graph.len();
let roots = RefCell::new(vec![n; n]);
for u in 0..n {
recurse(u, &|v, go| {
if roots.borrow()[v] < n {
return;
}
roots.borrow_mut()[v] = u;
for &w in graph[v].iter() {
go(w);
}
})
}
assert_eq!(&*roots.borrow(), &[0, 0, 0, 0, 4, 4]);
頂点 v が属す連結成分の代表を roots[v] に入れていきます。
このとき、再帰の途中で配列を更新する必要があります。しかし roots を let mut でミュータブル配列として宣言すると、先ほどの recurse は使えません。というもの、外部のミュータブルな変数を借用するクロージャは Fn トレイトを実装しないからです。
ここでは RefCell を使ってこの問題を回避しています。クロージャに渡すのが RefCell へのイミュータブルな参照でも、内部の値をミュータブルとして扱えます。参照: 保証を選ぶ
なんにせよ、それなりに簡潔に再帰処理ができました！
実装2. ミュータブル版
追記: ミュータブルなローカル変数を書き換えながらクロージャを再帰呼び出しする方法について記述していましたが、 安全でないコードが書けてしまう ので取り下げました。変更前の内容は編集履歴を参照。
参考
-
Stebalien commented on 28 Jan 2016
Zコンビネータを使ってクロージャを再帰可能にするコードの例。引数として受け取る再帰関数の型は推論されないっぽい。
-
クロージャのような匿名の関数を再帰呼び出しすることを無名再帰というらしい。