Подтвердить что ты не робот

Запись функции фиксированной точки в 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 `[[email protected]/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?

4b9b3361

Ответ 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}>>>, но он отказался это сделать. В результате нам нужно прибегнуть к сохранению Box<Fn(T) -> R>, так как мы не можем явно указать тип замыкания.

Наконец, мы должны построить новое замыкание, которое берет второй дескриптор в fixed, распаковывает его и вызывает его. Опять же, мы не можем использовать fixed как вызываемый напрямую. Мы также не можем повторно использовать закрытие внутри fixed, потому что для этого нам нужно будет поместить его внутри своего Rc, и в этот момент все начинает сходить с ума.

... более сумасшедший.

Наконец, мы должны вернуть это второе замыкание в Box, потому что, как я сказал ранее, мы не можем вернуть замыкания по значению, потому что мы не можем назвать их типы в сигнатуре.

* глубокий вдох *

Если у кого-то есть более простое решение, я бы хотел его увидеть.: P

Ответ 2

Начиная с того места, где вы остановились:

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

Возвращаемый объект имеет тип неподъемного закрытия. Использование общего типа не поможет здесь, так как тип закрытия определяется вызываемым абонентом, а не вызывающим. Heres, где полезные черты impl:

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

Мы не можем передать fix(func) в func, потому что он ожидает тип имен для F. Ну, вместо этого нужно согласиться на объект-признак:

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

Теперь пришло время сражаться с пожизненной шашкой. Компилятор жалуется:

only named lifetimes are allowed in `impl Trait`, but `` was found in the type `…`

Это несколько загадочное сообщение. Поскольку по умолчанию свойства tra обычно 'static, это круговой способ сказать: "закрытие не достаточно долго для 'static". Чтобы получить реальное сообщение об ошибке, добавьте + 'static в impl Fn(T) -> R и перекомпилируйте:

closure may outlive the current function, but it borrows `func`, which is owned by the current function

Итак, это была настоящая проблема. Он заимствует func. Нам не нужно брать func, потому что fn Copy, поэтому мы можем дублировать его столько, сколько хотим. Допустим закрытие с помощью move и избавьтесь от + 'static от ранее:

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

И вуаля, это работает! Ну, почти... вам нужно отредактировать guess_loop и изменить fn(T) -> () на &Fn(T) -> (). Im действительно очень поразило, что это решение не требует каких-либо распределений.

Если вы не можете использовать черты impl, вы можете вместо этого написать:

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

который, к сожалению, не является бесплатным.

Кроме того, мы можем немного обобщить результат, чтобы разрешить произвольные закрытия и сроки жизни:

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

В процессе выяснения решения вашей проблемы я закончил тем, что написал более простую версию fix, которая на самом деле привела меня к решению вашей функции fix:

type Lazy<'a, T> = Box<FnBox() -> T + 'a>;

// fix: (Lazy<T> -> T) -> T
fn fix<'a, T, F>(f: F) -> T
    where F: Fn(Lazy<'a, T>) -> T + Copy + 'a
{
    f(Box::new(move || fix(f)))
}

Вот демонстрация того, как эта функция fix может быть использована для вычисления факториала:

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

Ответ 3

Это ответ на мой собственный вопрос об использовании Y combinator, который является подмножеством этого вопроса. В чистом выражении лямбда версия Y combinator выглядит как

λf.(λw.w w)(λw.f (w w))

Решение в Rosetta Code является слишком сложным и используется Box для распределения памяти в куче. Я хочу упростить это.

Во-первых, пусть вместо этого реализует тип Mu<T> как символ.

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

Обратите внимание, что нам нужно, чтобы этот признак был безопасным для объекта, что означает, что мы не можем запрашивать Self в любом из его определений, поэтому второй параметр вводится &Mu<T>, и это объект-признак.

Теперь мы можем написать общую реализацию trait:

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

С этим теперь мы можем написать Y combinator следующим образом:

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

Вышеприведенная компиляция в Rust playground без включения каких-либо функций и использования только стабильного канала, так что это довольно хороший ответ на мой вопрос.

Однако вышеизложенное не будет работать на практике, потому что Rust - это вызов по значению, но код выше - это вызов по имени Y combinator.

Решение по умолчанию

Чтобы работать со стабильным каналом без каких-либо функций, мы не можем вернуть закрытие (что требует impl Trait). Вместо этого я придумал другой тип Mu2, который принимает два типа параметров:

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

Как и выше, давайте реализовать этот новый признак.

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

Новый Y combinator:

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

Теперь пришло время протестировать наш новый объект.

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

Результаты в:

3628800

Все сделано!

Вы можете видеть, что функция y имеет немного отличающуюся подпись, чем вопросник fix, но это не имеет значения.

Прямая повторяющаяся версия

Такую же технологию, чтобы избежать возврата замыкания, можно использовать и для обычной прямой повторяющейся версии:

fn fix<T, R, F>(f: &F, t: T) -> R
where
    F: Fn(&Fn(T) -> R, T) -> R,
{
    f(&|t| fix(f, t), t)        
}

fn fib(i: i32) -> i32 {
    let fn_ = &|f:&Fn(i32) -> i32, x| if x < 2 { x } else { f(x-1) + f(x-2) };
    fix(fn_, i)
}

В принципе, всякий раз, когда вам нужно вернуть замыкание из функции, вы можете добавить параметр закрытия в функцию и изменить тип возврата на тип возврата закрытия. Позже, когда вам нужно реальное закрытие, просто создайте закрытие, частично оценив эту функцию.

Дальнейшие обсуждения

Сравните с другими языками, в Rust существует большая разница: функция, заданная для нахождения фиксированной точки, не должна иметь никаких внутренних состояний. В Rust это требование, чтобы параметр F типа y должен быть Fn, а не FnMut или FnOnce.

Например, мы не можем реализовать fix_mut, который будет использоваться как

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

    fix_mut(fn_, i)
}

без небезопасного кода, в то время как эта версия, если она работает, работает намного лучше (O (N)), чем версия, приведенная выше (O (2 ^ N)).

Это потому, что вы можете иметь только один &mut одного объекта за один раз. Но идея Y combinator или даже функция фиксированной точки требует захвата/передачи функции в то же время при ее вызове, двух ссылок, и вы не можете просто отметить любое из них неизменяемым без маркировки другого.

С другой стороны, мне было интересно, можем ли мы сделать что-то, что другие языки обычно не могут, но Rust, похоже, в состоянии. Я думал ограничить первый тип аргумента F от Fn до FnOnce (поскольку функция y обеспечит реализацию, изменение на FnMut не имеет смысла, мы знаем, что оно не будет иметь состояний, но изменение на FnOnce означает, что мы хотим, чтобы оно использовалось только один раз), Rust не разрешил бы на данный момент, поскольку мы не сможем передавать неспециализированный объект по значению.

Таким образом, эта реализация является наиболее гибким решением, о котором мы могли бы подумать.

Кстати, работа над непреложным ограничением заключается в использовании псевдо-мутации:

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

Ответ 4

Это можно сделать при нулевой стоимости исполнения, если вы хотите использовать нестабильные функции (т.е. ночной компилятор) и готовы... немного запутать ваш код.

Во-первых, нам нужно преобразовать результат fix в именованную структуру. Эта структура должна реализовывать Fn, поэтому мы реализуем ее вручную (это неустойчивая функция).

    #![feature(fn_traits)]
    #![feature(unboxed_closures)]

extern crate rand;

use rand::Rng;
use std::cmp::Ordering;

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
        }
    }
}

struct Fix<F>
    where F: Fn(i32, &Fix<F>)
{
    func: F,
}

impl<F> FnOnce<(i32,)> for Fix<F>
    where F: Fn(i32, &Fix<F>)
{
    type Output = ();

    extern "rust-call" fn call_once(self, args: (i32,)) -> Self::Output {
        self.call(args)
    }
}

impl<F> FnMut<(i32,)> for Fix<F>
    where F: Fn(i32, &Fix<F>)
{
    extern "rust-call" fn call_mut(&mut self, args: (i32,)) -> Self::Output {
        self.call(args)
    }
}

impl<F> Fn<(i32,)> for Fix<F>
    where F: Fn(i32, &Fix<F>)
{
    extern "rust-call" fn call(&self, (val,): (i32,)) -> Self::Output {
        (self.func)(val, self);
    }
}

fn fix<F>(func: F) -> Fix<F>
    where F: Fn(i32, &Fix<F>)
{
    Fix { func: func }
}

fn guess_loop<F>(actual: i32, recur: &F)
    where F: Fn(i32)
{
    let guess_int = rand::thread_rng().gen_range(1, 51);

    if guess_int != actual {
        recur(actual)
    }
}

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

    fix(guess_loop)(secret_number);
}

Однако мы еще не закончили. Это не скомпилируется со следующей ошибкой:

error[E0281]: type mismatch: the type `fn(i32, &_) {guess_loop::<_>}` implements the trait `for<'r> std::ops::Fn<(i32, &'r _)>`, but the trait `for<'r> std::ops::Fn<(i32, &'r Fix<fn(i32, &_) {guess_loop::<_>}>)>` is required (cyclic type of infinite size)
  --> src/main.rs:77:5
   |
77 |     fix(guess_loop)(secret_number);
   |     ^^^
   |
   = note: required by `fix`

Примечание. Если вы не знаете, в Rust каждая функция имеет свой собственный нулевой размер. Если функция является общей, то каждый экземпляр этой функции будет иметь свой собственный тип. Например, тип guess_loop::<X> будет сообщен компилятором как fn(i32, &X) {guess_loop::<X>} (как вы можете видеть в вышеприведенном сообщении об ошибке, кроме как с подчеркиваниями, где конкретный тип еще не был разрешен). Этот тип может быть принудительно применен к типу указателя функции неявно в некоторых контекстах или явно с литой (as).

Проблема заключается в том, что в выражении fix(guess_loop) компилятору необходимо создать экземпляр guess_loop, который является общей функцией, и похоже, что компилятор не может определить правильный тип для его создания с помощью, Фактически, тип, который мы хотели бы задать для параметра типа F, ссылается на тип guess_loop. Если бы мы записали его в стиле, описанном компилятором, тип будет выглядеть как fn(i32, &Fix<X>) {guess_loop::<Fix<&X>>}, где X заменяется самим типом (теперь вы можете увидеть, где "циклический тип бесконечного размера" происходит из).

Мы можем решить это, заменив функцию guess_loop на не-общую структуру (мы будем называть ее GuessLoop), которая реализует Fn, ссылаясь на себя. (Вы не можете сделать это с нормальной функцией, потому что вы не можете назвать тип функции.)

struct GuessLoop;

impl<'a> FnOnce<(i32, &'a Fix<GuessLoop>)> for GuessLoop {
    type Output = ();

    extern "rust-call" fn call_once(self, args: (i32, &Fix<GuessLoop>)) -> Self::Output {
        self.call(args)
    }
}

impl<'a> FnMut<(i32, &'a Fix<GuessLoop>)> for GuessLoop {
    extern "rust-call" fn call_mut(&mut self, args: (i32, &Fix<GuessLoop>)) -> Self::Output {
        self.call(args)
    }
}

impl<'a> Fn<(i32, &'a Fix<GuessLoop>)> for GuessLoop {
    extern "rust-call" fn call(&self, (actual, recur): (i32, &Fix<GuessLoop>)) -> Self::Output {
        let guess_int = rand::thread_rng().gen_range(1, 51);

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

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

    fix(GuessLoop)(secret_number);
}

Обратите внимание, что GuessLoop реализация Fn больше не является типичной для типа параметра recur. Что делать, если мы попытались сделать реализацию Fn generic (при этом оставив структуру не универсальной, чтобы избежать циклических типов)?

struct GuessLoop;

impl<'a, F> FnOnce<(i32, &'a F)> for GuessLoop
    where F: Fn(i32),
{
    type Output = ();

    extern "rust-call" fn call_once(self, args: (i32, &'a F)) -> Self::Output {
        self.call(args)
    }
}

impl<'a, F> FnMut<(i32, &'a F)> for GuessLoop
    where F: Fn(i32),
{
    extern "rust-call" fn call_mut(&mut self, args: (i32, &'a F)) -> Self::Output {
        self.call(args)
    }
}

impl<'a, F> Fn<(i32, &'a F)> for GuessLoop
    where F: Fn(i32),
{
    extern "rust-call" fn call(&self, (actual, recur): (i32, &'a F)) -> Self::Output {
        let guess_int = rand::thread_rng().gen_range(1, 51);

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

К сожалению, это не скомпилируется со следующей ошибкой:

error[E0275]: overflow evaluating the requirement `<Fix<GuessLoop> as std::ops::FnOnce<(i32,)>>::Output == ()`
  --> src/main.rs:99:5
   |
99 |     fix(GuessLoop)(secret_number);
   |     ^^^
   |
   = note: required because of the requirements on the impl of `for<'r> std::ops::Fn<(i32, &'r Fix<GuessLoop>)>` for `GuessLoop`
   = note: required by `fix`

По сути, компилятор не может проверить, что Fix<GuessLoop> реализует Fn(i32), потому что для этого ему необходимо проверить, что GuessLoop реализует Fn(i32, &Fix<GuessLoop>), но это верно только в том случае, если Fix<GuessLoop> реализует Fn(i32) (поскольку этот impl является условным), что справедливо только в том случае, если GuessLoop реализует Fn(i32, &Fix<GuessLoop>) (поскольку этот impl также является условным), который... вы получаете идею. Для слов две реализации Fn здесь зависят друг от друга, и компилятор не может это решить.