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

[John Van Enk]

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.

Code: http://github.com/sw17ch/data-ring/blob/master/src/Data/Ring.hs
Tests: http://github.com/sw17ch/data-ring/blob/master/tests/quickcheck.hs
Package Root: http://github.com/sw17ch/data-ring

Thanks ahead of time,
John Van Enk

[Luke Palmer]

On Thu, Dec 31, 2009 at 2:59 AM, John Van Enk <van...@gmail.com> 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:
>

> make sure the code looks goodish (127 lines with full docs)

Code looks okay. It suffers from the same persistence/amortization
problem as the classical functional queue; if you happen to shift from
one of the edge cases (eg. prev when the left is empty), you will get
degenerate time complexity, reversing that right list over and over.
See discussion at "Simple and efficient purely functional queues and
deques, by Chris Okasaki"; probably can adapt that solution to yours.
More of an academic interest, I doubt anyone will care about those
cases.

Ring is a comonad, so you can make it an instance of one if you want
to have some fun :-P

It seems weird that you would put the focus in the middle in fromList.
Overly strict. Why not just put it at the first element? (Also
easier to reason about)

I would consider considering a ring where *both* left and right were
infinite to be valid, but not when only one of them is infinite (when
they both are infinite, you will never get to reverse).

Luke

> make sure my tests look saneish
>
> If I hear nothing, I'll assume wild support and push to Hackage.
>
> Code: http://github.com/sw17ch/data-ring/blob/master/src/Data/Ring.hs
> Tests: http://github.com/sw17ch/data-ring/blob/master/tests/quickcheck.hs
> Package Root: http://github.com/sw17ch/data-ring
>
> Thanks ahead of time,
> John Van Enk
>

> _______________________________________________
> Haskell-Cafe mailing list
> Haskel...@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
_______________________________________________
Haskell-Cafe mailing list
Haskel...@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Daniel Fischer]

Am Donnerstag 31 Dezember 2009 10:59:54 schrieb John Van Enk:
> 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)

I think 'left' and 'right' aren't the optimal names. But I can't think of something
clearly better either. The same applies to 'remove'.

Please, flip the arguments in 'insert'. While ring `insert` el or insert ring el may seem
more natural (or not) and that argument order is nicer for foldl', consistency with the
argument order of Data.List.insert, Data.Set.insert and Data.Map.insert seems far more
important to me.

> 2. make sure my tests look saneish

Sort of. The code is so short and clear that testing it at all may hint at paranoia.
Jokes aside, prop_balance is a consequence of prop_list
(toList . balance . fromList === toList . fromList . toList . fromList;
toList . fromList === id ==> toList . fromList . toList . fromList === id).

prop_isEmpty :: [Int] -> Bool
prop_isEmpty [] = True == (isEmpty . fromList $ [])
prop_isEmpty l = False == (isEmpty . fromList $ l)

prop_isEmpty [] = isEmpty . fromList $ []
prop_isEmpty l = not . isEmpty . fromList $ l

or

prop_isEmpty l = null l == isEmpty (fromList l)

[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

[Tom Tobin]

On Thu, Dec 31, 2009 at 5:27 AM, Heinrich Apfelmus
<apfe...@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.

Is Necklace a known name for this data structure? If not Ring, I was
thinking Circular might be an appropriate name.

[John Van Enk]

Hi Luke,

Thanks for the feedback. I had some follow up comments.

On Thu, Dec 31, 2009 at 5:50 AM, Luke Palmer <lrpa...@gmail.com> wrote:

> Code looks okay. It suffers from the same persistence/amortization
> problem as the classical functional queue; if you happen to shift from
> one of the edge cases (eg. prev when the left is empty), you will get
> degenerate time complexity, reversing that right list over and over.
> See discussion at "Simple and efficient purely functional queues and
> deques, by Chris Okasaki"; probably can adapt that solution to yours.
> More of an academic interest, I doubt anyone will care about those
> cases.
>

Yes. I agree and did see it. I'm reading the paper and may implement some of
the stuff he talks about.

> Ring is a comonad, so you can make it an instance of one if you want
> to have some fun :-P
>

I plan on adding as many instances as I know and make sense to me. :)

