Re: [Haskell-cafe] Re: Data.Ring -- Pre-announce
wren ng thornton schrieb: Tom Tobin wrote: - Heinrich Apfelmus apfel...@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. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Data.Ring -- Pre-announce
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 schlepp...@henning-thielemann.de wrote: wren ng thornton schrieb: Tom Tobin wrote: - Heinrich Apfelmus apfel...@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. ___ 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
Re: [Haskell-cafe] Re: Data.Ring -- Pre-announce
Tom Tobin wrote: - Heinrich Apfelmus apfel...@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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Data.Ring -- Pre-announce
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 From 5f8bb8eeaabe6d2b82cd68ba99272603b82d9c67 Mon Sep 17 00:00:00 2001 From: Maciej Piechotka uzytkown...@gmail.com Date: Mon, 4 Jan 2010 14:00:33 +0100 Subject: [PATCH 1/6] Added Monad instance --- src/Data/CircularList.hs |4 1 files changed, 4 insertions(+), 0 deletions(-) diff --git a/src/Data/CircularList.hs b/src/Data/CircularList.hs index 24e5bb9..17b7bba 100644 --- a/src/Data/CircularList.hs +++ b/src/Data/CircularList.hs @@ -230,3 +230,7 @@ instance Arbitrary a = Arbitrary (CList a) where instance Functor CList where fmap _ Empty = Empty fmap fn (CList l f r) = (CList (fmap fn l) (fn f) (fmap fn r)) + +instance Monad CList where +return = singleton +m = f = fromList $ concat $ toList $ fmap (toList . f) m -- 1.6.6 From a0841065478225c7d7beff39fc206ed6b4be35e8 Mon Sep 17 00:00:00 2001 From: Maciej Piechotka uzytkown...@gmail.com Date: Mon, 4 Jan 2010 14:01:33 +0100 Subject: [PATCH 2/6] Added MonadPlus instance --- src/Data/CircularList.hs |6 ++ 1 files changed, 6 insertions(+), 0 deletions(-) diff --git a/src/Data/CircularList.hs b/src/Data/CircularList.hs index 17b7bba..cfd39b6 100644 --- a/src/Data/CircularList.hs +++ b/src/Data/CircularList.hs @@ -66,6 +66,7 @@ module Data.CircularList ( isEmpty, size, ) where +import Control.Monad import Test.QuickCheck.Arbitrary import Test.QuickCheck.Gen @@ -234,3 +235,8 @@ instance Functor CList where instance Monad CList where return = singleton m = f = fromList $ concat $ toList $ fmap (toList . f) m + +instance MonadPlus CList where +mzero = Empty +(CList l v r) `mplus` c = (CList l v (r++toList c)) +Empty `mplus` c = c \ No newline at end of file -- 1.6.6 From 7ad6834537d63ba511ff37b2a490d89bde8a4a02 Mon Sep 17 00:00:00 2001 From: Maciej Piechotka uzytkown...@gmail.com Date: Mon, 4 Jan 2010 14:02:34 +0100 Subject: [PATCH 3/6] Added Applicative instance --- src/Data/CircularList.hs |5 + 1 files changed, 5 insertions(+), 0 deletions(-) diff --git a/src/Data/CircularList.hs b/src/Data/CircularList.hs index cfd39b6..09defe3 100644 --- a/src/Data/CircularList.hs +++ b/src/Data/CircularList.hs @@ -66,6 +66,7 @@ module Data.CircularList ( isEmpty, size, ) where +import Control.Applicative hiding (empty) import Control.Monad import Test.QuickCheck.Arbitrary import Test.QuickCheck.Gen @@ -232,6 +233,10 @@ instance Functor CList where fmap _ Empty = Empty fmap fn (CList l f r) = (CList (fmap fn l) (fn f) (fmap fn r)) +instance Applicative CList where +pure = return +(*) = ap + instance Monad CList where return = singleton m = f = fromList $ concat $ toList $ fmap (toList . f) m -- 1.6.6 From 8a49a4658ad5fc6da96cb688e4a8761415ac2678 Mon Sep 17 00:00:00 2001 From: Maciej Piechotka uzytkown...@gmail.com Date: Mon, 4 Jan 2010 14:03:38 +0100 Subject: [PATCH 4/6] Added Alternative instance --- src/Data/CircularList.hs |5 + 1 files changed, 5 insertions(+), 0 deletions(-) diff --git a/src/Data/CircularList.hs b/src/Data/CircularList.hs index 09defe3..ffbc735 100644 --- a/src/Data/CircularList.hs +++ b/src/Data/CircularList.hs @@ -67,6 +67,7 @@ module Data.CircularList ( ) where import Control.Applicative hiding (empty) +import qualified Control.Applicative import Control.Monad import Test.QuickCheck.Arbitrary import Test.QuickCheck.Gen @@ -237,6 +238,10 @@ instance Applicative CList where pure = return (*) = ap +instance Alternative CList where +empty = mzero +(|) = mplus + instance Monad CList where return = singleton m = f = fromList $ concat $ toList $ fmap (toList . f) m -- 1.6.6 From c930f1f86a676620df317ef0e3a90d52b527ca59 Mon Sep 17 00:00:00 2001 From: Maciej Piechotka uzytkown...@gmail.com Date: Mon, 4 Jan 2010 14:19:01 +0100 Subject: [PATCH 5/6] Added Foldable instance --- src/Data/CircularList.hs |8 +++- 1 files changed, 7 insertions(+), 1 deletions(-) diff --git a/src/Data/CircularList.hs b/src/Data/CircularList.hs index
Re: [Haskell-cafe] Re: Data.Ring -- Pre-announce
On Mon, Jan 4, 2010 at 6:51 AM, Maciej Piechotka uzytkown...@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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Data.Ring -- Pre-announce
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 lrpal...@gmail.com wrote: On Mon, Jan 4, 2010 at 6:51 AM, Maciej Piechotka uzytkown...@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 ___ 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
Re: [Haskell-cafe] Re: Data.Ring -- Pre-announce
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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Data.Ring -- Pre-announce
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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Data.Ring -- Pre-announce
On Thu, Dec 31, 2009 at 5:27 AM, Heinrich Apfelmus apfel...@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. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Data.Ring -- Pre-announce
Hi Heinrich, Some comments: On Thu, Dec 31, 2009 at 6:27 AM, Heinrich Apfelmus apfel...@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.pdfhttp://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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Data.Ring -- Pre-announce
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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Data.Ring -- Pre-announce
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 twa...@gmail.comwrote: 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Data.Ring -- Pre-announce
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 vane...@gmail.com 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 twa...@gmail.com 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-Ring.html 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
Re: [Haskell-cafe] Re: Data.Ring -- Pre-announce
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 iavor.diatc...@gmail.comwrote: 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 vane...@gmail.com 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 twa...@gmail.com 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-Ring.html 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Data.Ring -- Pre-announce
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) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
