[clean-list] support for OpenGl

Richard A. O'Keefe ok@cs.otago.ac.nz
Tue, 9 Jul 2002 12:08:14 +1200 (NZST)


I believe it was Geoffrey G Plitt <ggp@andrew.cmu.edu> who wrote:
	>2. does a constant-time functional queue implementation exist?
	
Constant *amortized* time, yes.  The classical back-to-back pair of lists
implementation is O(1) amortized time.

For general questions about functional data structures, a
superb resource is Chris Okasaki's book.  On-line, look for the 'Edison'
library.

In Clean, however, we have another option.  Clean's uniqueness typing
means that arrays with O(1) worst case access AND update are available
without leaving the pure functional model.  This means that the usual
imperative "rotating array segment" implementation of queues is directly
available with the same kind of performance bounds you'd get from an
imperative language.

(Mercury has the same uniqueness typing as Clean.  In Haskell you'd have
to use some kind of monad, perhaps the array monad.)