> It seems weird that you would put the focus in the middle in fromList.
> Overly strict. Why not just put it at the first element? (Also
> easier to reason about)
>

It actually uses the first element as the focus, not the middle.

> I would consider considering a ring where *both* left and right were
> infinite to be valid, but not when only one of them is infinite (when
> they both are infinite, you will never get to reverse).
>

This would be neat, perhaps someday. I don't think this works well with my
current API. :(

Thanks again. :)

/jve

[John Van Enk]

Hi Daniel,

Some follow up on your comments:

On Thu, Dec 31, 2009 at 5:54 AM, Daniel Fischer <daniel.i...@web.de>wrote:

> Am Donnerstag 31 Dezember 2009 10:59:54 schrieb John Van Enk:
>
> > 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)
>
> I think 'left' and 'right' aren't the optimal names. But I can't think of
> something clearly better either. The same applies to 'remove'.
>
> Please, flip the arguments in 'insert'. While ring `insert` el or insert
> ring el may seem more natural (or not) and that argument order is nicer for
> foldl', consistency with the argument order of Data.List.insert,
> Data.Set.insert and Data.Map.insert seems far more important to me.
>

Done.

> > 2. make sure my tests look saneish
>
> Sort of. The code is so short and clear that testing it at all may hint at
> paranoia.
>
> Jokes aside, prop_balance is a consequence of prop_list
>
> (toList . balance . fromList === toList . fromList . toList . fromList;
>
> toList . fromList === id ==> toList . fromList . toList . fromList === id).
>
> prop_isEmpty :: [Int] -> Bool
>
> prop_isEmpty [] = True == (isEmpty . fromList $ [])
>
> prop_isEmpty l = False == (isEmpty . fromList $ l)
>
> prop_isEmpty [] = isEmpty . fromList $ []
>
> prop_isEmpty l = not . isEmpty . fromList $ l
>
> or
>
> prop_isEmpty l = null l == isEmpty (fromList l)
>
>
>

Agreed. I actually dislike all the tests... this is actually the first
package I've used QuickCheck to test with. I'm most likely going to redo the
test set shortly. I'll take this advice.

Thanks again.

/jve

[John Van Enk]

Hi Heinrich,

Some comments:

On Thu, Dec 31, 2009 at 6:27 AM, Heinrich Apfelmus <
apfe...@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

[Twan van Laarhoven]

John Van Enk wrote:
> Hi Heinrich,

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

The mathematical concept would likely also go in Data, unfortunately. See for
example Data.Monoid. If someone does at a Ring class sometime, it is very likely
to go into Data.Ring, which would lead to conflicts. In fact it already exists,
see the "monoids" package [1]

I would prefer the name RingList or CircularList. As long as you put the word
"ring" in the package description users will still find it when searching on
hackage.

[1]
http://hackage.haskell.org/packages/archive/monoids/0.1.25/doc/html/Data-Ring.html

Twan

[John Van Enk]

I've decided to settle on Data.CircularList. The renamed git repository is
here:

http://github.com/sw17ch/data-clist

[Iavor Diatchki]

Hi,
I usually refer to this structure as a RingBuffer, just an idea. If
you have the time, I would add rough complexity estimates to the
documentation for the different functions. Thanks for your work!
Happy new year,
Iavor

[David Leimbach]

I recently needed a ring buffer in haskell, so I did it in C and used the
FFI :-)

This is much nicer.

Dave

[Jim Snow]

My first thoughts are that you could implement a Ring type using
Data.Sequence [1], which is a sort of balanced binary tree where you can
insert or remove elements at the beginning or end in amortized O(1) time.

You might have a data type like this:

data Ring a = Empty | Ring (Seq a) a

The main difference between a Ring and a Sequence seems to be that the
former uses a particular element as the focus, whereas you can think of
a Sequence as having a focus that's in between two elements.

Some advantages of using a Sequence rather than two lists are that you
could then combine two rings in O(logn) time rather than O(n), and you
can also find the n'th item to the right or left in log(n) time. I
suspect that lists may perform better if all you're doing is inserting
and removing elements to the right or left, or rotating the ring.

I'm not sure about the worst case behavior of Data.Sequence. The docs
also explicitly say that sequences are finite.

-jim

