在Rust中编写修复点函数

Question

我刚刚开始使用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功能？

Answer 1

首先,变量名称在初始化之后才存在.你不能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}>>>,但它拒绝这样做.因此,我们不得不求助于存储a Box<Fn(T) -> R>,因为我们无法明确地命名闭包的类型.

最后,我们必须构造一个新的闭包,它接受第二个句柄fixed,解包并调用它.同样,我们不能fixed直接用作可调用的.我们也无法在内部 重复使用闭包fixed,因为为了做到这一点,我们必须把它放在自己的内部Rc,在这一点上,事情开始变得疯狂.

...... 更疯狂

最后,我们必须在a中返回第二个闭包,Box因为正如我之前所说的,我们不能按值返回闭包,因为我们无法在签名中命名它们的类型.

*深呼吸*

如果有人有更简单的解决方案,我很乐意看到它.:P

Answer 2

从您上次停下的地方开始：

\n\n

fn fix<T, R, F>(func: fn(T, F) -> R) -> F\n    where F: Fn(T) -> R\n{\n    |val: T| func(val, fix(func))\n}\n

\n\n

返回的对象具有不可命名的闭包类型。使用泛型类型在这里不会有帮助，因为闭包的类型是由被调用者而不是调用者决定的。这里\xe2\x80\x99simpl特征派上用场：

\n\n

fn fix<T, R, F>(func: fn(T, F) -> R) -> impl Fn(T) -> R\n    where F: Fn(T) -> R\n{\n    |val: T| func(val, fix(func))\n}\n

\n\n

我们可以\xe2\x80\x99t 传递fix(func)给func，因为它需要 的​​可命名类型F。我们\xe2\x80\x99将不得不满足于一个trait对象：

\n\n

fn fix<T, R>(func: fn(T, &Fn(T) -> R) -> R) -> impl Fn(T) -> R {\n    |val: T| func(val, &fix(func))\n}\n

\n\n

现在是与生命周期检查器战斗的时候了。编译器抱怨：

\n\n

fn fix<T, R, F>(func: fn(T, F) -> R) -> F\n    where F: Fn(T) -> R\n{\n    |val: T| func(val, fix(func))\n}\n

\n\n

这是一条有点神秘的消息。由于 impl 特征总是\'static默认的，这是一种迂回的说法：\xe2\x80\x9c 对于 \xe2\x80\x9d 来说，闭包的寿命不够长\'static。为了获得真正的错误消息，我们附加+ \'static到impl Fn(T) -> R并重新编译：

\n\n

fn fix<T, R, F>(func: fn(T, F) -> R) -> impl Fn(T) -> R\n    where F: Fn(T) -> R\n{\n    |val: T| func(val, fix(func))\n}\n

\n\n

这才是真正的问题。是借 func。我们不需要借用 xe2x80x99，func因为fn是Copy，所以我们可以根据需要复制它。让\xe2\x80\x99s 在闭包前面添加move并删除+ \'static之前的：

\n\n

fn fix<T, R>(func: fn(T, &Fn(T) -> R) -> R) -> impl Fn(T) -> R {\n    move |val: T| func(val, &fix(func))\n}\n

\n\n

瞧，它有效了！好吧，几乎 \xe2\x80\xa6 你\xe2\x80\x99 必须编辑guess_loop并更改fn(T) -> ()为&Fn(T) -> (). 我\xe2\x80\x99m 实际上非常惊讶这个解决方案不需要\xe2\x80\x99t 任何分配。

\n\n

如果你可以\xe2\x80\x99t使用impl特征，你可以写：

\n\n

fn fix<T, R>(func: fn(T, &Fn(T) -> R) -> R) -> Box<Fn(T) -> R>\n    where T: \'static,\n          R: \'static\n{\n    Box::new(move |val: T| func(val, fix(func).as_ref()))\n}\n

\n\n

不幸的是，这不是免分配的。

\n\n

此外，我们可以稍微概括一下结果以允许任意的闭包和生命周期：

\n\n

fn fix<\'a, T, R, F>(func: F) -> impl \'a + Fn(T) -> R\n    where F: \'a + Fn(T, &Fn(T) -> R) -> R + Copy\n{\n    move |val: T| func(val, &fix(func))\n}\n

\n\n\n\n

在找出问题解决方案的过程中，我最终编写了一个更简单的版本fix，它实际上最终引导我找到了您的 fix函数的解决方案：

\n\n

type Lazy<\'a, T> = Box<FnBox() -> T + \'a>;\n\n// fix: (Lazy<T> -> T) -> T\nfn fix<\'a, T, F>(f: F) -> T\n    where F: Fn(Lazy<\'a, T>) -> T + Copy + \'a\n{\n    f(Box::new(move || fix(f)))\n}\n

\n\n

Here\xe2\x80\x99s 演示了如何使用此 fix函数来计算阶乘：

\n\n

