On Thu, Dec 31, 2009 at 2:59 AM, John Van Enk
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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe