exact-combinatorics 0.2.0.11 → 0.2.1.0
raw patch · 6 files changed
+103/−37 lines, 6 filesdep ~basePVP ok
version bump matches the API change (PVP)
Dependency ranges changed: base
API changes (from Hackage documentation)
Files
- CHANGELOG +22/−0
- README.md +3/−2
- exact-combinatorics.cabal +23/−12
- src/Math/Combinatorics/Exact/Binomial.hs +7/−3
- src/Math/Combinatorics/Exact/Factorial.hs +7/−7
- src/Math/Combinatorics/Exact/Primes.hs +41/−13
CHANGELOG view
@@ -1,3 +1,25 @@+0.2.1.0 (2026-09-28):+ - Removed the use of 'head' and 'tail' in order to silence warnings.+0.2.0.15 (2026-02-28):+ - Added `Tested-With: GHC == 9.12, 9.14` (didn't actually need to+ nudge the upper bound on 'base', because it's already lenient)+ - Silenced warnings on GHC 9.10 about importing 'Data.List'+ - TODO: still need to silence the following warnings:+ - 'Math.Combinatorics.Exact.Binomial.choose': GHC 9.14 deprecated+ multiple SPECIALIZE pragmas (and will remove them in 9.18)+ - 'Math.Combinatorics.Exact.Primes.primes': GHC 9.10 warns+ about using 'head' and 'tail'; so we need to rephrase the+ @seive@ function to avoid them while retaining the necessary+ laziness.+0.2.0.14 (2024-08-29):+ - Added `Tested-With: GHC == 9.8, 9.10` (didn't actually need to+ nudge the upper bound on 'base', because it's already lenient)+0.2.0.13 (2023-03-19):+ - Added `Tested-With: GHC == 9.6.1` (didn't actually need to+ nudge the upper bound on 'base', because it's already lenient)+0.2.0.12 (2022-08-28):+ - Added `Tested-With: GHC == 9.4.1` (didn't actually need to+ nudge the upper bound on 'base', because it's already lenient) 0.2.0.11 (2021-11-02): - Added `Tested-With: GHC == 9.2.1` (didn't actually need to nudge the upper bound on 'base', because it's already lenient)
README.md view
@@ -1,8 +1,9 @@ exact-combinatorics ===================+[](https://github.com/wrengr/exact-combinatorics/actions?query=workflow%3Aci+-event%3Apull_request) [](https://hackage.haskell.org/package/exact-combinatorics) -[](https://github.com/wrengr/exact-combinatorics/actions?query=workflow%3Aci)-[](http://packdeps.haskellers.com/specific?package=exact-combinatorics)+[](https://stackage.org/lts/package/exact-combinatorics)+[](https://stackage.org/nightly/package/exact-combinatorics) Efficient exact computation of combinatoric functions.
exact-combinatorics.cabal view
@@ -1,20 +1,25 @@+Cabal-Version: 2.2+-- Cabal >=2.2 is required for:+-- <https://cabal.readthedocs.io/en/latest/cabal-package.html#common-stanzas>+-- Since 2.1, the Cabal-Version must be the absolutely first thing+-- in the file, even before comments. Also, no longer uses ">=".+-- <https://github.com/haskell/cabal/issues/4899>+ ------------------------------------------------------------------- wren gayle romano <wren@cpan.org> ~ 2021.11.02+-- wren gayle romano <wren@cpan.org> ~ 2026-09-28 ---------------------------------------------------------------- --- Cabal >=1.10 is required by Hackage.-Cabal-Version: >= 1.10-Build-Type: Simple- Name: exact-combinatorics-Version: 0.2.0.11+Version: 0.2.1.0+Build-Type: Simple Stability: experimental Homepage: https://wrengr.org/software/hackage.html Bug-Reports: https://github.com/wrengr/exact-combinatorics/issues Author: wren gayle romano Maintainer: wren@cpan.org-Copyright: Copyright (c) 2011–2021 wren gayle romano-License: BSD3+Copyright: 2011–2026 wren romano+-- Cabal-2.2 requires us to say "BSD-3-Clause" not "BSD3"+License: BSD-3-Clause License-File: LICENSE Category: Statistics, Math@@ -34,7 +39,13 @@ GHC ==8.8.4, GHC ==8.10.3, GHC ==9.0.1,- GHC ==9.2.1+ GHC ==9.2.4,+ GHC ==9.4.8,+ GHC ==9.6.5,+ GHC ==9.8.2,+ GHC ==9.10.1,+ GHC ==9.12.1,+ GHC ==9.14.1 Source-Repository head Type: git@@ -47,12 +58,12 @@ Exposed-Modules: Math.Combinatorics.Exact.Primes , Math.Combinatorics.Exact.Factorial , Math.Combinatorics.Exact.Binomial- -- Data.IntList -- 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+ -- versions, so these are the lowest bounds we still verify.+ -- <https://gitlab.haskell.org/ghc/ghc/-/wikis/commentary/libraries/version-history>+ Build-Depends: base >= 4.9 && < 5 ---------------------------------------------------------------- ----------------------------------------------------------- fin.
src/Math/Combinatorics/Exact/Binomial.hs view
@@ -1,13 +1,14 @@ {-# OPTIONS_GHC -Wall -fwarn-tabs #-}+{-# LANGUAGE CPP #-} ------------------------------------------------------------------- 2021.10.17+-- 2026-02-28 -- | -- Module : Math.Combinatorics.Exact.Binomial--- Copyright : Copyright (c) 2011--2021 wren gayle romano+-- Copyright : Copyright (c) 2011--2026 wren gayle romano -- License : BSD -- Maintainer : wren@cpan.org -- Stability : experimental--- Portability : Haskell98+-- Portability : Haskell98 (+CPP) -- -- Binomial coefficients (<http://oeis.org/A007318>), aka the count -- of possible combinations. For negative inputs, all functions@@ -15,7 +16,9 @@ ---------------------------------------------------------------- module Math.Combinatorics.Exact.Binomial (choose) where +#if __GLASGOW_HASKELL__ < 910 import Data.List (foldl')+#endif import Math.Combinatorics.Exact.Primes (primes) {-@@ -82,6 +85,7 @@ -- choose :: (Integral a) => a -> a -> a -- The result type could be any (Num b) if desired.+-- TODO: GHC 9.14 deprecated multiple SPECIALIZE (and will remove in 9.18) {-# SPECIALIZE choose :: Integer -> Integer -> Integer, Int -> Int -> Int
src/Math/Combinatorics/Exact/Factorial.hs view
@@ -111,15 +111,15 @@ -- argument is the largest previously used term. partialProduct :: (Integral a) => Int -> a -> (a,a) partialProduct len j- | half == 0 = (,) <!> (j+2) <!> (j+2)- | len == 2 = (,) <!> ((j+2)*(j+4)) <!> (j+4)+ | half == 0 = mkPair (j+2) (j+2)+ | len == 2 = mkPair ((j+2)*(j+4)) (j+4) | otherwise =- let (qL, j' ) = partialProduct (len - half) j- (qR, j'') = partialProduct half j'- in (,) <!> (qL*qR) <!> j''+ let (qL , j' ) = partialProduct (len - half) j+ (qR , j'') = partialProduct half j'+ in mkPair (qL*qR) j'' where- half = len `quot` 2- (<!>) = ($!) -- fix associativity+ mkPair = \x y -> x `seq` y `seq` (x,y)+ half = len `quot` 2 {- floorLog2 :: (Integral a, Bits a) => a -> Int
src/Math/Combinatorics/Exact/Primes.hs view
@@ -1,14 +1,15 @@ {-# OPTIONS_GHC -Wall -fwarn-tabs- -fno-warn-incomplete-patterns -fno-warn-name-shadowing+ -fno-warn-incomplete-patterns+ -fno-warn-incomplete-uni-patterns #-} ------------------------------------------------------------------- 2021.10.17+-- 2026-09-28 -- | -- Module : Math.Combinatorics.Exact.Primes--- Copyright : Copyright (c) 2011--2021 wren gayle romano+-- Copyright : Copyright (c) 2011--2026 wren gayle romano -- License : BSD -- Maintainer : wren@cpan.org -- Stability : experimental@@ -18,12 +19,21 @@ ---------------------------------------------------------------- module Math.Combinatorics.Exact.Primes (primes) where +-- TODO: With the exception of the lists stored in a 'Wheel', all+-- the lists in this file are in fact infinite (modulo size issues+-- about 'Int'). Therefore it would be nice to implement (or find+-- on hackage) a datatype for infinite lists to avoid the cost of+-- unnecessary branches in case analysis, and to avoid the need for+-- `-fno-warn-incomplete-patterns` and `-fno-warn-incomplete-uni-patterns`.+-- In particular, we need the monad\/list-comprehension and @(++)@;+-- which alas seems to indicate that we need to use finite-lists+-- intermediately to constructing the infinite lists, unless we can+-- be especially clever. data Wheel = Wheel {-# UNPACK #-}!Int ![Int] - -- BUG: the CAF is nice for sharing, but what about when we want--- fusion and to avoid sharing? Using Data.IntList seems to only+-- fusion and to avoid sharing? Using "Data.IntList" seems to only -- increase the overhead. I guess things aren't being memoized/freed -- like they should... @@ -34,29 +44,47 @@ -- Journal of Functional Programming, 7(2). pp.219--225. -- ISSN 0956-7968 -- <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.7096>+-- TODO: get a new url for the paper, since citeseer is dead. -- primes :: [Int] primes = seive wheels primes primeSquares where+ primeSquares :: [Int] primeSquares = [p*p | p <- primes] + wheels :: [Wheel] wheels = Wheel 1 [1] : zipWith nextSize wheels primes where+ nextSize :: Wheel -> Int -> Wheel nextSize (Wheel s ns) p = Wheel (s*p) [n' | o <- [0,s..(p-1)*s] , n <- ns- , n' <- [n+o]+ , let 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]+ -- NOTE: I've switched to using lazy-patterns in lieu of 'head'+ -- and 'tail' in order to silence warnings on GHC >= 9.10.+ -- However, beware the syntax problems of combining as-patterns+ -- with lazy-patterns on GHC >= 9.0:+ -- <https://stackoverflow.com/q/67972231>+ -- <https://gitlab.haskell.org/ghc/ghc/-/wikis/migration/9.0#whitespace-sensitive----and->+ --+ -- Also note that `-fno-warn-incomplete-patterns` is no longer+ -- sufficient to silence the errors about incompete patterns here;+ -- we additionally need `-fno-warn-incomplete-uni-patterns`.+ -- Moreover, this isn't something we can resolve by simply expanding+ -- out the impossible cases, for some strange reason.++ seive :: [Wheel] -> [Int] -> [Int] -> [Int]+ -- NOTE: @pps@ and @qqs@ must be lazy; or else the circular program is _|_.+ seive (Wheel s ns : ws) pps@(~(p:ps)) qqs@(~(_:qs)) =+ [ n' | o <- s : [2*s,3*s..(p-1)*s] , n <- ns- , n' <- [n+o]- , s <= 2 || noFactorIn ps qs n' ]- ++ seive ws (tail ps) (tail qs)+ , let n' = n+o+ , s <= 2 || noFactorIn pps qqs n' ]+ ++ seive ws ps qs where- -- noFactorIn :: [Int] -> [Int] -> Int -> Bool+ noFactorIn :: [Int] -> [Int] -> Int -> Bool noFactorIn (p:ps) (q:qs) x = q > x || x `mod` p > 0 && noFactorIn ps qs x