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.
But that's a neat data structure, thanks for putting it into a library. :) Here my comments: Since the name Ring is already taken by an ubiquitous mathematical structure, and thus already in hackage for example as Algebra.Ring in the numeric-prelude , I suggest to call the data structure Necklace instead. While we're at it, I'd also perform the following name changes: -- new focus = element to the left of the current focus prev - > left -- new focus = element to the right of the current focus next -> right left -> elementsLeft right -> elementsRight The problem with prev and next is that they are relative to a default direction and everybody would have to remember whether that was to the left or right. Since a necklace is inherently symmetric, I suggest to avoid imposing such a default direction. Furthermore, I think the documentation is lacking a few key points, first and foremost the explanation of what exactly a Ring (Necklace) is. While you can assume that people should know what a stack or queue is, this cannot be said for this little known data structure. Second, there is the "off by one" issue. Does insert put elements left or right of the focus? Third, I think the quickcheck tests are not very effective; instead of always converting to and from lists and testing how the operations behave, I suggest to focus on "intrinsic" laws, like for example (prev . next) x == x focus . insert a x == Just a and so on. (You do need one or two tests involving toList and fromList , but no more.) Also, you should make an instance Arbitrary a => Arbitrary (Necklace a) to replace the [Int] arguments that are just a proxy for an actual necklace. (Not to mention that thanks to parametric polymorphism, it is sufficient to test everything on the lists [1..n]) Last but not least, what about asymptotic complexity? While your operations are usually O(1), sometimes they are O(n). You provide a function balance to deal with the latter case, but the API is much more usable if you guarantee O(1) no matter what; please dispense with balance and friends. You can implement O(1) operations by using two queues instead of two lists as left and right part. Alternatively, you can adapt the rotation scheme for purely functional queues to your data structure and internally balance whenever one of the lists becomes for example 3x larger than the other one. See also chapter 3.4.2 of Chris Okasaki. Purely Functional Data Structures. (thesis) http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf (Not sure if 3 is a good size factor; this can be determined with the amortized cost/step graph c(a) = let b = a/(1+a)-1/2 in (b+1)/b where a is the size factor.) Regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com