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

[Heinrich Apfelmus]

John Van Enk wrote:
> Hi List,
> 
> I recently needed a ring structure (circular list with bi-directional
> access) and didn't see anything obvious on Hackage. I threw something
> together fairly quickly and would like some feedback before tossing it on
> Hackage.
> 
> I'd really appreciate if some one would:
> 
>    1. make sure the code looks goodish (127 lines with full docs)
>    2. make sure my tests look saneish
> 
> If I hear nothing, I'll assume wild support and push to Hackage.

But that's a neat data structure, thanks for putting it into a library.
:) Here my comments:


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.

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.



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.

Second, there is the "off by one" issue. Does  insert  put elements left
or right of the focus?

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

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])



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.

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



Regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com