fn factorial(n: u64) -> u64 {\n    // f: Lazy<u64 -> u64> -> u64 -> u64\n    fn f(fac: Lazy<\'static, Box<FnBox(u64) -> u64>>) -> Box<FnBox(u64) -> u64> {\n        Box::new(move |n| {\n            if n == 0 {\n                1\n            } else { \n                n * fac()(n - 1)\n            }\n        })\n    }\n    fix(f)(n)\n}\n

\n

Answer 3

这是我自己关于实现 Y 组合器的问题的答案，它是这个问题的子集。在纯 lambda 表达式中，Y 组合器的一个版本如下所示

\n\n

\xce\xbbf.(\xce\xbbw.w w)(\xce\xbbw.f (w w))\n

\n\n

Rosetta Code中的解决方案过于复杂，并且采用Box在堆中分配内存的方式。我想简化这个。

\n\n

首先，让我们将类型实现Mu<T>为特征。

\n\n

trait Mu<T> {\n    fn unroll(&self, &Mu<T>) -> T;\n}\n

\n\n

Self请注意，我们需要此特征是对象安全的，这意味着我们不能在其任何定义中要求，因此第二个参数是类型化的&Mu<T>并且它是一个特征对象。

\n\n

现在我们可以编写一个通用的trait实现：

\n\n

impl<T, F: Fn(&Mu<T>) -> T> Mu<T> for F {\n    fn unroll(&self, o: &Mu<T>) -> T {\n        self(o)\n    }\n}\n

\n\n

有了这个，我们现在可以将 y 组合器编写如下：

\n\n

fn y<T, F: Fn(T) -> T>(f: &F) -> T {\n    (&|w: &Mu<T>| w.unroll(w))(&|w: &Mu<T>| f(w.unroll(w)))\n}\n

\n\n

上面的代码在Rust 游乐场中编译，没有启用任何功能，并且仅使用稳定通道，所以这是对我的问题的一个很好的答案。

\n\n

然而，上面的代码在实践中不起作用，因为 Rust 是按值调用，但上面的代码是按名称调用 Y 组合器。

\n\n

按值调用解决方案

\n\n

为了在不需要任何功能的情况下使用稳定通道，我们不能返回闭包（这需要impl Trait）。相反，我想出了另一种Mu2带有两个类型参数的类型：

\n\n

trait Mu2<T, R> {\n    fn unroll(&self, &Mu2<T, R>, t: T) -> R;\n}\n

\n\n

如上所述，让我们实现这个新特征。

\n\n

impl<T, R, F> Mu2<T, R> for F\nwhere\n    F: Fn(&Mu2<T, R>, T) -> R,\n{\n    fn unroll(&self, o: &Mu2<T, R>, t: T) -> R {\n        self(o, t)\n    }\n}\n

\n\n

新的 Y 组合器：

\n\n

fn y<T, R, F>(f: &F, t: T) -> R\nwhere\n    F: Fn(&Fn(T) -> R, T) -> R,\n{\n    (&|w: &Mu2<T, R>, t| w.unroll(w, t))((&|w: &Mu2<T, R>, t| f(&|t| w.unroll(w, t), t)), t)\n}\n

\n\n

现在是时候测试我们的新设施了。

\n\n

fn main() {\n    let fac = &|f: &Fn(i32) -> i32, i| if i > 0 { i * f(i - 1) } else { 1 };\n    println!("{}", y(fac, 10))\n}\n

\n\n

结果是：

\n\n

trait Mu<T> {\n    fn unroll(&self, &Mu<T>) -> T;\n}\n

\n\n

全做完了！

\n\n

您可以看到该y函数的签名与提问者的签名略有不同fix，但这应该不重要。

\n\n

直接循环版本

\n\n

避免返回闭包的相同技术也可用于正常的直接循环版本：

\n\n

fn fix<T, R, F>(f: &F, t: T) -> R\nwhere\n    F: Fn(&Fn(T) -> R, T) -> R,\n{\n    f(&|t| fix(f, t), t)        \n}\n\nfn fib(i: i32) -> i32 {\n    let fn_ = &|f:&Fn(i32) -> i32, x| if x < 2 { x } else { f(x-1) + f(x-2) };\n    fix(fn_, i)\n}\n

\n\n

基本上，每当您需要从函数返回闭包时，都可以将闭包的参数添加到函数中，并将返回类型更改为闭包的返回类型。稍后，当您需要真正的闭包时，只需通过部分评估该函数来创建闭包。

\n\n

进一步讨论

\n\n

与其他语言相比，Rust 有一个很大的区别：用于查找不动点的函数不能有任何内部状态。在 Rust 中，要求 的F类型参数y必须是Fn，而不是FnMut或FnOnce。

\n\n

例如，我们不能实现fix_mut像这样使用的

\n\n

fn fib1(i: u32) -> u32 {\n    let mut i0 = 1;\n    let mut i1 = 1;\n    let fn_ = &mut |f:&Fn(u32) -> u32, x| \n        match x {\n            0 => i0,\n            1 => i1,\n            _ => {\n                let i2 = i0;\n                i0 = i1;\n                i1 = i1 + i2;\n                f(x)\n            }\n        };\n\n    fix_mut(fn_, i)\n}\n

\n\n

没有不安全的代码，而这个版本如果有效的话，性能比上面给出的版本 (O(2^N)) 好得多 (O(N))。

\n\n

&mut这是因为您一次只能拥有一个对象之一。但是 Y 组合器的想法，甚至是不动点函数，需要在调用它时同时捕获/传递该函数，这是两个引用，你不能只将它们中的任何一个标记为不可变而不标记另一个，所以。

\n\n

另一方面，我想知道我们是否可以做一些其他语言通常做不到的事情，但 Rust 似乎可以。F我正在考虑限制from Fnto的第一个参数类型FnOnce（因为y函数将提供实现，更改为FnMut没有意义，我们知道它不会有状态，但更改为FnOnce意味着我们希望它只使用一次），Rust 会目前不允许，因为我们无法按值传递未大小的对象。

\n\n

所以基本上，这个实现是我们能想到的最灵活的解决方案。

\n\n

顺便说一下，解决不可变限制的方法是使用伪突变：

\n\n

fn fib(i: u32) -> u32 {\n    let fn_ = &|f:&Fn((u32,u32,u32)) -> u32, (x,i,j)| \n        match x {\n            0 => i,\n            1 => j,\n            _ => {\n                f((x-1,j,i+j))\n            }\n        };\n    fix(&fn_, (i,1,1))\n}\n

\n