Optimized lists

Matthias Lang <>
Fri Mar 11 15:24:02 CET 2005


Zoltan Peter Toth writes:

 > The Erlang solution is really pretty straightforward, and may 
 > be an option for new code that uses only the new list structure.
 > But it would not solve the problem when we get a long conventional 
 > list that we don't want to handle and want to check its size with 
 > length().

 > Further on, transforming to/from conventional list would also be O(n).
 > Therefore I propose a change to the implementation of the Erlang 
 > list construct in the emulator.

Transforming a conventional list to one with the size in every element
will cost O(n), even if the emulator does it for you.

Or is the idea that the emulator be changed to _only_ allow
tail-size-in-every-element lists? The benefit is that length() becomes
O(1). The cost is O(n) space for all lists and O(n) extra execution
time for most string operations.

Matthias



More information about the erlang-questions mailing list