www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Immutable Red-Black trees

reply "bearophile" <bearophileHUGS lycos.com> writes:
Bartosz Milewski has written the second article about immutable 
data structures in C++11, this time about Red-Black trees:
http://bartoszmilewski.com/2013/11/25/functional-data-structures-in-c-trees/

The C++11 code with few small changes (like using "enum class" 
instead of "enum"):
http://codepad.org/AEVVnfSc

D has GC and transitive immutability, so I have tried a D 
translation, a first draft:
http://dpaste.dzfl.pl/a48452af3

In the D code there are some problems with C++ lines as:
return RBTree(Color::R, RBTree(), x, RBTree());

And I don't know if this is public:
     Color rootColor() const {

Bye,
bearophile
Nov 25 2013
parent reply "Craig Dillabaugh" <craig.dillabaugh gmail.com> writes:
On Tuesday, 26 November 2013 at 00:28:34 UTC, bearophile wrote:

 Bartosz Milewski has written the second article about immutable 
 data structures in C++11, this time about Red-Black trees:
 http://bartoszmilewski.com/2013/11/25/functional-data-structures-in-c-trees/

 The C++11 code with few small changes (like using "enum class" 
 instead of "enum"):
 http://codepad.org/AEVVnfSc

 D has GC and transitive immutability, so I have tried a D 
 translation, a first draft:
 http://dpaste.dzfl.pl/a48452af3

 In the D code there are some problems with C++ lines as:
 return RBTree(Color::R, RBTree(), x, RBTree());

 And I don't know if this is public:
     Color rootColor() const {

 Bye,
 bearophile


What do you mean by an 'immutable' data structure.  The linked 
article talks about Persistent data structures.  Are these the 
same thing?

When I saw "Immutable" I figured it didn't support 
insertion/deletion - which would sort eliminate the need for a 
Red-Black tree anyways.
Nov 25 2013
next sibling parent reply "Craig Dillabaugh" <craig.dillabaugh gmail.com> writes:
On Tuesday, 26 November 2013 at 01:21:49 UTC, Craig Dillabaugh 
wrote:

 On Tuesday, 26 November 2013 at 00:28:34 UTC, bearophile wrote:


clip

 Bye,
 bearophile


 What do you mean by an 'immutable' data structure.  The linked 
 article talks about Persistent data structures.  Are these the 
 same thing?

 When I saw "Immutable" I figured it didn't support 
 insertion/deletion - which would sort eliminate the need for a 
 Red-Black tree anyways.


While I am at it, I might as well ask another question.  How is 
it that your 'insert' function is const?  I thought I understood 
const, but apparently not!

Cheers
Nov 25 2013
parent "bearophile" <bearophileHUGS lycos.com> writes:
Craig Dillabaugh:


 While I am at it, I might as well ask another question.  How is 
 it that your 'insert' function is const?  I thought I 
 understood const, but apparently not!


The D code I have linked is not yet working, so don't read too 
much in it.
But you can add items to an immutable tree, if you use structural 
sharing.

Bye,
bearophile
Nov 25 2013
prev sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Craig Dillabaugh:


 What do you mean by an 'immutable' data structure.  The linked 
 article talks about Persistent data structures.  Are these the 
 same thing?

 When I saw "Immutable" I figured it didn't support 
 insertion/deletion - which would sort eliminate the need for a 
 Red-Black tree anyways.


In those articles Bartosz is implementing in C++11 the immutable 
data structures from the book by Okasaki. Immutable doesn't mean 
you can't change them :-) It means you can't modify the single 
data items, and you have referential transparency.

Bye,
bearophile
Nov 25 2013
parent "Craig Dillabaugh" <craig.dillabaugh gmail.com> writes:
On Tuesday, 26 November 2013 at 01:31:11 UTC, bearophile wrote:

 Craig Dillabaugh:


 What do you mean by an 'immutable' data structure.  The linked 
 article talks about Persistent data structures.  Are these the 
 same thing?

 When I saw "Immutable" I figured it didn't support 
 insertion/deletion - which would sort eliminate the need for a 
 Red-Black tree anyways.


 In those articles Bartosz is implementing in C++11 the 
 immutable data structures from the book by Okasaki. Immutable 
 doesn't mean you can't change them :-) It means you can't 
 modify the single data items, and you have referential 
 transparency.

 Bye,
 bearophile


Ok, that make sense.
Nov 25 2013