[Haskell-cafe] Re: Why no merge and listDiff?
Will Ness wrote: > Heinrich Apfelmus writes: > >> (Just for historical reference, credit for the data structure that works >> with infinite merges goes to Dave Bayer, I merely contributed the >> mnemonic aid of interpreting it in terms of VIPs.) > > yes, yes, my bad. GMANE is very unreliable at presenting the discussion > threads > in full. :| I saw it first on the Haskellwiki page though, and it was your > code > there, that's the reason for my mistake. :) No worries, doesn't count as mistake for none intended. :) In fact, I'm flattered. ;) Regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Why no merge and listDiff?
Heinrich Apfelmus quantentunnel.de> writes: > > Will Ness wrote: > > You can check it out on the Haskellwiki Prime Numbers page (work still in > > progress, the comparison tables are missing). We had also a recent thread here > > in cafe under "FASTER primes". The original idea of Heinrich Apfelmus of > > treefold merging the composites really panned out. > > (Just for historical reference, credit for the data structure that works > with infinite merges goes to Dave Bayer, I merely contributed the > mnemonic aid of interpreting it in terms of VIPs.) > > Regards, > Heinrich Apfelmus > > -- > http://apfelmus.nfshost.com > yes, yes, my bad. GMANE is very unreliable at presenting the discussion threads in full. :| I saw it first on the Haskellwiki page though, and it was your code there, that's the reason for my mistake. :) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Why no merge and listDiff?
Will Ness wrote: > You can check it out on the Haskellwiki Prime Numbers page (work still in > progress, the comparison tables are missing). We had also a recent thread > here > in cafe under "FASTER primes". The original idea of Heinrich Apfelmus of > treefold merging the composites really panned out. (Just for historical reference, credit for the data structure that works with infinite merges goes to Dave Bayer, I merely contributed the mnemonic aid of interpreting it in terms of VIPs.) Regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Why no merge and listDiff?
Derek Elkins gmail.com> writes: > > On Wed, Jan 20, 2010 at 9:42 AM, Will Ness yahoo.com> wrote: > > Derek Elkins gmail.com> writes: > >> On Sun, Jan 17, 2010 at 2:22 PM, Will Ness yahoo.com> wrote: > >> > Hello cafe, > >> > > >> > I wonder, if we have List.insert and List.union, why > >> > no List.merge (:: Ord a => [a] -> [a] -> [a]) > >> > and no List.minus ? These seem to be pretty general > >> > operations. > >> > >> You > >> probably also want to look at the package data-ordlist on hackage > >> (http://hackage.haskell.org/packages/archive/data- ordlist/0.0.1/doc/html/Data- > > OrdList.html) > >> which represents sets and bags as ordered lists and has all of the > >> operations you mention. > > > > > > I did, thanks again! Although, that package deals with non-decreasing lists, > > i.e. lists with multiples possibly. As such, its operations produce non- > > decreasing lists, i.e. possibly having multiples too. > > It is clear that some of the operations are guaranteed to produce sets > given sets. The documentation could be better in this regard though. > > The 'union' and 'minus' functions of ordlist meet this requirement if > you satisfy the preconditions. Yes, thanks, it's exactly what I was looking for. I've recognized from the code that `minus' was OK, but `merge' was different. As it turns out, OrdList.union is exactly what I have under `merge'. Better (or any at all really) documentation for Data.OrdList would be a big help. I don't know if it's at all easy to separate Sets and Bags, though it may seem desirable. I seem to have read something about Circle/Ellipse problem, i.e. the Sets/Bags problem which are not easily detachable from one another? Although I don't know the details of that. The background for this is my attempts to classify the various primes- generating code variants. Apparently, the essense of sieve is the composites removal, and both composites and natural numbers are naturally represented as strictly increasing lists. Same with merging the lists of multiples of each prime to construct the composites. I had to provide the `minus' and `merge' definitions along with the actual code and searched for something standard. You can check it out on the Haskellwiki Prime Numbers page (work still in progress, the comparison tables are missing). We had also a recent thread here in cafe under "FASTER primes". The original idea of Heinrich Apfelmus of treefold merging the composites really panned out. I found a little bit better structure for the folding tree, and Daniel Fischer was a great help in fixing the space leaks there (two of them) so that now the resulting code, with wheel optimization, runs very close to the PQ-based O'Neill's sieve (actually faster than it if interpreted in GHCi). More importantly (?) there's a natural progression of code now, straight from the classic Turner's sieve, so it's not an ad-hoc thing anymore. It also became apparent that the essence of prime wheels is Euler's sieve. And vice versa. :) Thanks a lot for all the help from all the posters! Cheers, ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Why no merge and listDiff?
On Wed, Jan 20, 2010 at 9:42 AM, Will Ness wrote: > Derek Elkins gmail.com> writes: >> On Sun, Jan 17, 2010 at 2:22 PM, Will Ness yahoo.com> wrote: >> > Hello cafe, >> > >> > I wonder, if we have List.insert and List.union, why no List.merge (:: Ord > a => >> > [a] -> [a] -> [a]) and no List.minus ? These seem to be pretty general >> > operations. >> >> Presumably by List.minus you mean the (\\) function in Data.List. > > No, it has to search its second list over and over from the start, to be able > to deal with unordered lists, so its performance can't be good. Then use the ordlist one. >> You >> probably also want to look at the package data-ordlist on hackage >> (http://hackage.haskell.org/packages/archive/data-ordlist/0.0.1/doc/html/Data- > OrdList.html) >> which represents sets and bags as ordered lists and has all of the >> operations you mention. > > > I did, thanks again! Although, that package deals with non-decreasing lists, > i.e. lists with multiples possibly. As such, its operations produce non- > decreasing lists, i.e. possibly having multiples too. It is clear that some of the operations are guaranteed to produce sets given sets. The documentation could be better in this regard though. > I meant strictly increasing ordered lists, without multiples, for which the > two > operations, 'merge' and 'minus', would also have to produce like lists, i.e > strictly increasing, without multiples. The 'union' and 'minus' functions of ordlist meet this requirement if you satisfy the preconditions. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Why no merge and listDiff?
Will Ness schrieb: > Christian Maeder dfki.de> writes: > >> Will Ness schrieb: >>> I meant strictly increasing ordered lists, without multiples, for which the > two >>> operations, 'merge' and 'minus', would also have to produce like lists, i.e >>> strictly increasing, without multiples. >> Why don't you use directly Data.Set? > > It says it's based on size balanced Trees? I initially wondered why no such > fundamental operations as merge and minus for _lists_, in the stadard > libraries? Yes, balanced trees, which makes insertion and member testing O(log n). > Also, its to/from list conversions are O(n), so probably won't work for > infinite lists. One should not convert much from and to list, but always use operations on sets directly. Sets are finite. I wonder what fundamental advantage there is for infinite strictly increasing lists. > > I was told the trend is to move specifics to hackage packages, but I wonder > why > shouldn't such fundamental operations be just included in standard Data.List? Both the current "Set" operations of Data.List and the (so many) functions from Data.Ordlist are only useful for short lists (or other special purposes) because of efficiency. Furthermore, there is some risk that the invariant of lists being (strictly) sorted is violated by accident (programming-error). The ...By-functions allow to further confuse orders. >> There are also bags aka multisets: >> http://hackage.haskell.org/package/multiset > > it's too seems to be based on trees. Yes. > Data.Ordlist seems to be a good match, except for its conflation of > ascending/non-decreasing lists under one "ordered" category (i.e. sets/bags > distinction). If you say, these should be two separate module, I would agree. Cheers Christian ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Why no merge and listDiff?
Christian Maeder dfki.de> writes: > Will Ness schrieb: > > I meant strictly increasing ordered lists, without multiples, for which the two > > operations, 'merge' and 'minus', would also have to produce like lists, i.e > > strictly increasing, without multiples. > > Why don't you use directly Data.Set? It says it's based on size balanced Trees? I initially wondered why no such fundamental operations as merge and minus for _lists_, in the stadard libraries? Also, its to/from list conversions are O(n), so probably won't work for infinite lists. I was told the trend is to move specifics to hackage packages, but I wonder why shouldn't such fundamental operations be just included in standard Data.List? > > I guess the first variety is more appropriate for bags, and the second one > > - for sets. The two would have to be de-conflated for that. (?) > > There are also bags aka multisets: > http://hackage.haskell.org/package/multiset it's too seems to be based on trees. Data.Ordlist seems to be a good match, except for its conflation of ascending/non-decreasing lists under one "ordered" category (i.e. sets/bags distinction). ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Why no merge and listDiff?
Will Ness schrieb: > I meant strictly increasing ordered lists, without multiples, for which the > two > operations, 'merge' and 'minus', would also have to produce like lists, i.e > strictly increasing, without multiples. Why don't you use directly Data.Set? > I guess the first variety is more appropriate for bags, and the second one - > for sets. The two would have to be de-conflated for that. (?) There are also bags aka multisets: http://hackage.haskell.org/package/multiset Cheers Christian ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Why no merge and listDiff?
Derek Elkins gmail.com> writes: > > On Sun, Jan 17, 2010 at 2:22 PM, Will Ness yahoo.com> wrote: > > Hello cafe, > > > > I wonder, if we have List.insert and List.union, why no List.merge (:: Ord a => > > [a] -> [a] -> [a]) and no List.minus ? These seem to be pretty general > > operations. > > Presumably by List.minus you mean the (\\) function in Data.List. No, it has to search its second list over and over from the start, to be able to deal with unordered lists, so its performance can't be good. > You > probably also want to look at the package data-ordlist on hackage > (http://hackage.haskell.org/packages/archive/data-ordlist/0.0.1/doc/html/Data- OrdList.html) > which represents sets and bags as ordered lists and has all of the > operations you mention. I did, thanks again! Although, that package deals with non-decreasing lists, i.e. lists with multiples possibly. As such, its operations produce non- decreasing lists, i.e. possibly having multiples too. I meant strictly increasing ordered lists, without multiples, for which the two operations, 'merge' and 'minus', would also have to produce like lists, i.e strictly increasing, without multiples. I guess the first variety is more appropriate for bags, and the second one - for sets. The two would have to be de-conflated for that. (?) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Why no merge and listDiff?
Derek Elkins gmail.com> writes: > > On Sun, Jan 17, 2010 at 2:22 PM, Will Ness yahoo.com> wrote: > > Hello cafe, > > > > I wonder, if we have List.insert and List.union, why no List.merge (:: Ord a => > > [a] -> [a] -> [a]) and no List.minus ? These seem to be pretty general > > operations. > > Presumably by List.minus you mean the (\\) function in Data.List. You > probably also want to look at the package data-ordlist on hackage > (http://hackage.haskell.org/packages/archive/data-ordlist/0.0.1/doc/html/Data- OrdList.html) > which represents sets and bags as ordered lists and has all of the > operations you mention. thanks for the pointers! > > Brief look into haskell-prime-report/list.html reveals nothing. > > > > Could we please have them? > > The trend is to remove things from "standard" libraries and to push > them more to 3rd party libraries hosted on hackage. understood. > > On the wider perspective, is their a way to declare an /ordered/ list on the > > type level (e.g. [1,2,3] would be one, but not [2,3,1])? Non-decreasing lists? > > Cyclical, or of certain length? What are such types called? > > There are a few ways to encode such things. The most direct route is > to use dependent types as Miguel mentioned, but Haskell has no support > for those. See languages like Agda or Coq. Another approach is to > use a type that specifically represents what you want and nothing > else. For example, a list of a set length is just a tuple. It is > easy to make a type that represents cyclic lists. Finally, the most > general method is to use an abstract data type to maintain the > invariant. It is trivial to handle ordered/non-decreasing lists in > this way. One note about the dependent types route is that the > ability to assert arbitrary properties comes with it the > responsibility to prove them later on. So you can make a function > which only accepts ordered lists, but then the users need to pass in a > proof that their lists are ordered when they use such functions and > these proofs can be a significant burden. Presumably a system would be able to prove - to know - by itself that [1..n] is an ordered list, to start with. The idea is to have a way of maintaining - and refining - our knowledge about objects we work on/with. I've also found out about refinement types, but the wikipedia page is _very_ sketchy. Presumably each function definition would automatically produce a part of proof for the values it produces, given the compliance of its inputs to their preconditions. A program built as a chain of such fuctions would automatically have its proof calculated for it. The goal, to illustrate it by way of example, is to be able to compile/simplify the expression ( x = sum $ take n $ cycle $ [1..m] ) into a straightforward math formula with some quotRem call in it. I think this would naturally extend to the constraint programming. All I have is some vague notions for now. :) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
