[Haskell-cafe] Data.Ring -- Pre-announce

[Jim Snow]

My first thoughts are that you could implement a Ring type using 
Data.Sequence [1], which is a sort of balanced binary tree where you can 
insert or remove elements at the beginning or end in amortized O(1) time.

You might have a data type like this:

data Ring a = Empty | Ring (Seq a) a

The main difference between a Ring and a Sequence seems to be that the 
former uses a particular element as the focus, whereas you can think of 
a Sequence as having a focus that's in between two elements.

Some advantages of using a Sequence rather than two lists are that you 
could then combine two rings in O(logn) time rather than O(n), and you 
can also find the n'th item to the right or left in log(n) time.  I 
suspect that lists may perform better if all you're doing is inserting 
and removing elements to the right or left, or rotating the ring.

I'm not sure about the worst case behavior of Data.Sequence.  The docs 
also explicitly say that sequences are finite.

-jim

[1] 
http://www.haskell.org/ghc/docs/latest/html/libraries/containers-0.3.0.0/Data-Sequence.html


John Van Enk wrote:
> Hi List,
>
> I recently needed a ring structure (circular list with bi-directional 
> access) and didn't see anything obvious on Hackage. I threw something 
> together fairly quickly and would like some feedback before tossing it 
> on Hackage.
>
> I'd really appreciate if some one would:
>
>    1. make sure the code looks goodish (127 lines with full docs)
>    2. make sure my tests look saneish
>
> If I hear nothing, I'll assume wild support and push to Hackage.
>
> Code: http://github.com/sw17ch/data-ring/blob/master/src/Data/Ring.hs
> Tests: http://github.com/sw17ch/data-ring/blob/master/tests/quickcheck.hs
> Package Root: http://github.com/sw17ch/data-ring
>
> Thanks ahead of time,
> John Van Enk
> ------------------------------------------------------------------------
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>