I've implemented a persistent HAMT [1] a while back:
https://github.com/michaelwoerister/rs-persistent-datastructures/blob/master/hamt.rs
It's the data structure used for persistent maps in Clojure (and Scala,
I think). It's not too hard to implement and it's pretty nifty. I'm not
sure about the performance with atomic reference counting being used for
memory management. It will definitely be worse than with a
stop-the-world garbage collector. Although, it's noteworthy that look
ups in the data structure only have to copy one `Arc` for returning the
result, so the high fan-out of the data structure should not hurt if you
mostly read from it. I'd be very interested in a performance comparison
to other persistent map implementations in Rust (e.g. a red-black tree
or splay tree).
Here are some things I came across during implementing this:
* I too discovered that I couldn't parametrize on the type of reference
being used without higher kinded types. I did the implementation with
regular @ pointers at first and later switched to `Arc`, since
concurrent contexts are where persistent data structures really shine.
Switching the implementation from @ to Arc was pretty straight forward.
* I found there is no standardized trait for persistent maps in libstd
or libextra. It would be nice to have one!
* It's probably a very good idea to provide a non-persistent "builder"
that avoids the excessive copying during the insertion phase. In Clojure
one can switch between "transient" and persistent mode for a data
structure instance which also allows for optimized batch modifications.
An `insert_from(iterator)` method might also do the trick. There's quite
a bit of design space here.
* I would have liked to avoid some allocations and pointer chasing by
using fixed size vectors directly within nodes but I could not get that
to work without a lot of unsafe code that I was not sure would be
correct in all cases. So I just used owned vectors in the end.
Looking forward to seeing more in this area :)
-Michael
[1] https://en.wikipedia.org/wiki/Hash_array_mapped_trie
On 04.12.2013 08:28, Isaac Dupree wrote:
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
[email protected]
https://mail.mozilla.org/listinfo/rust-dev
_______________________________________________
Rust-dev mailing list
[email protected]
https://mail.mozilla.org/listinfo/rust-dev
