Re: [Haskell-cafe] ANN: combinatorics
On Wednesday 01 February 2012, 07:53:03, wren ng thornton wrote: The primes function in the combinat package is based on an old Cafe thread, and actually seems to be faster than the one in the combinatorics package. Yes, but it has a memory leak. On my box at least, with ghc 6.12, 7.0 and 7.2. The primes generator was some old code I had laying around for one of those online programming challenges; fast enough for the task. I'll probably trade it in for your algorithm though. Why not use one of the packages on hackage which offer faster prime generators? I'm aware of the following usable packages: - primes: decentish performance if you don't need to sieve high, but not recommendable if you want to sieve above ~10^7, in my measurements about the same performance as the algorithm used in combinat, but without memory leak. - NumberSieves: The O'Neill sieve, about twice as fast as the primes sieve, uses less memory (and scales better if you want to sieve to higher limits). - arithmoi: A segmented Eratosthenes sieve using mutable unboxed arrays. Much faster than the above and uses less memory. If you don't like arrays, it also has a priority queue sieve similar to the O'Neill sieve, but with a more efficient PQ implementation. One of the things I'm disappointed by about the current implementation is the memory overhead for storing the primes. It'd be nice to use chunked arrays of unboxed integers in order to remove all the pointers; but my attempt at doing so had catastrophic performance... arithmoi's Eratosthenes sieve offers the option to get a list of sieve chunks, basically UArray Int Bool, which gives far more compact storage than a list of Integers (~33KB per million range, much more compact than an unboxed array of primes for the reachable ranges) from which the list of primes can rather efficiently obtained when needed. That may do what you want well enough. Cheers, Daniel ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: combinatorics
On 2/5/12 10:21 AM, Daniel Fischer wrote: Why not use one of the packages on hackage which offer faster prime generators? Mostly because I hadn't looked, having had the code already laying around. I'm not opposed to it, however another goal is to remain portable to other compilers, which means being H98/H2010 compliant. NumberSieves uses BangPatterns, but that would be easily remedied if the author is willing; arithmoi looks quite nice, however it is GHC-only. -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: combinatorics
On Sunday 05 February 2012, 23:14:35, wren ng thornton wrote: On 2/5/12 10:21 AM, Daniel Fischer wrote: Why not use one of the packages on hackage which offer faster prime generators? Mostly because I hadn't looked, having had the code already laying around. Yeah, that's fine, it was just I'll probably trade it in for your algorithm though. that made me wonder. I'm not opposed to it, however another goal is to remain portable to other compilers, which means being H98/H2010 compliant. A noble goal. NumberSieves uses BangPatterns, but that would be easily remedied if the author is willing; arithmoi looks quite nice, however it is GHC-only. The curse of striving for efficiency. Portability is on the to-do list (with low priority, however). It just climbed a place. Cheers, Daniel ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: combinatorics
On 2/5/12 5:40 PM, Daniel Fischer wrote: On Sunday 05 February 2012, 23:14:35, wren ng thornton wrote: On 2/5/12 10:21 AM, Daniel Fischer wrote: Why not use one of the packages on hackage which offer faster prime generators? Mostly because I hadn't looked, having had the code already laying around. Yeah, that's fine, it was just I'll probably trade it in for your algorithm though. that made me wonder. Well, I would've looked around before making the change :) I'm not opposed to it, however another goal is to remain portable to other compilers, which means being H98/H2010 compliant. A noble goal. By which I really mean H98/H2010 plus all the things that were already 'standard' in the days of GHC 6.6 and Hugs. MPTCs and some of the related extensions for making type classes more flexible really need to be added to the standard, despite the valid political reasons for wanting to wait for the FD vs TF/AT issues to get resolved. NumberSieves uses BangPatterns, but that would be easily remedied if the author is willing; arithmoi looks quite nice, however it is GHC-only. The curse of striving for efficiency. Portability is on the to-do list (with low priority, however). It just climbed a place. Unless I'm doing something that by its nature requires GHC extensions, I've been doing my best to avoid them in published packages. Not that I have anything against them, but rather that I'd like to support JHC, UHC, and other alternatives (just as I used to support Hugs before it died). I think there's great value in compiler competition, so I'd like to foster it as much as I can. There're quite a number of efficiency hacks you can do while remaining in standard Haskell (and you can always hide the GHC-only parts with CPP). -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: combinatorics
On Fri, Feb 03, 2012 at 01:06:16AM -0500, wren ng thornton wrote: On 2/2/12 6:46 PM, Carter Schonwald wrote: On Thu, Feb 2, 2012 at 4:06 PM, Ivan Lazar Miljenovic wrote: On 3 February 2012 07:11, Brent Yorgey wrote: On Wed, Feb 01, 2012 at 01:53:03AM -0500, wren ng thornton wrote: [2] HaskellForMaths, gamma, statistics, erf, math-functions, combinat,... To this list I'd like to add 'species' and also the specialized 'multiset-comb' packages. The former doesn't build under recent GHCs but I plan to fix that (and continue extending the library) soon. Would people be interested in creating a mailing list for those interested in combinatorics+Haskell? I would. ditto I don't know how involved I'd be, but I'd join. It's just a side interest for me (more a curiosity than a hobby at this point), though I would definitely like to see things better organized and integrated since it seems like there are a bunch of folks with passing interest in the area, and it's someplace that Haskell could really shine. OK, I've emailed mail...@haskell.org requesting the creation of a combinator...@haskell.org mailing list (if anyone knows of a better way to go about this let me know). -Brent ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: combinatorics
On Wed, Feb 01, 2012 at 01:53:03AM -0500, wren ng thornton wrote: [2] HaskellForMaths, gamma, statistics, erf, math-functions, combinat,... To this list I'd like to add 'species' and also the specialized 'multiset-comb' packages. The former doesn't build under recent GHCs but I plan to fix that (and continue extending the library) soon. Would people be interested in creating a mailing list for those interested in combinatorics+Haskell? -Brent ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: combinatorics
On 3 February 2012 07:11, Brent Yorgey byor...@seas.upenn.edu wrote: On Wed, Feb 01, 2012 at 01:53:03AM -0500, wren ng thornton wrote: [2] HaskellForMaths, gamma, statistics, erf, math-functions, combinat,... To this list I'd like to add 'species' and also the specialized 'multiset-comb' packages. The former doesn't build under recent GHCs but I plan to fix that (and continue extending the library) soon. Would people be interested in creating a mailing list for those interested in combinatorics+Haskell? I would. -Brent ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: combinatorics
ditto On Thu, Feb 2, 2012 at 4:06 PM, Ivan Lazar Miljenovic ivan.miljeno...@gmail.com wrote: On 3 February 2012 07:11, Brent Yorgey byor...@seas.upenn.edu wrote: On Wed, Feb 01, 2012 at 01:53:03AM -0500, wren ng thornton wrote: [2] HaskellForMaths, gamma, statistics, erf, math-functions, combinat,... To this list I'd like to add 'species' and also the specialized 'multiset-comb' packages. The former doesn't build under recent GHCs but I plan to fix that (and continue extending the library) soon. Would people be interested in creating a mailing list for those interested in combinatorics+Haskell? I would. -Brent ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com IvanMiljenovic.wordpress.com ___ 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] ANN: combinatorics
On 2/2/12 6:46 PM, Carter Schonwald wrote: On Thu, Feb 2, 2012 at 4:06 PM, Ivan Lazar Miljenovic wrote: On 3 February 2012 07:11, Brent Yorgey wrote: On Wed, Feb 01, 2012 at 01:53:03AM -0500, wren ng thornton wrote: [2] HaskellForMaths, gamma, statistics, erf, math-functions, combinat,... To this list I'd like to add 'species' and also the specialized 'multiset-comb' packages. The former doesn't build under recent GHCs but I plan to fix that (and continue extending the library) soon. Would people be interested in creating a mailing list for those interested in combinatorics+Haskell? I would. ditto I don't know how involved I'd be, but I'd join. It's just a side interest for me (more a curiosity than a hobby at this point), though I would definitely like to see things better organized and integrated since it seems like there are a bunch of folks with passing interest in the area, and it's someplace that Haskell could really shine. -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: combinatorics
Hi,
On 29.01.2012, at 23:30, wren ng thornton wrote:
On 1/29/12 5:48 AM, Roman Cheplyaka wrote:
* wren ng thorntonw...@freegeek.org [2012-01-28 23:06:08-0500]
Why not to make it more pure? That is, return a lazy list of Ints (but
not a CAF), which user can throw away by the usual GC means?
The functions from the other modules that use primes would have to be
put in a Reader monad. That would make it a little bit more awkward to
use, but personally I'd prefer that over memory leaks.
I'd also prefer a more pure solution, but I don't think that the Reader monad
is the right tool here. I played around with that approach, but it requires
extremely invasive changes to client code, obfuscating what should be simple
mathematical formulae. And, it's too fragile, exposing the implementation in
a way that breaks client code should I change a non-prime-using algorithm to
a prime-using one, or vice versa. The fragility could be partially avoided by
providing both prime-using and non-prime-using algorithms, but then that
forces users to decide which one they want--- and if their only concern is
performance, then they'd have to go through the code-breaking refactoring
anyways, just to determine which is faster for their application.
One alternative I'm exploring is, rather than (only) making the primes not a
CAF, instead make the prime-using functions non-CAFs as well. That is,
provide a makePrimeUsingFunctions function which returns a record/tuple of
all the functions, sharing a stream of primes. This way, after allocating the
functions, they can be used purely just as in the current model; and when the
client wants the primes to be GCed, they can drop their references to the
allocated functions which use those primes (allocating new functions later,
if necessary).
A slight variation on that approach is to use implicit parameters to
parameterize your functions by the primes. Something allong the following lines:
{-# LANGUAGE ImplicitParams, Rank2Types #-}
data PrimeTable -- abstract
withPrimes :: ((?primes :: PrimeTable) = a) - a
withPrimes e = e
where
?primes = ...
factorial :: (?primes :: PrimeTable) = Integer - Integer
factorial = ...
example = withPrimes $ ... factorial n ….
This has the advantage that the user doesn't have to bring all the elemnts of
your tuple/record into scope.
And you can have two modules with an almost identical content, one uses the
implicit primes argument and the other uses a global CAF for its primes. A user
would only have to change his type signatures and strategically add/remove a
call to withPrimes when switching.
Cheers,
Jean
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: combinatorics
On 1/30/12 12:55 PM, Balazs Komuves wrote: -- combinatorics 0.1.0 The combinatorics package offers efficient *exact* computation of common combinatorial functions like the binomial coefficients and factorial. (For fast *approximations*, see the math-functions package instead.) Shameless self-promotion: The combinat package (which deliberately does not try to own the valuable namespace Math.Combinatorics) is a more extensive combinatorics library: http://hackage.haskell.org/package/combinat While the main focus is the generation of combinatorial objects themselves, counting functions and common number sequences like the above are also offered. I came across that package when looking around, but I only noticed the generation of combinatorial objects rather than the counting functions. As for namespacing, I'd be happy to move things further down to Math.Combinatorics.Exact (or similar)[1] it's just that Math.Combinatorics.* seemed not to be used by the numerous packages floating around this area with different purposes[2], and it seems the natural place for this sort of work. I think it'd be nice to get a bit more collaboration among folks doing this stuff so we can (a) clean up the namespace for this topic, and (b) reduce the amount of duplicated effort. [1] I'll probably end up doing that anyways, if I follow through with the proposed pure solution to the space-leak issue about storing the primes. [2] HaskellForMaths, gamma, statistics, erf, math-functions, combinat,... Even though the binomial and factorial definition in this package are the naive ones, a quick experiment imply that the differences start show themselves around 100,000 factorial, or choosing 50,000 elements out of 100,000, which is probably a rather specialized use case. In my experiments the threshold was a bit lower, but yes it's special purpose for people who need exact answers for big problems. The primes function in the combinat package is based on an old Cafe thread, and actually seems to be faster than the one in the combinatorics package. The primes generator was some old code I had laying around for one of those online programming challenges; fast enough for the task. I'll probably trade it in for your algorithm though. One of the things I'm disappointed by about the current implementation is the memory overhead for storing the primes. It'd be nice to use chunked arrays of unboxed integers in order to remove all the pointers; but my attempt at doing so had catastrophic performance... -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: combinatorics
On 1/30/12 3:54 PM, Roman Cheplyaka wrote: Makes sense; but doesn't making the monad abstract and putting all functions in the monad address the fragility issue? The primary issue with monads is that the syntax is extremely cumbersome for the expected use case. It'd be like paranoid C where, since order of evaluation is unspecified, all subexpressions are floated out into let-bindings. At that point (a) the verbosity is ugly, (b) the code is much harder to follow, and (c) it's all too easy to introduce errors where you use x instead of x' or the like. The semantic model of monads just isn't a good fit for this domain. There really aren't any side effects going on, there's no sequencing of actions, there's no little language that's being implemented,... I love me some monads and all, but they just don't fit here. -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: combinatorics
On 1/31/12 8:58 AM, Jean-Marie Gaillourdet wrote: A slight variation on that approach is to use implicit parameters to parameterize your functions by the primes. Something allong the following lines: That is another option. However, implicit parameters are GHC-only and seldom used even in GHC. The RTS-hacking I mentioned in the announcement would also be GHC-only, which is part of the reason I'd prefer to find a non-cumbersome way of dealing with the issue purely. As it stands the library is Haskell98 (with some trivial CPP to make the Haddocks pretty) and it'd be nice to stay that way. -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: combinatorics
-- combinatorics 0.1.0 The combinatorics package offers efficient *exact* computation of common combinatorial functions like the binomial coefficients and factorial. (For fast *approximations*, see the math-functions package instead.) Shameless self-promotion: The combinat package (which deliberately does not try to own the valuable namespace Math.Combinatorics) is a more extensive combinatorics library: http://hackage.haskell.org/package/combinat While the main focus is the generation of combinatorial objects themselves, counting functions and common number sequences like the above are also offered. Even though the binomial and factorial definition in this package are the naive ones, a quick experiment imply that the differences start show themselves around 100,000 factorial, or choosing 50,000 elements out of 100,000, which is probably a rather specialized use case. The primes function in the combinat package is based on an old Cafe thread, and actually seems to be faster than the one in the combinatorics package. In any case, I may switch to the faster algorithms in the future :) Balazs ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: combinatorics
* wren ng thornton w...@freegeek.org [2012-01-29 17:30:34-0500] On 1/29/12 5:48 AM, Roman Cheplyaka wrote: * wren ng thorntonw...@freegeek.org [2012-01-28 23:06:08-0500] * Math.Combinatorics.Primes: provides the prime numbers via Runciman's lazy wheel sieve algorithm. Provided here since efficient algorithms for combinatorial functions often require prime numbers. The current version memoizes the primes as an infinite list CAF, which could lead to memory leaks in long-running programs with irregular access to large primes. I'm looking into a GHC patch to allow resetting individual CAFs from within compiled programs so that you can explicitly decide when to un-memoize the primes. (In GHCi when you reload a module all the CAFs are reset. However, there's no way to access this feature from within compiled programs as yet.) Why not to make it more pure? That is, return a lazy list of Ints (but not a CAF), which user can throw away by the usual GC means? The functions from the other modules that use primes would have to be put in a Reader monad. That would make it a little bit more awkward to use, but personally I'd prefer that over memory leaks. I'd also prefer a more pure solution, but I don't think that the Reader monad is the right tool here. I played around with that approach, but it requires extremely invasive changes to client code, obfuscating what should be simple mathematical formulae. And, it's too fragile, exposing the implementation in a way that breaks client code should I change a non-prime-using algorithm to a prime-using one, or vice versa. The fragility could be partially avoided by providing both prime-using and non-prime-using algorithms, but then that forces users to decide which one they want--- and if their only concern is performance, then they'd have to go through the code-breaking refactoring anyways, just to determine which is faster for their application. Makes sense; but doesn't making the monad abstract and putting all functions in the monad address the fragility issue? -- Roman I. Cheplyaka :: http://ro-che.info/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: combinatorics
* wren ng thornton w...@freegeek.org [2012-01-28 23:06:08-0500] * Math.Combinatorics.Primes: provides the prime numbers via Runciman's lazy wheel sieve algorithm. Provided here since efficient algorithms for combinatorial functions often require prime numbers. The current version memoizes the primes as an infinite list CAF, which could lead to memory leaks in long-running programs with irregular access to large primes. I'm looking into a GHC patch to allow resetting individual CAFs from within compiled programs so that you can explicitly decide when to un-memoize the primes. (In GHCi when you reload a module all the CAFs are reset. However, there's no way to access this feature from within compiled programs as yet.) Why not to make it more pure? That is, return a lazy list of Ints (but not a CAF), which user can throw away by the usual GC means? The functions from the other modules that use primes would have to be put in a Reader monad. That would make it a little bit more awkward to use, but personally I'd prefer that over memory leaks. -- Roman I. Cheplyaka :: http://ro-che.info/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: combinatorics
On 1/29/12 5:48 AM, Roman Cheplyaka wrote: * wren ng thorntonw...@freegeek.org [2012-01-28 23:06:08-0500] * Math.Combinatorics.Primes: provides the prime numbers via Runciman's lazy wheel sieve algorithm. Provided here since efficient algorithms for combinatorial functions often require prime numbers. The current version memoizes the primes as an infinite list CAF, which could lead to memory leaks in long-running programs with irregular access to large primes. I'm looking into a GHC patch to allow resetting individual CAFs from within compiled programs so that you can explicitly decide when to un-memoize the primes. (In GHCi when you reload a module all the CAFs are reset. However, there's no way to access this feature from within compiled programs as yet.) Why not to make it more pure? That is, return a lazy list of Ints (but not a CAF), which user can throw away by the usual GC means? The functions from the other modules that use primes would have to be put in a Reader monad. That would make it a little bit more awkward to use, but personally I'd prefer that over memory leaks. I'd also prefer a more pure solution, but I don't think that the Reader monad is the right tool here. I played around with that approach, but it requires extremely invasive changes to client code, obfuscating what should be simple mathematical formulae. And, it's too fragile, exposing the implementation in a way that breaks client code should I change a non-prime-using algorithm to a prime-using one, or vice versa. The fragility could be partially avoided by providing both prime-using and non-prime-using algorithms, but then that forces users to decide which one they want--- and if their only concern is performance, then they'd have to go through the code-breaking refactoring anyways, just to determine which is faster for their application. One alternative I'm exploring is, rather than (only) making the primes not a CAF, instead make the prime-using functions non-CAFs as well. That is, provide a makePrimeUsingFunctions function which returns a record/tuple of all the functions, sharing a stream of primes. This way, after allocating the functions, they can be used purely just as in the current model; and when the client wants the primes to be GCed, they can drop their references to the allocated functions which use those primes (allocating new functions later, if necessary). I've used that pattern before for similar resource issues, and it worked nicely. But how well it works depends a lot on the structure of the program needing those resources. In particular it can lead to needing to use the Reader monad (or similar) in order to pass around the functions, even though the functions themselves can be used purely. Unfortunately I don't have any large combinatorial programs on hand to assess whether this would be problematic in practice or not. -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] ANN: combinatorics
-- combinatorics 0.1.0 The combinatorics package offers efficient *exact* computation of common combinatorial functions like the binomial coefficients and factorial. (For fast *approximations*, see the math-functions package instead.) -- Long Description * Math.Combinatorics.Primes: provides the prime numbers via Runciman's lazy wheel sieve algorithm. Provided here since efficient algorithms for combinatorial functions often require prime numbers. The current version memoizes the primes as an infinite list CAF, which could lead to memory leaks in long-running programs with irregular access to large primes. I'm looking into a GHC patch to allow resetting individual CAFs from within compiled programs so that you can explicitly decide when to un-memoize the primes. (In GHCi when you reload a module all the CAFs are reset. However, there's no way to access this feature from within compiled programs as yet.) * Math.Combinatorics.Binomial: offers a fast computation of the binomial coefficients based on the prime factorization of the result. As it turns out, it's easier to compute the prime factorization of the answer than it is to compute the answer directly! And you don't even need the factorial function to do so. Albeit, with a fast factorial function, the naive definition of binomial coefficients gives this algorithm a run for its money. * Math.Combinatorics.Factorial: offers a fast computation of factorial numbers. As Peter Luschny comments[1], the factorial function is often shown as a classic example of recursive functions, like addition of Peano numbers, however that naive way of computing factorials is extremely inefficient and does a disservice to those learning about recursion. The current implementation uses the split-recursive algorithm which is more than sufficient for casual use. I'm working on implementing the parallel prime-swing algorithm, which should be a bit faster still. [1] http://www.luschny.de/math/factorial/FastFactorialFunctions.htm -- Links Homepage: http://code.haskell.org/~wren/ Hackage: http://hackage.haskell.org/package/combinatorics Darcs: http://community.haskell.org/~wren/combinatorics Haddock (Darcs version): http://community.haskell.org/~wren/combinatorics/dist/doc/html/combinatorics -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
