I cannot say that I have been following the erlang mailing list day to day, but some quick googling indicates that no one has yet mentioned vlists or varrays here.<br><br><a href="http://en.wikipedia.org/wiki/VList">http://en.wikipedia.org/wiki/VList
</a><br><br>Just for fun I made a small test implementation in erlang (no optimizations, and probably a lot of bugs) and did some benchmarking against normal list operations with a list of 1000 and 10000 elements. Adding an element ( 
i.e. [ NewElement |  List ] ) is 3 times slower with lists, but the rest of the operations seem to be quite ok at least when doing the benchmarks with hipe compiled code. That is not bad considering for instance that lists:reverse/1 is a bif.
<br><br>$ erl -noshell -run vlists test 1000 -s erlang halt<br>        {insert,insert_last,iterate,first,last,reverse,length}<br>lists:  {250,22010,194,6,516,40,15}<br>vlists: {774,2507,213,6,3,16,22}<br><br>$ erl -noshell -run vlists test 10000 -s erlang halt
<br>        {insert,insert_last,iterate,first,last,reverse,length}<br>lists:  {1420,3536945,3353,11,5071,824,228}<br>vlists: {4250,27324,1760,6,5,5,23}<br><br>Now the vlists module is really using a list as a wrapper around hipe arrays. Is there anyone who can spot something which is apparently dangerous or could cause unexpected side effects with the way they are used here? Are hipe arrays garbage collected for instance? Can they be passed around between erlang nodes as other data structures? Any way to optimize the insert operation? Code is attached. 
<br><br>The paper by Phil Bagwell referenced at the end of the wikipedia page is worth reading. It states among other things that it is quite easy to change a vlist into a dynamic array with O(1) time for addition and deletion and where copying can be avoided altogether. It also describes how to write a deque using the same principles, and some other interesting pieces of information. I guess I will leave the varray and deque as an exercise to the reader if anyone is up to the challenge... :-)
<br><br>BR /Fredrik Svahn<br>