[erlang-questions] Data structures are strange things

[Robert Virding]

No, it is not surprising when you think about it. I just found it a bit surprising that the conventions which seem to apply to imperative languages have been more less imported into the functional/declarative world where they don't apply to the same degree. It seems that in the functional world going "red-black" seems to be accepted even though there aren't many benefits of it. The code is a little simpler, but for 2-3 trees the difference is very small. And it is faster for insertion and deletion.

----- Original Message -----
> If you take a look at a typical 2-3-4 tree implementation in Java
>     http://www.cs.berkeley.edu/~jrs/61bs02/hw/hw7/dict/Tree234.java
> >>  http://www.cs.berkeley.edu/~jrs/61bs02/hw/hw7/dict/Tree234Node.java
> you'll see nodes containing
> 
> 	an integer saying how many keys there are
> 	three keys
> 	four links to children nodes
> 	a link to a parent node
> 
> Allow one word for "what is the class of this object" and that's
> 10 words per node.
> 
> Using Erlang tuples, we'd have
> 	{K1,C0,C1}			4 words
> 	{K1,K2,C0,C1,C2}		6 words
> 	{K1,K2,K3,C0,C1,C2,C3}		8 words
> WAM-based Prolog systems would take the same space;
> SML/NJ should be able to shave a word off each (using the bottom
> 2 bits of a pointer to say which of the three cases applies).
> 
> In a functional language, when you make a change you create new
> nodes,
> so no node ever has to change size/shape.  You _could_ do that in
> Java
> too, but people often don't think of it.
> 
> It seems pretty clear that the Prolog/Erlang/SML version of a 2-3-4
> tree is going to take *less* space than a binary tree in the same
> language.  Since in these languages there is often a strong
> correlation
> between space and time, I find Robert Virding's results pleasant but
> not that surprising.
> 
> 
>