I'm interested in having persistent data structures[1] in Rust. To
start, I implemented the simplest one, the cons/nil list (it looks like
extra::list::List has another implementation of it). Am I using Rust
conventions properly?
My persistent list code:
https://github.com/idupree/rust-code/blob/master/persistent.rs
My next goal is a persistent tree-map, probably cribbing from Haskell's
Data.Map.
Is Rc the best smart pointer for persistent data structures? Is it
possible for the structure to be parametrized on smart pointer?
Rc requires the contained data to be Freeze or Send or risk reference
cycles. Gc requires T:'static (which means no borrowed pointers besides
&'static ones within the type). 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.
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.)
[1] https://en.wikipedia.org/wiki/Persistent_data_structure , like every
data structure in Haskell
-Isaac
_______________________________________________
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
