Data.Ring -- Pre-announce

newer
Haskell Weekly News: Issue 146 -...

John Van Enk

31 Dec 2009 31 Dec '09

4:59 a.m.

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

Attachments:

attachment.html (text/html — 959 bytes)

Show replies by date

Luke Palmer

31 Dec 31 Dec

5:50 a.m.

On Thu, Dec 31, 2009 at 2:59 AM, 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:

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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

John Van Enk

2:56 p.m.

Hi Luke, Thanks for the feedback. I had some follow up comments. On Thu, Dec 31, 2009 at 5:50 AM, Luke Palmer 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

Daniel Fischer

5:54 a.m.

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)

...

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

John Van Enk

2:58 p.m.

Hi Daniel, Some follow up on your comments: On Thu, Dec 31, 2009 at 5:54 AM, Daniel Fischer 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

Heinrich Apfelmus

6:27 a.m.

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

9:29 a.m.

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

wren ng thornton

9 Jan 9 Jan

6:45 p.m.

Tom Tobin wrote:

...

----- Heinrich Apfelmus 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

16 Jan 16 Jan

1:40 p.m.

wren ng thornton schrieb:

...

Tom Tobin wrote:

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

11:40 p.m.

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 On Sat, Jan 16, 2010 at 1:40 PM, Henning Thielemann < schlepptop@henning-thielemann.de> wrote:

...

wren ng thornton schrieb:

Tom Tobin wrote:

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

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

John Van Enk

31 Dec 31 Dec

3:06 p.m.

Hi Heinrich, Some comments: 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 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

3:29 p.m.

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

John Van Enk

4:13 p.m.

I've decided to settle on Data.CircularList. The renamed git repository is here: http://github.com/sw17ch/data-clist On Thu, Dec 31, 2009 at 3:29 PM, Twan van Laarhoven wrote:

...

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

Twan

Iavor Diatchki

5:37 p.m.

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 On Thu, Dec 31, 2009 at 1:13 PM, John Van Enk wrote:

...

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

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

On Thu, Dec 31, 2009 at 3:29 PM, Twan van Laarhoven wrote:

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

Twan

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

David Leimbach

5:41 p.m.

I recently needed a ring buffer in haskell, so I did it in C and used the FFI :-) This is much nicer. Dave On Thu, Dec 31, 2009 at 2:37 PM, Iavor Diatchki wrote:

...

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

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

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

On Thu, Dec 31, 2009 at 3:29 PM, Twan van Laarhoven wrote:

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

On Thu, Dec 31, 2009 at 1:13 PM, John Van Enk wrote: 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-Rin...

...
Twan

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

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

Daniel Fischer

6:05 p.m.

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

1 Jan 1 Jan

7:36 a.m.

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

Jim Snow

31 Dec 31 Dec

1:48 p.m.

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

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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Wouter Swierstra

4 Jan 4 Jan

5:35 a.m.

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

8:51 a.m.

On Thu, 2009-12-31 at 04:59 -0500, 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.

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

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

9:17 a.m.

On Mon, Jan 4, 2010 at 6:51 AM, Maciej Piechotka 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

9:19 a.m.

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. On Mon, Jan 4, 2010 at 9:17 AM, Luke Palmer wrote:

...

On Mon, Jan 4, 2010 at 6:51 AM, Maciej Piechotka 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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Maciej Piechotka

3:13 p.m.

On Mon, 2010-01-04 at 07:17 -0700, Luke Palmer wrote:

...

On Mon, Jan 4, 2010 at 6:51 AM, Maciej Piechotka 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

6:14 p.m.

On Tue, Jan 5, 2010 at 5:13 AM, Maciej Piechotka wrote:

...

On Mon, 2010-01-04 at 07:17 -0700, Luke Palmer wrote:

...
On Mon, Jan 4, 2010 at 6:51 AM, Maciej Piechotka 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

5 Jan 5 Jan

2:53 a.m.

On Mon, Jan 4, 2010 at 1:13 PM, Maciej Piechotka 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

9:50 a.m.

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 On Tue, Jan 5, 2010 at 2:53 AM, Luke Palmer wrote:

...

On Mon, Jan 4, 2010 at 1:13 PM, Maciej Piechotka 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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

5603

Age (days ago)

5620

Last active (days ago)

List overview

Download

25 comments

16 participants

participants (16)

Daniel Fischer
David Leimbach
Derek Elkins
Edward Kmett
Heinrich Apfelmus
Henning Thielemann
Iavor Diatchki
Jim Snow
John Van Enk
Luke Palmer
Maciej Piechotka
Tillmann Rendel
Tom Tobin
Twan van Laarhoven
Wouter Swierstra
wren ng thornton