Optimized lists

[Matthias Lang]

Zoltan Peter Toth writes:

 > Idea:
 > Store in each list element the length of the remaining part of the list.
[...]

 > How feasible this would be to implement ?

Pretty straightforward:

   -module(zoltan).
   -compile([export_all]).
   
   from_list(List) ->
     from_list(lists:reverse(List), [], 0).
   
   from_list([], Acc, _) -> Acc;
   from_list([H|T], Acc, N) -> from_list(T, [{H, N}|Acc], N+1).
   
   to_list(List) -> [H || {H,_} <- List].
   
   length([]) -> 0;
   length([{_, N}|_]) -> N + 1.

I'm not sure many people will use it, given that it imposes even more
space overhead than lists already have.

Implementing it inside the runtime would be possible too, with likely
space and performance gains. I'm sure a bunch of people would
implement it right away, if only the Erlang source code wasn't kept a
closely guarded secret.

Matthias