[Haskell-cafe] Re: Data.Ring -- Pre-announce
John Van Enk
vanenkj at gmail.com
Thu Dec 31 15:06:36 EST 2009
On Thu, Dec 31, 2009 at 6:27 AM, Heinrich Apfelmus <
apfelmus at 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
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
> 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)
> (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
Thanks for your feedback!
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe