23 May
2005
23 May
'05
11:43 a.m.
On Mon, May 23, 2005 at 04:19:12PM +0200, Tomasz Zielonka wrote:
Are these operations really O(1) : (<|), (|>), viewL, viewR?
Yes, the amortized time of these operations is independent of the size of the sequence. Not worst case, but Haskell's laziness means most things are amortized anyway. Chris Okasaki's book "Purely Functional Data Structures" contains a number of implementations of deques with such bounds on these operations. There are even implementations of deques with O(1) worst case bounds, but these are quite a bit more complex.