[1]
http://www.haskell.org/ghc/docs/latest/html/libraries/containers-0.3.0.0/Data-Sequence.html

> ------------------------------------------------------------------------

[Daniel Fischer]

Am Donnerstag 31 Dezember 2009 23:41:13 schrieb David Leimbach:
> ï¿œI recently needed a ring buffer in haskell, so I did it in C

http://en.wikipedia.org/wiki/Non_sequitur_(logic)

[Tillmann Rendel]

Hi,

Iavor Diatchki schrieb:
> I usually refer to this structure as a RingBuffer.

Really?

According to my understanding, and to wikipedia [1], a ring buffer is a
data structure used to implement O(1) bounded FIFO queues with mutable
arrays.

So in a ring buffer, you have distinct reading and writing foci, while
in John's circular list, you have only one focus for reading and writing.

Tillmann

[1] http://en.wikipedia.org/wiki/Circular_buffer

[Wouter Swierstra]

Hi John,

> I threw something together fairly quickly and would like some feedback before tossing it on Hackage.
>
> I'd really appreciate if some one would:
>

> make sure the code looks goodish (127 lines with full docs)

> make sure my tests look saneish

A similar structure is used in XMonad where it's called a Stack (which
isn't a very good name). There are loads of QuickCheck properties in
the XMonad sources you might want to use. Hope this helps,

Wouter

[Maciej Piechotka]

Monad, MonadPlus, Applicative, Alternative, Foldable and Traversable.

About comonad - not exactly as every comonad is copointed and the only
possible way is extract Empty = _|_

Regards

[Luke Palmer]

On Mon, Jan 4, 2010 at 6:51 AM, Maciej Piechotka <uzytk...@gmail.com> wrote:
> About comonad - not exactly as every comonad is copointed and the only
> possible way is extract Empty = _|_

I think this module could be cleaned up by disallowing empty lists.
You have this nice semantic property that "every clist has a focus",
but when you add empty you have to add "unless it's empty". focus
returns a Maybe, isEmpty is necessary.

I mean, it could be that your use case requires empty clists and would
be uglier without empty, but think about it. I find in Haskell that
simplicity breeds simplicity; i.e. I'm willing to wager that whatever
algorithm you are using clist for will actually be cleaner if you got
rid of empty and modify the algorithm accordingly. We shall see
though...

Luke

[John Van Enk]

I've heard this a few times and am slowly becoming convinced of it. I'll try
my current use without the Empty and see how it goes.

Given that I've heard this from several places, I'll probably drop Empty.

[Maciej Piechotka]

On Mon, 2010-01-04 at 07:17 -0700, Luke Palmer wrote:
> On Mon, Jan 4, 2010 at 6:51 AM, Maciej Piechotka <uzytk...@gmail.com> wrote:
> > About comonad - not exactly as every comonad is copointed and the only
> > possible way is extract Empty = _|_
>
> I think this module could be cleaned up by disallowing empty lists.
> You have this nice semantic property that "every clist has a focus",
> but when you add empty you have to add "unless it's empty". focus
> returns a Maybe, isEmpty is necessary.
>
> I mean, it could be that your use case requires empty clists and would
> be uglier without empty, but think about it. I find in Haskell that
> simplicity breeds simplicity; i.e. I'm willing to wager that whatever
> algorithm you are using clist for will actually be cleaner if you got
> rid of empty and modify the algorithm accordingly. We shall see
> though...
>
> Luke

However then we lost the monoid (ok. I haven't send patch but please
accept[1]) along with alternative/monad plus - which is much more
popular, standard and useful then Copointed/Comonad.

Additionally it would introduce:
fromList [] = _|_

Is is somehow similar to 0 \in N - sometimes it is better to include it
sometimes to not include it.

Regards

[1]
> instance Monoid CList where
> mempty = Empry
> mappend = mplus

[Derek Elkins]

