[Haskell-cafe] Re: Data.Ring -- Pre-announce

[John Van Enk]

Hi Heinrich,

Some comments:

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
> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20091231/7d2a2ec7/attachment.html