removing last element from the list

klacke <>
Thu May 26 12:36:54 CEST 2005


On Thu, May 26, 2005 at 09:55:27AM +0200, Raimo Niskanen wrote:
> That is a good implementation of a fifo queue. In fact it is
> the one the queue module in Erlang/OTP uses :-)

It is good. 

The technique if amortizing the cost of an operation such as
removing the last item of a queue and sort of "remember the previous
work" can be used on many datastructures.

Chris Okasaki wrote an entire book on that topic. 

http://www.amazon.co.uk/exec/obidos/ASIN/0521663504/qid=1117104079/sr=1-1/ref=sr_1_0_1/026-4716218-1856429

Most of the code in the Okasaki book amortize the cost of reversal of
lists. The same idea can sometimes be applied to integer arithmetcs
as well. Look at user contrib http://www.erlang.org/user.html#anal-1.0

/klacke


-- 
Claes Wikstrom                        -- Caps lock is nowhere and
http://www.hyber.org                  -- everything is under control          



More information about the erlang-questions mailing list