Hi Heinrich, Some comments:
On Thu, Dec 31, 2009 at 6:27 AM, Heinrich Apfelmus < [email protected]> 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.pdf<http://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
_______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
