Persistent datatypes

[Aluminium95]

It would be great to be able to get some « persistent datatypes » the way clojure has because it allow the programmer to get some purely immutable variables without performances issues as wikipedia says.

Because Rust is able to handle unique boxes, and has a garbage collector, it will be « easy » to implement some of those persistent structures.

let myvec = ~[1, 8, 9];

let second = myvec.append (8); // creates a new vec (does not modify « myvec »)
let third = myvec.insert (8,1) // idem 

This would also allow to pass some immutable values between tasks, with an O(1) complexity and allow the task to « modify » the value with a near O(1) complexity ... This would be very great !

I found some articles about the implementation of such types in clojure :

• Persistent Vectors
• Persistent HashMaps

Then if this is possible, it would also be great to be able to specify that a variable is mutable only in a small block (like a function) in order to produce by mutation, an immutable value. For exemple to fill a vector with a function application and return a new immutable vector (sorry, I don't realy know the syntax of Rust ...)

fn new_vector_fill (func : &(fn(int) -> int), size : int) -> ~[int] {
    let mut vec = vector::new (size); // creates a new vector 
    // iterates over the vector and fill with « vec[i] = f(i) »
    return ~vec; // convert into a immutable value ...
}

Is it possible ? Would it be usefull ?

[thestinger]

Unique boxes are equivalent to a paired malloc/free in C, they don't use garbage collection and would have to copy.

A persistent data structure has to be implemented with @ (garbage collection) or Rc (reference counting). There's no global garbage collector so they won't be sendable between tasks, and Rc isn't sendable because it doesn't use atomic reference counting.

I have #4987 open about reimplementing the persistent tree to make it actually useful, and new bugs can be opened for other specific data structures. I don't think it really makes sense to have a metabug for this.

Realistically, concurrent access to persistent data structures would require implementing a global garbage collector for immutable data. There's extra::arc for sendable atomic reference counted types, but reference counting is only acceptable for persistent data structures with a low fanout, like 1 for a list, or 2 for a binary tree. For acceptable performance, most persistent data structures would require implementing a global garbage collector for immutable data.