[Haskell-cafe] Re: Doubly-linked zipper list w/ insert
apfelmus at quantentunnel.de
Wed Nov 7 13:16:26 EST 2007
Justin Bailey wrote:
> The other day I decided to implement a ring buffer with a current
> element (i.e. a doubly-linked zipper list). In order to allow inserts
> (and, in the future, deletes and updates), I have a special sentinel
> element called "Join" in the structure. When inserting, I find the
> join first, insert and then rebuild the buffer using circular
> programming techniques. This also allows the buffer to be converted
> back to a list. The current element can be changed by rotating right
> or left, which never fails. Rotating n positions takes n steps.
> I'm posting it here for comments and feedback. How could the structure
> be smarter? Would storing a unique ID with each element make more
> sense? Any comments on the space behavior under insert and rotates? I
> wanted to "maximize" sharing. Thanks in advance.
Do you really need to realize the cycle by sharing? I mean, sharing
doesn't go well with insertion / updates / deletion since each of these
operations breaks it and needs to restore it everywhere. In other words,
your insert takes O(n) time. I'd simply drop the sharing and use two
double ended queues (or something like that) instead
data Ring a = Ring (DeQueue a) a (DeQueue a)
-- pseudo-code missing lots of cases. I want views!
left (Ring (l' :< ls :> l) x (r :< rs :> r')) =
Ring (ls :> l :> x) r (rs :> r' :> l')
This way, you can implement update operations in O(1) time instead of
O(n). With a fancy random access queue like Data.Sequence , you can even
have rotations like rotL xs n in O(log n) time.
(I keep mixing up the meaning of rotL and rotR , does L push the
current element to the left or does it rotate the ring clockwise?)
More information about the Haskell-Cafe