exact-combinatorics 0.2.0.8 → 0.2.0.9
raw patch · 7 files changed
+116/−79 lines, 7 filesdep ~basenew-uploaderPVP ok
version bump matches the API change (PVP)
Dependency ranges changed: base
API changes (from Hackage documentation)
Files
- CHANGELOG +8/−0
- README +0/−34
- README.md +61/−0
- exact-combinatorics.cabal +30/−26
- src/Math/Combinatorics/Exact/Binomial.hs +1/−1
- src/Math/Combinatorics/Exact/Factorial.hs +13/−15
- src/Math/Combinatorics/Exact/Primes.hs +3/−3
CHANGELOG view
@@ -1,3 +1,11 @@+0.2.0.9 (2019-04-13):+ - Changed cabal to use Simple build type, to support cabal's new-build.+ - Removed the CPP hack for Haddock documentation, as part+ of switching to the Simple build type.+ - Using BangPatterns in lieu of the old seq-undefined-guard trick.+ - Added TravisCI integration+0.2.0.8 (2015-05-30):+ - Moved VERSION to CHANGELOG 0.2.0.4 (2012-09-26): - Math.Combinatorics.Exact.Binomial: added OEIS link 0.2.0 (2012-02-02):
− README
@@ -1,34 +0,0 @@-exact-combinatorics-===================--This is a simple package and should be easy to install. You should-be able to use one of the following standard methods to install it.-- -- With cabal-install and without the source:- $> cabal install exact-combinatorics- - -- With cabal-install and with the source already:- $> cd exact-combinatorics- $> cabal install- - -- Without cabal-install, but with the source already:- $> cd exact-combinatorics- $> runhaskell Setup.hs configure --user- $> runhaskell Setup.hs build- $> runhaskell Setup.hs test- $> runhaskell Setup.hs haddock --hyperlink-source- $> runhaskell Setup.hs copy- $> runhaskell Setup.hs register--The test step is optional and currently does nothing. The Haddock-step is also optional.---Portability-===========--An attempt has been made to keep this library as portable as possible.-It is Haskell98 except for the use of CPP, in order to get the-Haddock documentation to come out right.------------------------------------------------------------- fin.
+ README.md view
@@ -0,0 +1,61 @@+exact-combinatorics+===================+[](https://hackage.haskell.org/package/exact-combinatorics) +[](http://packdeps.haskellers.com/specific?package=exact-combinatorics)+[](https://travis-ci.org/wrengr/exact-combinatorics) ++Efficient exact computation of combinatoric functions.+++## Install++This is a simple package and should be easy to install via any of+the standared methods:++ -- With cabal-install and without the source:+ $> cabal new-install exact-combinatorics+ -- or:+ $> cabal install exact-combinatorics+ + -- With cabal-install and with the source already:+ $> cd exact-combinatorics+ $> cabal install+ + -- Without cabal-install, but with the source already:+ $> cd exact-combinatorics+ $> runhaskell Setup.hs configure --user+ $> runhaskell Setup.hs build+ $> runhaskell Setup.hs test+ $> runhaskell Setup.hs haddock --hyperlink-source+ $> runhaskell Setup.hs copy+ $> runhaskell Setup.hs register++The test step is optional and currently does nothing. The Haddock+step is also optional.+++## Portability++An attempt has been made to keep this library as portable as possible.+It is entirely Haskell98 with the exception of one use of BangPatterns.+BangPatterns are supported in GHC as far back as [version+6.6.1][ghc-bangpatterns], and are also supported by [JHC][jhc-bangpatterns]+and [UHC][uhc-bangpatterns]. As of 2010, they were [not supported+by Hugs][hugs-bangpatterns]; but alas Hugs is pretty much dead now.++[ghc-bangpatterns]: + https://downloads.haskell.org/~ghc/6.6.1/docs/html/users_guide/sec-bang-patterns.html+[jhc-bangpatterns]:+ http://repetae.net/computer/jhc/manual.html#code-options+[uhc-bangpatterns]:+ https://github.com/UU-ComputerScience/uhc-js/issues/1+[hugs-bangpatterns]: + https://mail.haskell.org/pipermail/haskell-cafe/2010-July/079946.html++## Links++* [Website](https://wrengr.org/)+* [Blog](http://winterkoninkje.dreamwidth.org/)+* [Twitter](https://twitter.com/wrengr)+* [Hackage](http://hackage.haskell.org/package/exact-combinatorics)+* [GitHub](https://github.com/wrengr/exact-combinatorics)
exact-combinatorics.cabal view
@@ -1,20 +1,21 @@ ------------------------------------------------------------------- wren gayle romano <wren@community.haskell.org> ~ 2015.05.30+-- wren gayle romano <wren@cpan.org> ~ 2019.04.13 ---------------------------------------------------------------- --- By and large Cabal >=1.2 is fine; but >= 1.6 gives tested-with:--- and source-repository:.-Cabal-Version: >= 1.6--- We need a custom build in order to define __HADDOCK__-Build-Type: Custom+-- By and large Cabal >=1.2 is fine; but+-- * >=1.6 gives tested-with: and source-repository:+-- * >=1.8 allows executables to build-depends: on the library+-- * >=1.9.2 allows Test-Suite+Cabal-Version: >= 1.9.2+Build-Type: Simple Name: exact-combinatorics-Version: 0.2.0.8+Version: 0.2.0.9 Stability: experimental-Homepage: http://code.haskell.org/~wren/+Homepage: https://wrengr.org/ Author: wren gayle romano-Maintainer: wren@community.haskell.org-Copyright: Copyright (c) 2011--2015 wren gayle romano+Maintainer: wren@cpan.org+Copyright: Copyright (c) 2011--2019 wren gayle romano License: BSD3 License-File: LICENSE @@ -22,21 +23,24 @@ Synopsis: Efficient exact computation of combinatoric functions. Description: Efficient exact computation of combinatoric functions. -Tested-With:- GHC ==6.12.1, GHC ==7.6.1, GHC ==7.8.0 Extra-source-files:- README, CHANGELOG-Source-Repository head- Type: darcs- Location: http://community.haskell.org/~wren/exact-combinatorics+ CHANGELOG, README.md ------------------------------------------------------------------Flag base4- Default: True- Description: base-4.0 emits "Prelude deprecated" messages in- order to get people to be explicit about which- version of base they use.+-- Cf., <https://travis-ci.org/wrengr/exact-combinatorics>+Tested-With:+ GHC ==7.4.1, GHC ==7.4.2,+ GHC ==7.6.1, GHC ==7.6.2, GHC ==7.6.3,+ GHC ==7.8.1, GHC ==7.8.2, GHC ==7.8.3, GHC ==7.8.4,+ GHC ==7.10.1, GHC ==7.10.2, GHC ==7.10.3,+ GHC ==8.0.1, GHC ==8.0.2,+ GHC ==8.2.1, GHC ==8.2.2,+ GHC ==8.4.1, GHC ==8.4.2, GHC ==8.4.3,+ GHC ==8.6.1, GHC ==8.6.2 +Source-Repository head+ Type: git+ Location: https://github.com/wrengr/exact-combinatorics.git+ ---------------------------------------------------------------- Library Hs-Source-Dirs: src@@ -45,10 +49,10 @@ , Math.Combinatorics.Exact.Binomial -- Data.IntList - if flag(base4)- Build-Depends: base >= 4 && < 5- else- Build-Depends: base < 4+ -- The lower bound is more restrictive than necessary.+ -- But then, we don't maintain any CI tests for older+ -- versions, so these are the lowest bounds we've verified.+ Build-Depends: base >= 4.5 && < 5 ---------------------------------------------------------------- ----------------------------------------------------------- fin.
src/Math/Combinatorics/Exact/Binomial.hs view
@@ -3,7 +3,7 @@ -- 2012.09.26 -- | -- Module : Math.Combinatorics.Exact.Binomial--- Copyright : Copyright (c) 2011--2015 wren gayle romano+-- Copyright : Copyright (c) 2011--2019 wren gayle romano -- License : BSD -- Maintainer : wren@community.haskell.org -- Stability : experimental
src/Math/Combinatorics/Exact/Factorial.hs view
@@ -1,14 +1,14 @@ {-# OPTIONS_GHC -Wall -fwarn-tabs #-}-{-# LANGUAGE CPP #-}+{-# LANGUAGE BangPatterns #-} ------------------------------------------------------------------- 2012.02.02+-- 2019.04.13 -- | -- Module : Math.Combinatorics.Exact.Factorial--- Copyright : Copyright (c) 2011--2015 wren gayle romano+-- Copyright : Copyright (c) 2011--2019 wren gayle romano -- License : BSD -- Maintainer : wren@community.haskell.org -- Stability : experimental--- Portability : Haskell98 + CPP+-- Portability : Haskell98 + BangPatterns -- -- The factorial numbers (<http://oeis.org/A000142>). For negative -- inputs, all functions return 0 (rather than throwing an exception@@ -24,10 +24,6 @@ ---------------------------------------------------------------- module Math.Combinatorics.Exact.Factorial (factorial) where --- N.B., we need a Custom cabal build-type for this to work.-#ifdef __HADDOCK__-import Data.Int (Int32, Int64)-#endif import Data.Bits {-@@ -93,8 +89,7 @@ -- r == (q1 ^ K) * (q2 ^ (K-1)) * ... * (qK ^ 1) -- s == 2^{n - popCount n} -- go :: Int -> Int -> Int -> Int -> a -> a -> a -> a- go k lo s hi j p r- | k `seq` lo `seq` s `seq` hi `seq` j `seq` p `seq` r `seq` False = undefined+ go !k !lo !s !hi !j !p !r | k >= 0 = -- TODO: why did old version use lo/=n ? let lo' = n `shiftR` k -- TODO: use shiftRL# hi' = (lo' - 1) .|. 1 -- if odd lo' then lo' else lo' - 1@@ -107,7 +102,8 @@ in go (k - 1) lo' (s + lo) hi' j' p' r' else go (k - 1) lo' (s + lo) hi' j p r --- -- fromIntegral s /= fromIntegral n - popCount (fromIntegral n) = error "factorial_splitRecursive: bug in the computation of n - popCount n"+ -- fromIntegral s /= fromIntegral n - popCount (fromIntegral n) =+ -- error "factorial_splitRecursive: bug in the computation of n - popCount n" | otherwise = r `shiftL` s -- | The product of odd @j@s between n/2^k and 2*n/2^k. @len@@@ -122,8 +118,7 @@ (qR, j'') = partialProduct half j' in (,) <!> (qL*qR) <!> j'' where- half = len `quot` 2-+ half = len `quot` 2 (<!>) = ($!) -- fix associativity {-@@ -157,7 +152,7 @@ -} highestBitPosition_Int :: Int -> Int-highestBitPosition_Int w = +highestBitPosition_Int w = if w < 1 `shiftL` 15 then if w < 1 `shiftL` 7 then if w < 1 `shiftL` 3@@ -231,7 +226,10 @@ $ primorial (n `div` 2 + 1) n * xmathProduct primeList 0 count - -- With hsc2hs we can use #def to define these as static C-style arrays, and then use base:Foreign.Marshall.Array to access them. Instead of using array:Data.Array.Unboxed; Or we could try the Addr# trick used in Warp+ -- With hsc2hs we can use #def to define these as static C-style+ -- arrays, and then use base:Foreign.Marshall.Array to access them.+ -- Instead of using array:Data.Array.Unboxed; Or we could try the+ -- Addr# trick used in Warp smallOddSwing :: UArray Int Int32 smallOddSwing = listArray (0,32) [ 1, 1, 1, 3, 3, 15, 5, 35, 35, 315, 63, 693, 231, 3003
src/Math/Combinatorics/Exact/Primes.hs view
@@ -8,7 +8,7 @@ -- 2012.02.02 -- | -- Module : Math.Combinatorics.Exact.Primes--- Copyright : Copyright (c) 2011--2015 wren gayle romano+-- Copyright : Copyright (c) 2011--2019 wren gayle romano -- License : BSD -- Maintainer : wren@community.haskell.org -- Stability : experimental@@ -39,7 +39,7 @@ primes = seive wheels primes primeSquares where primeSquares = [p*p | p <- primes]- + wheels = Wheel 1 [1] : zipWith nextSize wheels primes where nextSize (Wheel s ns) p =@@ -47,7 +47,7 @@ , n <- ns , n' <- [n+o] , n' `mod` p > 0 ]- + -- N.B., ps and qs must be lazy. Or else the circular program is _|_. seive (Wheel s ns : ws) ps qs = [ n' | o <- s : [2*s,3*s..(head ps-1)*s]