Re: [rust-dev] purely function red-black tree
Hello, 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) - MK, 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: http://smallcultfollowing.com/babysteps/blog/2012/07/24/generalizing-inherited-mutability/ Niko Steve Jenson wrote: On Sat, Dec 15, 2012 at 7:15 PM, Patrick Walton pwal...@mozilla.com mailto:pwal...@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@mozilla.org https://mail.mozilla.org/listinfo/rust-dev ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] purely function red-black tree
On Sat, Dec 15, 2012 at 7:02 PM, Nathan nejuc...@gmail.com wrote: Also, traverse should probably belong in its own trait. It seems like traversal over keys *and* values is quite useful, because it's common for applications to need both, and doing a separate lookup when a traversal is already close to the value would be a shame (changing asymptotic bounds on some applications). There is already an Iter trait. Is traversal simply an Iter over either K or (K, V) ? Thanks, I converted my code to implement BaseIter (although my implementation of size_hint is a little hacky since I'm not tracking the size of the tree) The private methods are part of the RBMap specialization of the Map trait and are required to reduce boilerplate. They don't belong in a Map trait proper. The rust way to do this is to have the trait methods call helper functions which are in scope, but not attached to the trait, I believe. Aha, that helps things click for me. Thanks again, Steve ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] purely function red-black tree
Thanks, I started with this definition and implemented BaseIter for my
RBTree.
https://github.com/stevej/rustled/commit/85cf4340eb1c0b985e27a48fe2603e6b75ffcb45
size_hint returns None as I'm not tracking size. I think that's ok? It's
hard to tell from the BaseIter documentation.
On Mon, Dec 17, 2012 at 1:34 PM, Erick Tryzelaar
erick.tryzel...@gmail.comwrote:
Is it important for `traverse` to pass along an option type? Is it
important to inform end users that a key has been deleted? Or is that
implementation specific? If so, I suggest rewriting `traverse` to something
like this (assuming this actually works):
implK, V RBMapK, V: iter::BaseIter(K, V) {
pure fn each(f: fn((K, V))) {
match *self {
Leaf = (),
Tree(_, left, ref key, maybe_value, right) = {
left.traverse(f);
match maybe_value {
Some(ref value) = f((key, value)),
None = {},
}
right.traverse(f);
}
}
}
}
On Mon, Dec 17, 2012 at 11:46 AM, Graydon Hoare gray...@mozilla.comwrote:
On 12-12-17 11:28 AM, Graydon Hoare wrote:
On 12-12-14 03:51 PM, Steve Jenson wrote:
I recently ported Matt Might's Scala port of Okasaki's purely
functional
red-black tree to Rust and am looking for some feedback.
https://github.com/stevej/rustled/blob/master/red_black_tree.rs
I've written this for 0.4 and will update it with other feedback I've
received for 0.5 when that lands.
Nice! The only things I'd ask are:
- I can't tell at a glance (sorry, RB-trees are always very subtle)
whether this is an LLRB. If not, could you make it so? It's likely
just a simplification to a couple of the functions.
Er, except of course, there's also:
https://github.com/fawek/llrbt.rs
I think we need some better coordination of library development :)
-Graydon
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] purely function red-black tree
On Mon, Dec 17, 2012 at 11:46 AM, Graydon Hoare gray...@mozilla.com wrote: On 12-12-17 11:28 AM, Graydon Hoare wrote: On 12-12-14 03:51 PM, Steve Jenson wrote: I recently ported Matt Might's Scala port of Okasaki's purely functional red-black tree to Rust and am looking for some feedback. https://github.com/stevej/rustled/blob/master/red_black_tree.rs I've written this for 0.4 and will update it with other feedback I've received for 0.5 when that lands. Nice! The only things I'd ask are: - I can't tell at a glance (sorry, RB-trees are always very subtle) whether this is an LLRB. If not, could you make it so? It's likely just a simplification to a couple of the functions. Er, except of course, there's also: https://github.com/fawek/llrbt.rs I think we need some better coordination of library development :) That's a mutable LLRB tree whereas mine is immutable. Since the language provides optional mutability, is it a goal to have both pure functional and mutable versions of common data structures and traits? ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] purely function red-black tree
On 12-12-18 04:56 PM, Steve Jenson wrote: That's a mutable LLRB tree whereas mine is immutable. Ah. Good point. Since the language provides optional mutability, is it a goal to have both pure functional and mutable versions of common data structures and traits? In some sense. Specifically, some number of container types will wind up multiply-implemented between managed an immutable and owned and freezable/thawable, since they have different semantics. Immutable managed types often permit substructure sharing between multiple copies of the type. Owned types, if built carefully, just lose their mutator methods when accessed through an immutable owner[1]. One can go a step further and make a third managed and mutable version of a datatype sometimes too, but (we hope) that will be rarer. -Graydon [1] Which is, incidentally, rad. ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] purely function red-black tree
On 12-12-17 11:28 AM, Graydon Hoare wrote: On 12-12-14 03:51 PM, Steve Jenson wrote: I recently ported Matt Might's Scala port of Okasaki's purely functional red-black tree to Rust and am looking for some feedback. https://github.com/stevej/rustled/blob/master/red_black_tree.rs I've written this for 0.4 and will update it with other feedback I've received for 0.5 when that lands. Nice! The only things I'd ask are: - I can't tell at a glance (sorry, RB-trees are always very subtle) whether this is an LLRB. If not, could you make it so? It's likely just a simplification to a couple of the functions. Er, except of course, there's also: https://github.com/fawek/llrbt.rs I think we need some better coordination of library development :) -Graydon ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] purely function red-black tree
Is it important for `traverse` to pass along an option type? Is it
important to inform end users that a key has been deleted? Or is that
implementation specific? If so, I suggest rewriting `traverse` to something
like this (assuming this actually works):
implK, V RBMapK, V: iter::BaseIter(K, V) {
pure fn each(f: fn((K, V))) {
match *self {
Leaf = (),
Tree(_, left, ref key, maybe_value, right) = {
left.traverse(f);
match maybe_value {
Some(ref value) = f((key, value)),
None = {},
}
right.traverse(f);
}
}
}
}
On Mon, Dec 17, 2012 at 11:46 AM, Graydon Hoare gray...@mozilla.com wrote:
On 12-12-17 11:28 AM, Graydon Hoare wrote:
On 12-12-14 03:51 PM, Steve Jenson wrote:
I recently ported Matt Might's Scala port of Okasaki's purely functional
red-black tree to Rust and am looking for some feedback.
https://github.com/stevej/rustled/blob/master/red_black_tree.rs
I've written this for 0.4 and will update it with other feedback I've
received for 0.5 when that lands.
Nice! The only things I'd ask are:
- I can't tell at a glance (sorry, RB-trees are always very subtle)
whether this is an LLRB. If not, could you make it so? It's likely
just a simplification to a couple of the functions.
Er, except of course, there's also:
https://github.com/fawek/llrbt.rs
I think we need some better coordination of library development :)
-Graydon
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] purely function red-black tree
Would this trait:
pub trait MapK: Copy Eq Ord, V: Copy {
pure fn get(k: K) - @OptionV;
pure fn put(k: K, v: V) - self;
pure fn delete(k: K) - self;
pure fn traverse(f: fn((K), (@OptionV)));
}
be something that ought to live somewhere in the standard library?
I also see that you have an impl of this trait in which you also define a
bunch of methods that don't belong to the trait. I didn't even know that
was possible! If you feel that those methods (blacken, modifiedWith,
balance, modWith) don't belong in the Map trait, perhaps split their
definitions off into a separate anonymous impl for now, and then when 0.5
rolls around you can define a trait that inherits from the Map trait and
requires those additional methods.
On Fri, Dec 14, 2012 at 6:51 PM, Steve Jenson ste...@fruitless.org wrote:
I recently ported Matt Might's Scala port of Okasaki's purely functional
red-black tree to Rust and am looking for some feedback.
https://github.com/stevej/rustled/blob/master/red_black_tree.rs
I've written this for 0.4 and will update it with other feedback I've
received for 0.5 when that lands.
Thanks!
Steve
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] purely function red-black tree
On Sat, Dec 15, 2012 at 11:46 AM, Patrick Walton pwal...@mozilla.comwrote:
On 12/15/12 8:58 AM, Benjamin Striegel wrote:
Would this trait:
pub trait MapK: Copy Eq Ord, V: Copy {
pure fn get(k: K) - @OptionV;
pure fn put(k: K, v: V) - self;
pure fn delete(k: K) - self;
pure fn traverse(f: fn((K), (@OptionV)));
}
be something that ought to live somewhere in the standard library?
Yes, probably, although it shouldn't have @s in it for the benefit of
those who don't want to use the garbage collector.
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?
I also see that you have an impl of this trait in which you also define
a bunch of methods that don't belong to the trait. I didn't even know
that was possible!
It's not possible in 0.5.
What is the rationale for making this impossible?
Thanks,
Steve
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] purely function red-black tree
On Sat, Dec 15, 2012 at 4:45 PM, Steve Jenson ste...@fruitless.org wrote:
On Sat, Dec 15, 2012 at 8:58 AM, Benjamin Striegel ben.strie...@gmail.com
wrote:
Would this trait:
pub trait MapK: Copy Eq Ord, V: Copy {
pure fn get(k: K) - @OptionV;
pure fn put(k: K, v: V) - self;
pure fn delete(k: K) - self;
pure fn traverse(f: fn((K), (@OptionV)));
}
be something that ought to live somewhere in the standard library?
I just renamed it to PersistentMap as a mutable Map would not typically
return itself on modification, that's a hallmark of a functional persistent
data structure.
Also, traverse should probably belong in its own trait.
It seems like traversal over keys *and* values is quite useful,
because it's common for applications to need both, and doing a
separate lookup when a traversal is already close to the value would
be a shame (changing asymptotic bounds on some applications).
There is already an Iter trait. Is traversal simply an Iter over
either K or (K, V) ?
I also see that you have an impl of this trait in which you also define a
bunch of methods that don't belong to the trait. I didn't even know that was
possible! If you feel that those methods (blacken, modifiedWith, balance,
modWith) don't belong in the Map trait, perhaps split their definitions off
into a separate anonymous impl for now, and then when 0.5 rolls around you
can define a trait that inherits from the Map trait and requires those
additional methods.
The private methods are part of the RBMap specialization of the Map trait
and are required to reduce boilerplate. They don't belong in a Map trait
proper.
The rust way to do this is to have the trait methods call helper
functions which are in scope, but not attached to the trait, I
believe.
There's a design choice here about implementations of traits that isn't
clear to me. Why restrict any given implementation of them to publicly
defined methods?
From an abstract type standpoint, all trait impls are *only* the
methods declared in the trait.
I'll go out on a limb and guess that this also makes the compiler and
runtime simpler, because the representation of an impl is the same
across all types for a given trait. I'm not sure that's true, just a
guess.
There's nothing to stop impl methods from calling other functions
whose privacy is protected by the module system, so impls can use
type-specific helper code.
Also, can you show me an example of using an anonymous trait? That seems
neat.
Best,
Steve
Regards,
Nathan Wilcox
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] purely function red-black tree
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.
What is the rationale for making this impossible?
You can put private methods on the anonymous trait associated with the
type instead. Say `implK:Copy Eq Ord, V:Copy RBMapK,V { ... }` (i.e.
leave off the trait) to put methods in the anonymous trait.
Patrick
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] purely function red-black tree
On 12/15/12 7:15 PM, Patrick Walton wrote: However, if you modify the algorithm to use unique pointers throughout, then your methods like get() can probably return a borrowed pointer instead. To add: For anyone interested in making data structures that don't use the garbage collector, look at the manually-memory-managed map here: https://github.com/mozilla/rust/blob/master/src/libcore/send_map.rs It's probably the best example of a GC-free data structure so far. Patrick ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
