Например, сейчас если у вас есть функция, которая принимает параметром коллекцию и не меняет ее (например, считает что-то на основе данных в коллекции), то в Rust вам придется написать две версии такой функции: одну для immutable коллекции, и одну — для mutable, — потому что так сейчас устроена система типов.

Вы что-то путаете. В Rust мутабельность определяется не структурой самой по себе, а тем, что с ней можно сделать и в каком слоте она лежит.

Если вы создаёте, например, коллекцию, и хотите, чтобы кто-то мог её изменить, вы пишете методы, которые меняют коллекцию, так, чтобы они принимали &mut self. Методы, которые не меняют коллекцию, будут принимать просто &self. После этого вы можете вызывать изменяющие и неизменяющие методы, если структура лежит в мутабельной переменной, и только неизменяющие, если структура лежит в немутабельной переменной. Поэтому если вы не собираетесь менять коллекцию, вам понадобится только одна функция, которая принимает &; если же вы хотите менять коллекцию, в функцию вам понадобится передавать &mut:

pub struct SomeCollection<T> {
    // ...
}

impl<T: Copy> SomeCollection<T> {
    fn get(&self, i: uint) -> T { ... }
    fn set(&mut self, i: uint, v: T) { ... }
}

fn compute_something(coll: &SomeCollection<int>) -> int {
    // здесь можно вызвать coll.get():
    let x = coll.get(0);
    // но вызвать coll.set() нельзя, будет ошибка компиляции
    // coll.set(0, x+1); 
    x
}

fn compute_and_modify(coll: &mut SomeCollection<int>) -> int {
    // здесь можно и то, и другое
    let x = coll.get(0);
    coll.set(0, x+1);
    x
}

fn main() {
    // s1 - неизменяемый слот (переменная)
    let s1: SomeCollection<int> = SomeCollection { ... };

    // можно вызвать compute_something(), но не compute_and_modify()
    println!("{}", compute_something(&s1));
    // println!("{}", compute_and_modify(&mut s1));

    let mut s2 = s1;  // перемещаем в мутабельный слот
    // можно вызвать и то, и другое
    println!("{}", compute_something(&s2));
    println!("{}", compute_and_modify(&mut s2));
}