[rust-dev] purely function red-black tree
niko at alum.mit.edu
Thu Dec 20 05:58:12 PST 2012
While Patrick's advice to avoid @ is good in general, in this case I
think it does not apply. Persistent or purely functional data
structures basically must use @ so that they can share pointers into
their internal nodes. I do hope that when Rust's libraries become more
mature we will offer a suite of persistent data structures like this
one. I expect that they will make use of distinct traits (it only makes
sense, since the operations are different: "addKey(K, V) -> M<K, V>"
instead of "put(K, V)", and so forth).
Traditional imperative data structures, though, are best designed to be
freezable, as Patrick said. That provides maximum flexibility to their
users. A freezable data structure (like the aforementioned send_map) is
one that uses only ~ pointers and has no mutability declarations. It
instead relies purely on inherited mutability. At some point we need to
write a tutorial on freezability, I've got one 25% finished but haven't
had time to revisit it. For now I think the best introduction is still
this old blog post:
Steve Jenson wrote:
> On Sat, Dec 15, 2012 at 7:15 PM, Patrick Walton <pwalton at mozilla.com
> <mailto:pwalton at mozilla.com>> wrote:
> On 12/15/12 4:38 PM, Steve Jenson wrote:
> I could use advice here. Is it possible for me to write a
> single trait
> that can be used by both users that want to use managed boxes
> and people
> who wish otherwise? IOW, what is the best way to abstract away
> the @sign
> in this trait?
> It depends on how you implement the red-black tree. With your
> current implementation, I think you're probably going to have to
> expose the GC to the user, because that implementation of
> red-black trees doesn't do manual memory management. There's no
> real way to abstract over methods of automatic storage reclamation
> in general (and adding such a mechanism would be pretty complex).
> If you're OK with having get() copy out the value instead of
> returning a reference to it, then you could avoid exposing the GC
> to the user, at the cost of copying every value you put in (which
> is not as bad as it sounds, since the cost of a copy of an @ box
> is practically zero). However, if you modify the algorithm to use
> unique pointers throughout, then your methods like get() can
> probably return a borrowed pointer instead.
> I'll tackle this within the next few days, once I understand send_map
> better. Thanks!
> Rust-dev mailing list
> Rust-dev at mozilla.org
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Rust-dev