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
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 `impl RBMap { ... }` (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 Sat, Dec 15, 2012 at 4:45 PM, Steve Jenson wrote:
>
>
>
> On Sat, Dec 15, 2012 at 8:58 AM, Benjamin Striegel
> wrote:
>>
>> Would this trait:
>>
>> pub trait Map {
>> pure fn get(k: K) -> @Option;
>> pure fn put(k: K, v: V) -> self;
>> pure fn delete(k: K) -> self;
>> pure fn traverse(f: fn((&K), (@Option)));
>> }
>>
>> 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 Sat, Dec 15, 2012 at 8:58 AM, Benjamin Striegel
wrote:
> Would this trait:
>
> pub trait Map {
> pure fn get(k: K) -> @Option;
> pure fn put(k: K, v: V) -> self;
> pure fn delete(k: K) -> self;
> pure fn traverse(f: fn((&K), (@Option)));
> }
>
> 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.
> 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.
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?
Also, can you show me an example of using an anonymous trait? That seems
neat.
Best,
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 11:46 AM, Patrick Walton wrote:
> On 12/15/12 8:58 AM, Benjamin Striegel wrote:
>
>> Would this trait:
>>
>> pub trait Map {
>>pure fn get(k: K) -> @Option;
>>pure fn put(k: K, v: V) -> self;
>>pure fn delete(k: K) -> self;
>>pure fn traverse(f: fn((&K), (@Option)));
>> }
>>
>> 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 12/15/12 8:58 AM, Benjamin Striegel wrote:
Would this trait:
pub trait Map {
pure fn get(k: K) -> @Option;
pure fn put(k: K, v: V) -> self;
pure fn delete(k: K) -> self;
pure fn traverse(f: fn((&K), (@Option)));
}
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 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.
Patrick
___
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 Map {
pure fn get(k: K) -> @Option;
pure fn put(k: K, v: V) -> self;
pure fn delete(k: K) -> self;
pure fn traverse(f: fn((&K), (@Option)));
}
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 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
