Optimized lists

[Zoltan Peter Toth]

Hi,

Currently there's no length information stored in the list elements, so
length/1 is an O(n) operation.
(This is not so nice if an application wants to safeguard against
operating on too long lists, but even length itself may last too long.)
However, list handling BIFs seem to count as a fixed number of
reductions, irrespectively of list length.
(See http://www.erlang.org/ml-archive/erlang-questions/200502/msg00168.html)

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

This way, length() would become an O(1) operation, 
[this may be a benefit if it's used frequently enough]
but also, the list BIFs could count as variable number
of reductions (based on length), keeping the real time behaviour.
Tail recursion would also work, as the length information in the
tail of the list would be correct too.

(Currently I think it is possible to call a BIF on a long list that keeps
the beam busy in that process so long that the net_ticktime elapses and
other nodes lose contact with the node. Am I wrong ?)

How feasible this would be to implement ?
(The more ambitious solution would be that if a list BIF would take more
than 1000 reductions (the limit for rescheduling) then it is scheduled out.
This part may be tricky, though.)
Cheers,
	Zoltan