[Haskell-cafe] ANN: combinatorics
wren ng thornton
wren at freegeek.org
Wed Feb 1 07:53:03 CET 2012
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
More information about the Haskell-Cafe
mailing list