[rust-dev] purely function red-black tree

Niko Matsakis 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
> https://mail.mozilla.org/listinfo/rust-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20121220/9e075e7d/attachment.html>

More information about the Rust-dev mailing list