On Tue, Jan 5, 2010 at 5:13 AM, Maciej Piechotka <uzytk...@gmail.com> wrote:
> On Mon, 2010-01-04 at 07:17 -0700, Luke Palmer wrote:
>> On Mon, Jan 4, 2010 at 6:51 AM, Maciej Piechotka <uzytk...@gmail.com> wrote:
>> > About comonad - not exactly as every comonad is copointed and the only
>> > possible way is extract Empty = _|_
>>
>> I think this module could be cleaned up by disallowing empty lists.
>> You have this nice semantic property that "every clist has a focus",
>> but when you add empty you have to add "unless it's empty". �focus
>> returns a Maybe, isEmpty is necessary.
>>
>> I mean, it could be that your use case requires empty clists and would
>> be uglier without empty, but think about it. �I find in Haskell that
>> simplicity breeds simplicity; i.e. I'm willing to wager that whatever
>> algorithm you are using clist for will actually be cleaner if you got
>> rid of empty and modify the algorithm accordingly. �We shall see
>> though...
>>
>> Luke
>
> However then we lost the monoid (ok. I haven't send patch but please
> accept[1]) along with alternative/monad plus - which is much more
> popular, standard and useful then Copointed/Comonad.
>
> Additionally it would introduce:
> fromList [] = _|_

This isn't a big deal, it just means fromList is not appropriate
(which it is not, it should be fromNonEmptyList in this case. We can
of course, also, simply return Maybe (NonEmptyCList a) which works
out.

> Is is somehow similar to 0 \in N - sometimes it is better to include it
> sometimes to not include it.
>
> Regards
>
> [1]
>> instance Monoid CList where
>> � mempty = Empry
>> � mappend = mplus

This is a bigger issue, however, given a type with a associative
binary operation, a semigroup, we can complete it to a monoid using a
Maybe-like type constructor to formally attach a unit.

data AddUnit a = Unit | Value a

class SemiGroup a where op :: a -> a -> a -- associative

instance (SemiGroup a) => Monoid (AddUnit a) where
mempty = Unit
Unit `mappend` y = y
x `mappend` Unit = x
Val x `mappend` Val y = Val (x `op` y)

We then have,
type CList a = AddUnit (NonEmptyCList a)

[Luke Palmer]

On Mon, Jan 4, 2010 at 1:13 PM, Maciej Piechotka <uzytk...@gmail.com> wrote:
> However then we lost the monoid (ok. I haven't send patch but please
> accept[1]) along with alternative/monad plus - which is much more
> popular, standard and useful then Copointed/Comonad.

This point is a self-fulfilling prophecy. We don't have very much
experience working with copointeds and comonads, but I don't think
that makes them useless, just unfamiliar.

"One must never confuse what is natural with what is habitual." --
Mahatma Gandhi

Luke

[John Van Enk]

For those interested, the version of data-clist without Empty is here:

http://github.com/sw17ch/data-clist/tree/noEmpty

<http://github.com/sw17ch/data-clist/tree/noEmpty>

[wren ng thornton]

Tom Tobin wrote:

> ----- Heinrich Apfelmus <apfe...@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.
>
> Is Necklace a known name for this data structure? If not Ring, I was
> thinking Circular might be an appropriate name.

I'm not sure if there's a canonical name, except perhaps "circular
queue". Necklace is cute, though Circular or CircleQueue might be
better. I'd also advise strongly against using Ring in order to avoid
confusing nomenclature. (Loop should be avoided for similar reasons.)

--
Live well,
~wren

[Henning Thielemann]

wren ng thornton schrieb:

> Tom Tobin wrote:
>> ----- Heinrich Apfelmus <apfe...@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.
>>
>> Is Necklace a known name for this data structure? If not Ring, I was
>> thinking Circular might be an appropriate name.
>
> I'm not sure if there's a canonical name, except perhaps "circular
> queue". Necklace is cute, though Circular or CircleQueue might be
> better. I'd also advise strongly against using Ring in order to avoid
> confusing nomenclature. (Loop should be avoided for similar reasons.)

When reading "Ring" first time in the e-mail subject, I also thought it
would be about the algebraic structure with that name.

CircularList seems fine to me. Necklace is nice but might be missed when
someone searches for that data structure on Hackage.

[Edward Kmett]

One other name I've heard used, pretty much ever since the dos days when the
16 character fixed sized keyboard buffer was the first instance of such a
structure I'd seen, was a 'ring buffer'. Data.RingBuffer perhaps? I agree
that Data.Ring is a terrible name, partially because I already have a
Data.Ring in the monoids package!

-Edward Kmett