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

[Luke Palmer]

On Thu, Dec 31, 2009 at 2:59 AM, John Van Enk <vanenkj at gmail.com> 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:
>
> make sure the code looks goodish (127 lines with full docs)

Code looks okay.  It suffers from the same persistence/amortization
problem as the classical functional queue; if you happen to shift from
one of the edge cases (eg. prev when the left is empty), you will get
degenerate time complexity, reversing that right list over and over.
See discussion at "Simple and efficient purely functional queues and
deques, by Chris Okasaki"; probably can adapt that solution to yours.
More of an academic interest, I doubt anyone will care about those
cases.

Ring is a comonad, so you can make it an instance of one if you want
to have some fun :-P

It seems weird that you would put the focus in the middle in fromList.
 Overly strict.  Why not just put it at the first element?  (Also
easier to reason about)

I would consider considering a ring where *both* left and right were
infinite to be valid, but not when only one of them is infinite (when
they both are infinite, you will never get to reverse).

Luke

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