[Haskell-cafe] Re: Why no merge and listDiff?

[Will Ness]

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/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,