removing last element from the list

[Richard A. O'Keefe]

Gaspar Chilingarov <nm@REDACTED> wrote:
	are there any really fast ways to remove last element from list?
	
No.  However, there _is_ the standard "functional" representation for
queues:

hi_add(X, {L,R}) -> {[X|L],R}.

hi_rem({[X|L],R}) -> {X, {L,R}};
hi_rem({[],[X|R]} -> hi_rem(reverse([X|R])).

lo_add(X, {L,R}) -> {L,[X|R]}.

lo_rem({L,[X|R]}) -> {X, {L,R}};
lo_rem({[X|L],[]}) -> lo_rem(reverse([X|L])).

q_len({L,R}) -> length(L) + length(R).

q_empty({[],[]}) -> true;
q_empty(_) -> false.

	I need to implement something like FIFO,
	new elements inserted in list push old elements out.
	
Use the data structure above.  Use lo_add/2 to add new elements
	Q1 = lo_add(Elem, Q0)
and hi_rem/2 to remove old elements
	{Elem, Q1} = hi_rem(Q0)
Or of course you could use hi_add/2 to add and lo_rem/2 to remove.

This isn't constant time, but it is constant _average_ time when used
as a queue.  You do O(1) work to add an element and O(1) work *per element*
to reverse the list, although the peak cost per removal is O(|q_len|).