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/Dat... 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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe