[rust-dev] purely function red-black tree

Nathan nejucomo at gmail.com
Sat Dec 15 19:02:14 PST 2012

On Sat, Dec 15, 2012 at 4:45 PM, Steve Jenson <stevej at fruitless.org> wrote:
> On Sat, Dec 15, 2012 at 8:58 AM, Benjamin Striegel <ben.striegel at gmail.com>
> wrote:
>> Would this trait:
>>     pub trait Map<K: Copy Eq Ord, V: Copy> {
>>       pure fn get(k: K) -> @Option<V>;
>>       pure fn put(k: K, v: V) -> self;
>>       pure fn delete(k: K) -> self;
>>       pure fn traverse(f: fn((&K), (@Option<V>)));
>>     }
>> 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

> 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

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

Nathan Wilcox

> _______________________________________________
> Rust-dev mailing list
> Rust-dev at mozilla.org
> https://mail.mozilla.org/listinfo/rust-dev

More information about the Rust-dev mailing list