Derek Elkins
On Wed, Jan 20, 2010 at 9:42 AM, Will Ness
wrote: Derek Elkins
writes: On Sun, Jan 17, 2010 at 2:22 PM, Will Ness
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,