removing last element from the list

[Raimo Niskanen]

That is a good implementation of a fifo queue. In fact it is
the one the queue module in Erlang/OTP uses :-)

ok@REDACTED (Richard A. O'Keefe) writes:

> 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|).
> 

-- 

/ Raimo Niskanen, Erlang/OTP, Ericsson AB