[Haskell-cafe] ANN: combinatorics

[wren ng thornton]

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