[rust-dev] purely function red-black tree

Graydon Hoare graydon at mozilla.com
Tue Dec 18 17:13:27 PST 2012

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.


[1] Which is, incidentally, rad.

More information about the Rust-dev mailing list