Hi Heinrich, Some comments: On Thu, Dec 31, 2009 at 6:27 AM, Heinrich Apfelmus < apfelmus@quantentunnel.de> wrote:
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.
I think I like Ring more than Necklace or Tom's suggestion of Circular. I chose Ring simply because that's what I was searching for when I wanted the data structure. The package will be named data-ring, so that should hopefully be enough to clue in the user that it's not dealing with the mathematical concept.
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.
Done. I actually had it this way first, but had the hard problem of conceptualizing left/prev right/next. I added some comments to the documentation describing the metaphor using a rotating table so that left/right make sense.
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.
I hope I've addressed this in the extended documentation.
Second, there is the "off by one" issue. Does insert put elements left or right of the focus?
I've replaced insert/remove with insertL/R and removeL/R. The docs better explain their behavior. 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.)
Yes. The tests are junk. I'm replacing them. :) 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])
Working on this now.
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.
I'll see what I can do. I'm addressing complexity after everything else looks okay. I don't like balance or pack and am hoping to drop all of them from the API. 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.pdfhttp://www.cs.cmu.edu/%7Erwh/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.)
This bothers me only because checking the length means I need to run down the spine of the list. Perhaps I can convince my self to keep a memo of the respective lengths. Thanks for your feedback! /jve