Почему мне не нужно явно предоставлять заимствованную изменяемую переменную?

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

Вот программа:

use std::collections::HashMap;

fn main() {
    let n = 42; // hardcoded for simplicity
    let mut cache = HashMap::new();
    let answer = fib(n, &mut cache);
    println!("fib of {} is {}", n, answer);
}

fn fib(n: i32, cache: &mut HashMap<i32,i32>) -> i32 {
    if cache.contains_key(&n) {
        return cache[&n];
    } else {
        if n < 1 { panic!("must be >= 1") }

        let answer = if n == 1 {
            0
        } else if n == 2 {
            1
        } else {
            fib(n - 1, cache) + fib(n - 2, cache)
        };
        cache.insert(n, answer);
        answer
    }
}

Вот как я понимаю, что происходит:

  • В main let mut cache означает «Я хочу иметь возможность видоизменить эту хеш-карту (или переназначить переменную)».
  • Когда main вызывает fib, он передает &mut cache, чтобы сказать: «Я одолжил вам это, и вам разрешено его видоизменять».
  • В подписи fib cache: &mut Hashmap означает «Я ожидаю, что мне одолжат изменяемую HashMap - одолжу ее с разрешением на изменение».

(Пожалуйста, поправьте меня, если я ошибаюсь.)

Но когда fib рекурсивно вызывает fib(n -1, cache), мне не нужно использовать fib(n -1, &mut cache), и если я это сделаю, я получаю сообщение об ошибке: «не могу заимствовать неизменяемую локальную переменную cache как изменяемую». Хм? Это не неизменяемая локальная переменная, это изменяемое заимствование, верно?

Если я попробую fib(n - 1, &cache), я получу немного другую ошибку:

error: mismatched types:
expected `&mut std::collections::hash::map::HashMap<i32, i32>`,
   found `&&mut std::collections::hash::map::HashMap<i32, i32>`

Похоже, он говорит: «Я ожидал изменяемую ссылку и получил ссылку на изменяемую ссылку».

Я знаю, что fib дает взаймы в рекурсивном вызове, потому что, если он откажется от владения, он не сможет впоследствии вызвать cache.insert. И я знаю, что это не особый случай рекурсии, потому что, если я определю, что fib2 почти идентичен fib, я могу заставить их рекурсивно проходить друг через друга, и это будет работать нормально.

Почему мне не нужно явно передавать заимствованную изменяемую переменную?


recursion rust ownership
person Nathan Long    schedule 24.05.2015    source источник
comment
Вы можете передать право собственности, и функция вернет кортеж с ответом и кешем: PlayPen   -  person oli_obk    schedule 24.05.2015

Ответы (1)


arrow_upward
12
arrow_downward

Ваши три очка в значительной степени точны. Когда компилятор не позволяет вам передать &mut cache, это потому, что значение фактически уже заимствовано. Тип cache - &mut HashMap<i32, i32>, поэтому передача &mut cache приводит к значению типа &mut &mut HashMap<i32, i32>. Простая передача cache приводит к ожидаемому типу.

Конкретное сообщение об ошибке cannot borrow immutable local variable cache as mutable запускается, потому что переменная cache сама по себе не изменяема, хотя память, на которую она указывает (HashMap), является. Это потому, что объявление аргумента cache: &mut HashMap<i32, i32> не объявляет переменную mut. Это похоже на то, как let отличается изменчивостью от let mut. Rust поддерживает изменяемые аргументы, которые в этом случае будут выглядеть как mut cache: &mut HashMap<i32, i32>.

person Snorre    schedule 24.05.2015
comment
Хм. Я не знал, что у меня может быть изменяемое значение в неизменяемой переменной. Вы уверены? let mut cache = делает обе изменяемыми - есть ли способ объявить изменяемой только структуру? Кроме того, если я добавлю cache = &mut HashMap::new(); в начало fib, я получу ошибку времени жизни, но не то, что вы не можете повторно назначить эту ошибку переменной. - person Nathan Long; 24.05.2015
comment
Также: интересно, что это изменяемое заимствование, проверяется через тип. Спасибо, что помогли мне понять. :) - person Nathan Long; 24.05.2015
comment
@NathanLong Вы действительно можете иметь изменяемую ссылку в неизменяемой переменной. Это потому, что Rust просто нужно, чтобы изменяемая ссылка была уникальной: никакой другой фрагмент кода не может прочитать или изменить значение. Это часть средства проверки заимствований компилятора, чтобы убедиться, что все &mut гарантированно уникальны (для & этого не требуется). Поскольку переменные всегда уникальны (поскольку они принадлежат вам), неизменяемая ссылка &mut по-прежнему уникальна и, следовательно, может быть изменена. Вы также можете проверить это. :) - person Snorre; 24.05.2015
comment
Ах да, конечно. main может иметь хэш, который он намеревается видоизменить, но безвозвратно одалживает его print - я просто даю вам разрешение прочитать это, а не изменять. - person Nathan Long; 24.05.2015