[Haskell-cafe] Re: Why no merge and listDiff?
will_n48 at yahoo.com
Tue Jan 26 07:47:18 EST 2010
Derek Elkins <derek.a.elkins <at> gmail.com> writes:
> On Wed, Jan 20, 2010 at 9:42 AM, Will Ness <will_n48 <at> yahoo.com> wrote:
> > Derek Elkins <derek.a.elkins <at> gmail.com> writes:
> >> On Sun, Jan 17, 2010 at 2:22 PM, Will Ness <will_n48 <at> 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.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!
More information about the Haskell-Cafe