Im crate; vector.append... does not look immutable to a newbie

Hi there. I'm brand new, coming from a TypeScript, ClojureScript, and PureScript mindset.

I'm confused about something I'm seeing in the library for immutable data structures, im. I'm seeing an example for appending to a vector that looks like:

let mut vec = vector![1, 2, 3];
vec.append(vector![7, 8, 9]);
assert_eq!(vector![1, 2, 3, 7, 8, 9], vec);

As shown above and in the example for appending a vector does not return a new modified vector, but instead appears to mutate the vector in place. This seems like the opposite of an immutable data structure to my mindset and just looks like in-place mutation. What am I missing? I'm expecting it to be necessary to assign the result of vec.append(vector![7, 8, 9]) to a new name like:

new_vec = vec.append(vector![7, 8, 9]);

I'm not familiar with the library, but I guess you're using
"In-place Mutation". It seems that whether these data structures are immutable follows the basic rule¹ that a variable is mutable if and only if it's bound with the mut keyword, as yours is.

(¹ the big exception to which I understand to be interior mutability)

Immutability isn’t done for immutability’s sake but because it is useful in typical programming languages where everything can be shared. Shared mutability is the main problem that needs to be solved, and that’s the philosophy that Rust follows: mutable access (via &mut T references) is exclusive access.

As an effect, a function

fn foo(&mut T)

in Rust is – ignoring some potential performance benefits (and perhaps some ergonomic benefits) of the former – (almost [1]) equivalent to

fn foo(T) -> T

i.e. mutation is essentially the same as consuming a value and producing a new one of the same type.


Rust’s concept of ownership makes sure that a T -> T function can often/typically be implemented by modifying any heap data of the T in-place. The original T is consumed and a new one is produced; the implementation can operate by mutating things in-place, yet from the outside everything looks immutable.

With this in mind, most data structures in Rust are already “immutable” in this sense, including things like Vec<i32> from the standard library. The thing that sets data structures from crates like im apart from their standard library equivalents is that you can share them. An im::Vector<i32> only represents a handle to a some potentially shared data underneath the hood, you can clone it cheaply, unlike Vec<i32> which is expensive to clone, requiring allocation of new memory, and duplication of all the items.

The immutability of im::Vector<i32> then becomes apparent that despite im::Vector<i32> only being a handle to a shared datastructure, seemingly “modifying” the thing through methods such as .append will only modify what you see through the single handle you called the method on, while everyone else will continue to be able to observe the old value unmodified; the implementation will build a new data structure (it’s some kind of tree structure), re-using large chunks of the original two im::Vector<i32>s that you’re combining.

If you like, you could completely wrap up the append function in a more traditionally-immutable-looking function signature

fn append<T: Clone>(x: Vector<T>, y: Vector<T>) -> Vector<T> {
    let mut result = x;
    result.append(y);
    result
}

In fact, the opposite is possible, too, by making use of the standard library function std::mem::take

// mutable-looking append function, implemented using immutable-looking `append` from above
fn append_mut<T: Clone>(x: &mut Vector<T>, y: Vector<T>) {
    let x_value = std::mem::take(x);
    *x = append(x_value, y);
}

Compared to more pure function languages, this API approach, combined with the ownership+borrowing system of Rust also means that types like im::Vector can offer further optimizations. Since creating new “handles” to the same data by cloning the im::Vector is explicit, the implementation can track whenever a handle is the only/unique handle to a particular value, and fall back to more efficient actual in-place modification in that case.


  1. the only significant difference between the two is only apparent when you’re catching panics, I’ll not go into it here ↩︎

12 Likes

Thank you so much for this education! It is soooo helpful!

Note that it's not the immutable data structure but the persistent data structure.

4 Likes

Your explanation reminds me of great post by Niko – In Rust, ordinary vectors are values

3 Likes

That’s a great post, I hadn’t read that one before. Now that I have read it, I can highly recommend to OP [@i3enhamin] (and others) to read that, too, as it’s well-written and gives some additional context, while making similar overall points; note that AFAICT the “persistent” DVec vector that the linked “dogged” crate provides is indeed an “immutable data structure” in the same sense as im::Vector is, i.e. they are essentially the same kind of thing (though the precise choice of data structure is probably different), both offering O(1) time cloning and O(log n) time modification or insertion of single elements.

1 Like