recursion - 在Rust中编写固定点功能

我刚刚开始Rust教程，并使用递归以此类代码结束

extern crate rand;

use std::io;
use rand::Rng;
use std::cmp::Ordering;
use std::str::FromStr;
use std::fmt::{Display, Debug};

fn try_guess<T: Ord>(guess: T, actual: T) -> bool {
    match guess.cmp(&actual) {
        Ordering::Less => {
            println!("Too small");
            false
        }
        Ordering::Greater => {
            println!("Too big");
            false
        }
        Ordering::Equal => {
            println!("You win!");
            true
        }
    }
}

fn guess_loop<T: Ord + FromStr + Display + Copy>(actual: T)
    where <T as FromStr>::Err: Debug
{
    println!("PLease input your guess.");

    let mut guess = String::new();

    io::stdin()
        .read_line(&mut guess)
        .expect("Failed to read line");

    let guess_int: T = guess.trim()
        .parse()
        .expect("Should enter integer number");

    println!("You guessed {} !", guess_int);

    if !try_guess(guess_int, actual) {
        guess_loop(actual)
    }
}

fn main() {
    println!("Guess the number!!!");

    let secret_number = rand::thread_rng().gen_range(1, 51);

    guess_loop(secret_number);

}

我希望从guess_loop函数中排除递归，并引入了一个定点运算符:

fn guess_loop<T: Ord + FromStr + Display + Copy>(actual: T, recur: fn(T) -> ()) -> ()
    where <T as FromStr>::Err: Debug
{
    println!("PLease input your guess.");

    let mut guess = String::new();

    io::stdin()
        .read_line(&mut guess)
        .expect("Failed to read line");

    let guess_int: T = guess.trim()
        .parse()
        .expect("Should enter integer number");

    println!("You guessed {} !", guess_int);

    if !try_guess(guess_int, actual) {
        recur(actual)
    }
}

fn fix<T, R>(func: fn(T, fn(T) -> R) -> R) -> fn(T) -> R {
    fn fixed(val: T) -> R {
        func(val, fixed)
    }
    fixed
}

fn main() {
    println!("Guess the number!!!");

    let secret_number = rand::thread_rng().gen_range(1, 51);

    fix(guess_loop)(secret_number);
}

但这导致了许多错误，例如

error[E0401]: can't use type parameters from outer function; try using a local type parameter instead
  --> src/main.rs:49:19
   |
49 |     fn fixed(val: T) -> R {
   |                   ^ use of type variable from outer function

error[E0401]: can't use type parameters from outer function; try using a local type parameter instead
  --> src/main.rs:49:25
   |
49 |     fn fixed(val: T) -> R {
   |                         ^ use of type variable from outer function

error[E0434]: can't capture dynamic environment in a fn item; use the || { ... } closure form instead
  --> src/main.rs:50:9
   |
50 |         func(val, fixed)
   |         ^^^^

我的下一个尝试是将guess_loop的定义更改为

fn guess_loop<T: Ord + FromStr + Display + Copy, F>(actual: T, recur: F) -> ()
where <T as FromStr>::Err: Debug,
      F: Fn(T) -> ()
{ ... }

并将fix重新定义为

fn fix<T, R, F>(func: fn(T, F) -> R) -> F
    where F: Fn(T) -> R
{
    let fixed = |val: T| func(val, fix(func));
    fixed
}

这导致

error[E0308]: mismatched types
  --> src/main.rs:53:5
   |
53 |     fixed
   |     ^^^^^ expected type parameter, found closure
   |
   = note: expected type `F`
   = note:    found type `[closure@src/main.rs:52:17: 52:46 func:_]`

error: the type of this value must be known in this context
  --> src/main.rs:61:5
   |
61 |     fix(guess_loop)(secret_number);
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

如何编写类似的fix函数？

最佳答案

首先，变量名直到初始化后才存在。您不能让fixed这样引用自身。

其次，您不能从函数，句点按值返回闭包。泛型参数由调用方选择，并且调用方不知道函数内部闭包的类型。

我并不是说接下来是实现此目的的最佳方法，但这是我能够进行类型检查的最简单方法。

fn guess_loop<T>(actual: T, recur: &Fn(T)) -> ()
    where T: Ord + FromStr + Display + Copy,
          <T as FromStr>::Err: Debug
{
    // ...
}

fn fix<T, R, F>(func: F) -> Box<Fn(T) -> R>
    where T: 'static,
          R: 'static,
          F: Fn(T, &Fn(T) -> R) -> R + 'static
{
    use std::cell::RefCell;
    use std::rc::Rc;

    let fixed = Rc::new(RefCell::new(None));
    let fixed_fn = {
        let fixed = fixed.clone();
        move |val: T| -> R {
            let fixed_ref = fixed.borrow();
            let fixed_ref: &Box<_> = fixed_ref.as_ref().unwrap();
            func(val, &**fixed_ref)
        }
    };
    *fixed.borrow_mut() = Some(Box::new(fixed_fn));

    Box::new(move |val: T| -> R {
        let fixed_ref = fixed.borrow();
        let fixed_ref: &Box<_> = fixed_ref.as_ref().unwrap();
        fixed_ref(val)
    })
}

为了使fixed_fn能够引用其自身，我们必须创建一些内容以便在它存在之前从中读取。不幸的是，这意味着有一个循环，而Rust讨厌循环。因此，我们通过构造一个以RefCell<Option<_>>开头的引用计数的None来实现此目的，该引用将在以后进行变异以包含定点闭包。

其次，我们不能将此句柄用作可调用对象，因此我们必须显式拉出一个指向闭包的指针，以便可以将其传递给func。

第三，编译器似乎无法正确推断fixed的类型。我希望它能够确定它是Rc<RefCell<Option<{closure}>>>，但它拒绝这样做。结果，我们不得不求助于存储Box<Fn(T) -> R>，因为我们不能显式命名闭包的类型。

最后，我们必须构造一个新的闭包，它需要另一个句柄fixed，将其解压缩并调用它。同样，我们不能直接将fixed用作可调用对象。我们也不能重复使用fixed内的闭包，因为要做到这一点，我们必须将其放入自己的Rc内，到那时，事情开始变得疯狂起来。

...更加疯狂。

最后，我们必须以Box返回第二个闭包，因为正如我之前所说，由于无法在签名中命名其类型，因此无法按值返回闭包。

*深呼吸*

如果有人有一个更简单的解决方案，我很乐意看到它。 :P

关于recursion - 在Rust中编写固定点功能，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/44511030/