Optimized lists

Matthias Lang matthias@REDACTED
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.


More information about the erlang-questions mailing list