Rustのclosureによりキャプチャーされた環境をmutableで持ってくるには？

Rustのclosureによる環境キャプチャーに関して質問です。
AtcoderのA-Frog1
を解いています。通常のコードはできたので、視点を変えて、
問題を漸化式に見立てて、再帰関数を用いてメモ化することで
解こうとしています。

rustc 1.57.0

Rustメモ化なし
1use proconio::input;
2use std::cmp::min;
3
4fn recurse<X, Y>(x: X,  f: &dyn Fn(X, &dyn Fn(X) -> Y) -> Y) -> Y {
5    f(x, &|x: X| recurse(x, &f))
6}
7fn main() {
8    input! {
9        n:usize,
10        cost:[i64;n],
11    }
12    let inf = i64::MAX;
13    let mut dp = vec![inf;n];
14    dp[0] = 0;
15    dp[1] = (cost[1]-cost[0]).abs();
16
17    let rec = recurse(n-1, &|i:usize,rec|{
18        if i == 0{
19            return dp[0]
20        }
21        else if i ==1{
22            return dp[1]
23        }
24        else{
25            let mut res = std::i64::MAX;
26            res = min(res,rec(i-1)+(cost[i]-cost[i-1]).abs());
27            res = min(res,rec(i-2)+(cost[i]-cost[i-2]).abs());
28           
29            return res 
30        }
31    });
32    println!("{}",rec);
33}

上記メモ化なしは問題ないのですが、

Rustメモ化あり
1use proconio::input;
2use std::cmp::min;
3
4fn recurse<X, Y>(x: X,  f: &dyn Fn(X, &dyn Fn(X) -> Y) -> Y) -> Y {
5    f(x, &|x: X| recurse(x, &f))
6}
7fn main() {
8    input! {
9        n:usize,
10        cost:[i64;n],
11    }
12    let inf = i64::MAX;
13    let mut dp = vec![inf;n];
14    dp[0] = 0;
15    dp[1] = (cost[1]-cost[0]).abs();
16
17    let rec = recurse(n-1, &|i:usize,rec|{
18        if dp[i] < inf{    //追加
19            return dp[i]   //追加
20        }                   //追加
21        if i == 0{
22            return dp[0]
23        }
24        else if i ==1{
25            return dp[1]
26        }
27        else{
28            let mut res = std::i64::MAX;
29            res = min(res,rec(i-1)+(cost[i]-cost[i-1]).abs());
30            res = min(res,rec(i-2)+(cost[i]-cost[i-2]).abs());
31            dp[i] = res;    //追加
32            return res 
33        }
34    });
35    println!("{}",rec);
36}
37

とすると、

Rust
1cannot borrow `dp` as mutable, as it is a captured variable in a `Fn` closure
2cannot borrow as mutable

とエラーメッセージがでてしまいます。
キャプチャーされた環境をmutableで持ってくるには
どうしたらいいのでしょうか？

よろしくお願いします。

行動規範の内容に同意します

回答1件

ベストアンサー

こんにちは。
念のため確認ですが proconio は 0.3.6で合っていますでしょうか。以下、この前提の下回答します。

以前似たようなコードを見たことがあるのですが、安全には作れなくて実現不可能そうでした。
https://qiita.com/vain0x/items/90c9580aa34926160ac1
私もその後については知らないので筆者の方がどう解決されたかはコメントなどで訊いてみて下さい。

ここではとりあえず問題をメモ化再帰で解くコードを提示しようと思います。
再帰関数を使わずに recurse コンビネータを使っているのはクロージャで捕捉した値を利用したいからだと思いますが、その用途であれば自分で構造体を定義してメソッドを作れば書けます。

rust
1use proconio::input;
2use std::cmp::min;
3
4struct Memoize {
5    dp: Vec<i64>,
6    cost: Vec<i64>,
7}
8
9impl Memoize {
10    fn rec(&mut self, i: usize) -> i64 {
11        let inf = i64::MAX;
12        if self.dp[i] < inf {
13            //追加
14            return self.dp[i]; //追加
15        } //追加
16        if i == 0 {
17            return self.dp[0];
18        } else if i == 1 {
19            return self.dp[1];
20        } else {
21            let mut res = std::i64::MAX;
22            res = min(
23                res,
24                self.rec(i - 1) + (self.cost[i] - self.cost[i - 1]).abs(),
25            );
26            res = min(
27                res,
28                self.rec(i - 2) + (self.cost[i] - self.cost[i - 2]).abs(),
29            );
30            self.dp[i] = res; //追加
31            return res;
32        }
33    }
34}
35
36fn main() {
37    input! {
38        n:usize,
39        cost:[i64;n],
40    }
41    let inf = i64::MAX;
42    let mut dp = vec![inf; n];
43    dp[0] = 0;
44    dp[1] = (cost[1] - cost[0]).abs();
45
46    let rec = Memoize { dp, cost }.rec(n - 1);
47    println!("{}", rec);
48}