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
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
