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.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