[Haskell-cafe] Re: Doubly-linked zipper list w/ insert implementation

[apfelmus]

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?)


Regards,
apfelmus