[plt-scheme] reverse operation - how fast?

Hans Oesterholt-Dijkema wrote:

> Dear All,
> 
> Could someone tell me what the performance impact
> is of the 'reverse' primitive in the code beneath:
> 
> *********************************************
> (define (get-element-from-fifo fifo)
>  (let ((elem (car (reverse (car fifo)))))
>    (set-car! fifo (reverse (cdr (reverse (car fifo)))))
>    elem))
> *********************************************

Reverse takes time proportional to the length of the list.
To avoid this work every time an element is to be removed
from the queue, you can keep two lists: one for insertion
and one for removal. When the removal list is empty,
you reverse the insertion list and use that as removal
queue.

See

<http://schemecookbook.org/view/Cookbook/FunctionalQueue>

-- 
Jens Axel Søgaard