On 12/3/13 11:28 PM, Isaac Dupree wrote:
Is Rc the best smart pointer for persistent data structures?
I would think so, for non-thread safe ones.
Is it possible for the structure to be parametrized on smart pointer?
Not without higher kinded types (which eventually we do want--so the answer is "not yet").
Rc requires the contained data to be Freeze or Send or risk reference cycles.
I want to lift this restriction, BTW. Trying to prevent cycles through the type system has never really worked for us.
Gc requires T:'static (which means no borrowed pointers besides
&'static ones within the type).
Yes, but I wouldn't worry about this restriction biting users of your structure too much. Rust data structures rarely ever store non-static references in them, as the stack discipline that references must follow is fairly limited. (I can probably count the number of times I've put a non-static `&` reference into a dynamic vector on one hand, and I don't think I've ever put references into a hash map.)
Every Send type is 'static, but not
every Freeze type is 'static, so neither Rc nor Gc is strictly more flexible. Arc is Send, unlike either Rc or Gc, but has more overhead and can only contain Freeze+Send data; someone wanting to share persistence between tasks (conceivably for the sake of memory-use or asymptotic time) would want it.
Really what you want here for maximum flexibility is higher-kinded types and an implementation parameterized over Rc<T> or Arc<T>. That doesn't work in today's Rust, so you'll have to implement the data structure separately for non-thread-safe and thread-safe applications, unless you use macros. (Though often times you may want separate logic either way, necessitating a separate implementation. I'm not sure about the particular data structure you had in mind though.)
Is it possible to implement FromIterator<T> for List<T> without using O(n) temporary space or "unsafe" code? The problem is that the list comes out reversed in an obvious implementation. (O(n) stack space via recursion, or an O(n) intermediate data structure, or unsafely constructing a cons cell before constructing its tail.)
I think it should be possible to reverse the list after it's constructed, but then of course it has to be mutable (at least temporarily). Or you could carry around a pointer to the end of the list (which, again, requires mutation). I don't think this is solvable without mutation in a strict (non-lazy) language, unless I'm missing something.
Patrick _______________________________________________ Rust-dev mailing list [email protected] https://mail.mozilla.org/listinfo/rust-dev
