ersatz 0.4.1 → 0.4.2

raw patch · 10 files changed

+227/−98 lines, 10 filesdep +semigroupsdep ~basedep ~temporaryPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

Dependencies added: semigroups

Dependency ranges changed: base, temporary

API changes (from Hackage documentation)

Files

• .gitignore +19/−0
• .travis.yml +111/−68
• CHANGELOG.md +11/−0
• ersatz.cabal +5/−3
• examples/regexp-grid/RegexpGrid/Problem.hs +13/−3
• src/Ersatz/Internal/Formula.hs +21/−8
• src/Ersatz/Problem.hs +14/−10
• src/Ersatz/Relation/Data.hs +10/−5
• src/Ersatz/Relation/Op.hs +14/−0
• src/Ersatz/Relation/Prop.hs +9/−1

@@ -1,4 +1,5 @@ dist+dist-newstyle docs wiki TAGS@@ -15,3 +16,21 @@ *# *.prof *.hp+.stack-work/+cabal-dev+*.chi+*.chs.h+*.dyn_o+*.dyn_hi+.hpc+.hsenv+.cabal-sandbox/+cabal.sandbox.config+*.prof+*.aux+*.hp+*.eventlog+cabal.project.local+cabal.project.local~+.HTF/+.ghc.environment.*

@@ -1,95 +1,138 @@-# This file has been generated -- see https://github.com/hvr/multi-ghc-travis+# This Travis job script has been generated by a script via+#+#   runghc make_travis_yml_2.hs '-o' '.travis.yml' '--irc-channel=irc.freenode.org#haskell-lens' '--no-no-tests-no-bench' '--no-installed' 'cabal.project'+#+# For more information, see https://github.com/hvr/multi-ghc-travis+# language: c sudo: false +git:+  submodules: false  # whether to recursively clone submodules++notifications:+  irc:+    channels:+      - "irc.freenode.org#haskell-lens"+    skip_join: true+    template:+      - "\x0313ersatz\x03/\x0306%{branch}\x03 \x0314%{commit}\x03 %{build_url} %{message}"+ cache:   directories:-    - $HOME/.cabsnap     - $HOME/.cabal/packages+    - $HOME/.cabal/store  before_cache:   - rm -fv $HOME/.cabal/packages/hackage.haskell.org/build-reports.log-  - rm -fv $HOME/.cabal/packages/hackage.haskell.org/00-index.tar+  # remove files that are regenerated by 'cabal update'+  - rm -fv $HOME/.cabal/packages/hackage.haskell.org/00-index.*+  - rm -fv $HOME/.cabal/packages/hackage.haskell.org/*.json+  - rm -fv $HOME/.cabal/packages/hackage.haskell.org/01-index.cache+  - rm -fv $HOME/.cabal/packages/hackage.haskell.org/01-index.tar+  - rm -fv $HOME/.cabal/packages/hackage.haskell.org/01-index.tar.idx +  - rm -rfv $HOME/.cabal/packages/head.hackage++addons:+  apt:+    packages: &apt_packages+      - ghc-ppa-tools+      - minisat+      - alex-3.1.7+      - happy-1.19.5+ matrix:   include:-    - env: CABALVER=1.24 GHCVER=7.10.3 GHCOPTS="" JOPTS="-j2"-      compiler: ": #GHC 7.10.3"-      addons: {apt: {packages: [cabal-install-1.24,ghc-7.10.3,minisat],sources: [hvr-ghc]}}-    - env: CABALVER=1.24 GHCVER=8.0.2 GHCOPTS="" JOPTS="-j2"-      compiler: ": #GHC 8.0.2"-      addons: {apt: {packages: [cabal-install-1.24,ghc-8.0.2,minisat],sources: [hvr-ghc]}}-    - env: CABALVER=2.0 GHCVER=8.2.1 GHCOPTS="" JOPTS="-j2"-      compiler: ": #GHC 8.2.1"-      addons: {apt: {packages: [cabal-install-2.0,ghc-8.2.1,minisat],sources: [hvr-ghc]}}-    - env: CABALVER=head GHCVER=head GHCOPTS="" JOPTS="-j2"-      compiler: ": #GHC head"-      addons: {apt: {packages: [cabal-install-head,ghc-head,minisat],sources: [hvr-ghc]}}+    - compiler: "ghc-7.10.3"+    # env: TEST=--disable-tests BENCH=--disable-benchmarks+      addons: {apt: {packages: [*apt_packages,cabal-install-2.0,ghc-7.10.3], sources: [hvr-ghc]}}+    - compiler: "ghc-8.0.2"+    # env: TEST=--disable-tests BENCH=--disable-benchmarks+      addons: {apt: {packages: [*apt_packages,cabal-install-2.0,ghc-8.0.2], sources: [hvr-ghc]}}+    - compiler: "ghc-8.2.2"+    # env: TEST=--disable-tests BENCH=--disable-benchmarks+      addons: {apt: {packages: [*apt_packages,cabal-install-2.0,ghc-8.2.2], sources: [hvr-ghc]}}+    - compiler: "ghc-8.4.1"+      env: GHCHEAD=true+      addons: {apt: {packages: [*apt_packages,cabal-install-head,ghc-8.4.1], sources: [hvr-ghc]}}+    - compiler: "ghc-head"+      env: GHCHEAD=true+      addons: {apt: {packages: [*apt_packages,cabal-install-head,ghc-head], sources: [hvr-ghc]}}    allow_failures:-   - env: CABALVER=head GHCVER=head GHCOPTS="" JOPTS="-j2"+    - compiler: "ghc-8.4.1"+    - compiler: "ghc-head"  before_install:- - unset CC- - export HAPPYVER=1.19.5- - export ALEXVER=3.1.7- - export PATH=~/.cabal/bin:/opt/ghc/$GHCVER/bin:/opt/cabal/$CABALVER/bin:/opt/happy/$HAPPYVER/bin:/opt/alex/$ALEXVER/bin:$PATH+  - HC=${CC}+  - HCPKG=${HC/ghc/ghc-pkg}+  - unset CC+  - ROOTDIR=$(pwd)+  - mkdir -p $HOME/.local/bin+  - "PATH=/opt/ghc/bin:/opt/ghc-ppa-tools/bin:$HOME/local/bin:$PATH"+  - HCNUMVER=$(( $(${HC} --numeric-version|sed -E 's/([0-9]+)\.([0-9]+)\.([0-9]+).*/\1 * 10000 + \2 * 100 + \3/') ))+  - echo $HCNUMVER  install:- - cabal --version- - echo "$(ghc --version) [$(ghc --print-project-git-commit-id 2> /dev/null || echo '?')]"- - if [ -f $HOME/.cabal/packages/hackage.haskell.org/00-index.tar.gz ];-   then-     zcat $HOME/.cabal/packages/hackage.haskell.org/00-index.tar.gz >-          $HOME/.cabal/packages/hackage.haskell.org/00-index.tar;-   fi- - travis_retry cabal update- - "sed -i  's/^jobs:.*$/jobs: 2/' $HOME/.cabal/config"- - cabal install --only-dependencies --enable-tests --enable-benchmarks --dry -v > installplan.txt- - sed -i -e '1,/^Resolving /d' installplan.txt; cat installplan.txt+  - cabal --version+  - echo "$(${HC} --version) [$(${HC} --print-project-git-commit-id 2> /dev/null || echo '?')]"+  - BENCH=${BENCH---enable-benchmarks}+  - TEST=${TEST---enable-tests}+  - HADDOCK=${HADDOCK-true}+  - INSTALLED=${INSTALLED-true}+  - GHCHEAD=${GHCHEAD-false}+  - travis_retry cabal update -v+  - "sed -i.bak 's/^jobs:/-- jobs:/' ${HOME}/.cabal/config"+  - rm -fv cabal.project cabal.project.local+  # Overlay Hackage Package Index for GHC HEAD: https://github.com/hvr/head.hackage+  - |+    if $GHCHEAD; then+      sed -i.bak 's/-- allow-newer:.*/allow-newer: *:base, *:template-haskell, *:ghc, *:Cabal/' ${HOME}/.cabal/config -# check whether current requested install-plan matches cached package-db snapshot- - if diff -u installplan.txt $HOME/.cabsnap/installplan.txt;-   then-     echo "cabal build-cache HIT";-     rm -rfv .ghc;-     cp -a $HOME/.cabsnap/ghc $HOME/.ghc;-     cp -a $HOME/.cabsnap/lib $HOME/.cabsnap/share $HOME/.cabsnap/bin $HOME/.cabal/;-   else-     echo "cabal build-cache MISS";-     rm -rf $HOME/.cabsnap;-     mkdir -p $HOME/.ghc $HOME/.cabal/lib $HOME/.cabal/share $HOME/.cabal/bin;-     cabal install --only-dependencies --enable-tests --enable-benchmarks;-   fi+      echo 'repository head.hackage'                                                        >> ${HOME}/.cabal/config+      echo '   url: http://head.hackage.haskell.org/'                                       >> ${HOME}/.cabal/config+      echo '   secure: True'                                                                >> ${HOME}/.cabal/config+      echo '   root-keys: 07c59cb65787dedfaef5bd5f987ceb5f7e5ebf88b904bbd4c5cbdeb2ff71b740' >> ${HOME}/.cabal/config+      echo '              2e8555dde16ebd8df076f1a8ef13b8f14c66bad8eafefd7d9e37d0ed711821fb' >> ${HOME}/.cabal/config+      echo '              8f79fd2389ab2967354407ec852cbe73f2e8635793ac446d09461ffb99527f6e' >> ${HOME}/.cabal/config+      echo '   key-threshold: 3'                                                            >> ${HOME}/.cabal.config -# snapshot package-db on cache miss- - if [ ! -d $HOME/.cabsnap ];-   then-      echo "snapshotting package-db to build-cache";-      mkdir $HOME/.cabsnap;-      cp -a $HOME/.ghc $HOME/.cabsnap/ghc;-      cp -a $HOME/.cabal/lib $HOME/.cabal/share $HOME/.cabal/bin installplan.txt $HOME/.cabsnap/;-   fi+      cabal new-update head.hackage -v+    fi+  - grep -Ev -- '^\s*--' ${HOME}/.cabal/config | grep -Ev '^\s*$'+  - "printf 'packages: \".\"\\n' > cabal.project"+  - cat cabal.project+  - if [ -f "./configure.ac" ]; then+      (cd "." && autoreconf -i);+    fi+  - rm -f cabal.project.freeze+  - cabal new-build -w ${HC} ${TEST} ${BENCH} --project-file="cabal.project" --dep -j2 all+  - rm -rf "."/.ghc.environment.* "."/dist+  - DISTDIR=$(mktemp -d /tmp/dist-test.XXXX)  # Here starts the actual work to be performed for the package under test; # any command which exits with a non-zero exit code causes the build to fail. script:- - cabal configure --enable-tests --enable-benchmarks -v2  # -v2 provides useful information for debugging- - cabal build $JOPTS --ghc-options=$GHCOPTS # this builds all libraries and executables (including tests)- - cabal test- - cabal sdist   # tests that a source-distribution can be generated+  # test that source-distributions can be generated+  - (cd "." && cabal sdist)+  - mv "."/dist/ersatz-*.tar.gz ${DISTDIR}/+  - cd ${DISTDIR} || false+  - find . -maxdepth 1 -name '*.tar.gz' -exec tar -xvf '{}' \;+  - "printf 'packages: ersatz-*/*.cabal\\n' > cabal.project"+  - cat cabal.project -# Check that the resulting source distribution can be built & installed.-# If there are no other `.tar.gz` files in `dist`, this can be even simpler:-# `cabal install --force-reinstalls dist/*-*.tar.gz`- - SRC_TGZ=$(cabal info . | awk '{print $2;exit}').tar.gz &&-   (cd dist && cabal install $JOPTS --ghc-options=$GHCOPTS --force-reinstalls "$SRC_TGZ") -notifications:-  irc:-    channels:-      - "irc.freenode.org#haskell-lens"-    skip_join: true-    template:-      - "\x0313ersatz\x0f/\x0306%{branch}\x0f \x0314%{commit}\x0f %{message} \x0302\x1f%{build_url}\x0f"+  # build & run tests, build benchmarks+  - cabal new-build -w ${HC} ${TEST} ${BENCH} all+  - if [ "x$TEST" = "x--enable-tests" ]; then cabal new-test -w ${HC} ${TEST} ${BENCH} all; fi++  # cabal check+  - (cd ersatz-* && cabal check)++  # haddock+  - rm -rf ./dist-newstyle+  - if $HADDOCK; then cabal new-haddock -w ${HC} ${TEST} ${BENCH} all; else echo "Skipping haddock generation";fi++# REGENDATA ["-o",".travis.yml","--irc-channel=irc.freenode.org#haskell-lens","--no-no-tests-no-bench","--no-installed","cabal.project"] # EOF

@@ -1,3 +1,14 @@+0.4.2+-----+* Add `Semigroup` instances for `Clause` and `Formula`.+* Generalize `regular`, `regular_in_degree`, `regular_out_degree`,+  `max_in_degree`, `min_in_degree`, `max_out_degree`, and `min_out_degree` to+  work over heterogeneous relations.+* Add `buildFrom` to `Ersatz.Relation.Data`.+* Add `difference`, `reflexive_closure`, and `symmetric_closure` to+  `Ersatz.Relation.Op`.+* Add `anti_symmetric` and `total` to `Ersatz.Relation.Prop`.+ 0.4.1 ----- * Add a library dependency on the `doctests` test suite

@@ -1,5 +1,5 @@ name:           ersatz-version:        0.4.1+version:        0.4.2 license:        BSD3 license-file:   LICENSE author:         Edward A. Kmett, Eric Mertens, Johan Kiviniemi@@ -75,7 +75,7 @@  build-type:     Custom cabal-version:  >= 1.10-tested-with:    GHC == 7.10.3, GHC == 8.0.2, GHC == 8.2.1+tested-with:    GHC == 7.10.3, GHC == 8.0.2, GHC == 8.2.2, GHC == 8.4.1 extra-source-files:   .ghci   .gitignore@@ -183,6 +183,7 @@     lens                 >= 3.8      && < 5,     mtl                  >= 1.1      && < 2.3,     process              >= 1.1      && < 1.7,+    semigroups           >= 0.16     && < 1,     temporary            >= 1.1      && < 1.3,     transformers         >= 0.3      && < 0.6,     unordered-containers == 0.2.*,@@ -227,7 +228,8 @@       ersatz,       lens,       mtl,-      parsec >= 3.1 && < 3.2+      parsec >= 3.1 && < 3.2,+      semigroups     if impl(ghc >= 7.4 && < 7.6)       build-depends: ghc-prim   else

@@ -1,3 +1,4 @@+{-# LANGUAGE CPP #-} {-# LANGUAGE TupleSections #-} {-# LANGUAGE TemplateHaskell #-} @@ -9,11 +10,14 @@  import Control.Applicative import Control.Monad.Reader-import Control.Monad.RWS.Strict+import Control.Monad.RWS.Strict hiding ((<>)) import Control.Lens import Data.Foldable (asum) import Data.Map (Map) import qualified Data.Map as Map+#if !(MIN_VERSION_base(4,11,0))+import Data.Semigroup (Semigroup(..))+#endif import Data.Sequence (Seq) import qualified Data.Sequence as Seq import Ersatz@@ -41,12 +45,18 @@ makeLenses ''ReBitState makeLenses ''ReBitResult +instance Semigroup ReBitResult where+  ReBitResult fieldsA bitA <> ReBitResult fieldsB bitB =+    ReBitResult (fieldsA <> fieldsB) (bitA && bitB)+  {-# INLINE (<>) #-}+ instance Monoid ReBitResult where   mempty = ReBitResult mempty true   {-# INLINE mempty #-}-  ReBitResult fieldsA bitA `mappend` ReBitResult fieldsB bitB =-    ReBitResult (fieldsA <> fieldsB) (bitA && bitB)+#if !(MIN_VERSION_base(4,11,0))+  mappend = (<>)   {-# INLINE mappend #-}+#endif  problem :: (Applicative m, MonadState s m, HasSAT s) => m (Map Pos Field) problem = do

@@ -28,15 +28,9 @@   , formulaFAS, formulaFAC   ) where -#if __GLASGOW_HASKELL__ < 710-import Control.Applicative-#endif import Data.IntSet (IntSet) import qualified Data.IntSet as IntSet import qualified Data.List as List (intersperse)-#if __GLASGOW_HASKELL__ < 710-import Data.Monoid-#endif import Data.Typeable import Ersatz.Internal.Literal @@ -44,6 +38,15 @@ import qualified Data.Sequence as Seq import Data.Foldable (toList) +#if !(MIN_VERSION_base(4,8,0))+import Control.Applicative+import Data.Monoid (Monoid(..))+#endif++#if !(MIN_VERSION_base(4,11,0))+import Data.Semigroup (Semigroup(..))+#endif+ ------------------------------------------------------------------------------ -- Clauses ------------------------------------------------------------------------------@@ -57,9 +60,14 @@ clauseLiterals :: Clause -> [Literal] clauseLiterals (Clause is) = Literal <$> IntSet.toList is +instance Semigroup Clause where+  Clause x <> Clause y = Clause (x <> y)+ instance Monoid Clause where   mempty = Clause mempty-  mappend (Clause x) (Clause y) = Clause (mappend x y)+#if !(MIN_VERSION_base(4,11,0))+  mappend = (<>)+#endif  fromLiteral :: Literal -> Clause fromLiteral l = Clause { clauseSet = IntSet.singleton $ literalId l }@@ -72,9 +80,14 @@ newtype Formula = Formula { formulaSet :: Seq Clause }   deriving (Eq, Ord, Typeable) +instance Semigroup Formula where+  Formula x <> Formula y = Formula (x <> y)+ instance Monoid Formula where   mempty = Formula mempty-  mappend (Formula x) (Formula y) = Formula (mappend x y)+#if !(MIN_VERSION_base(4,11,0))+  mappend = (<>)+#endif  instance Show Formula where   showsPrec p = showParen (p > 2) . foldr (.) id

@@ -45,28 +45,18 @@   ) where  import Data.ByteString.Builder-#if __GLASGOW_HASKELL__ < 710-import Control.Applicative-#endif import Control.Lens import Control.Monad-#if !(MIN_VERSION_lens(4,0,0))-import Control.Monad.Identity-#endif import Control.Monad.State import Data.ByteString (ByteString) import qualified Data.ByteString.Lazy as Lazy import Data.Default-#if __GLASGOW_HASKELL__ < 710-import Data.Foldable (foldMap)-#endif import Data.HashMap.Lazy (HashMap) import qualified Data.HashMap.Lazy as HashMap import Data.Int import Data.IntSet (IntSet) import qualified Data.IntSet as IntSet import qualified Data.List as List-import Data.Monoid import Data.Typeable import Ersatz.Internal.Formula import Ersatz.Internal.Literal@@ -74,6 +64,20 @@ import System.IO.Unsafe import Data.Sequence (Seq) import qualified Data.Sequence as Seq++#if !(MIN_VERSION_base(4,8,0))+import Control.Applicative+import Data.Foldable (foldMap)+import Data.Monoid (Monoid(..))+#endif++#if !(MIN_VERSION_base(4,11,0))+import Data.Semigroup (Semigroup(..))+#endif++#if !(MIN_VERSION_lens(4,0,0))+import Control.Monad.Identity+#endif  ------------------------------------------------------------------------------ -- SAT Problems

@@ -3,6 +3,7 @@ module Ersatz.Relation.Data ( Relation , relation, symmetric_relation , build+, buildFrom , identity , bounds, (!), indices, assocs, elems , table@@ -47,16 +48,20 @@                    ++ [ ((q,p), x) | p /= q ]     return $ build bnd $ concat pairs -identity :: ( Ix a )-         => ((a,a),(a,a)) ->  Relation a a-identity bnd = build bnd $ flip map (A.range bnd) $ \ (i,j) ->-        ((i,j), if i == j then true else false )- build :: ( Ix a, Ix b )       => ((a,b),(a,b))       -> [ ((a,b), Bit ) ]       -> Relation a b build bnd pairs = Relation $ A.array bnd pairs++buildFrom :: (Ix a, Ix b)+          => (a -> b -> Bit) -> ((a,b),(a,b)) -> Relation a b+buildFrom p bnd = build bnd $ flip map (A.range bnd) $ \ (i,j) ->+    ((i,j), p i j)++identity :: (Ix a)+         => ((a,a),(a,a)) -> Relation a a+identity = buildFrom (\ i j -> bool $ i == j)   bounds :: (Ix a, Ix b) => Relation a b -> ((a,b),(a,b))

@@ -5,8 +5,11 @@ ( mirror , union , complement+, difference , product, power , intersection+, reflexive_closure+, symmetric_closure )  where@@ -27,6 +30,10 @@ complement r =     build (bounds r) $ do i <- indices r ; return ( i, not $ r!i ) +difference :: ( Ix a , Ix b )+        => Relation a b -> Relation a b ->  Relation a b+difference r s =+    intersection r $ complement s  union :: ( Ix a , Ix b )         => Relation a b -> Relation a b ->  Relation a b@@ -66,3 +73,10 @@         i <- indices r         return (i, and [ r!i, s!i ] ) +reflexive_closure :: Ix a => Relation a a -> Relation a a+reflexive_closure t =+    union t $ identity $ bounds t++symmetric_closure :: Ix a => Relation a a -> Relation a a+symmetric_closure r =+    union r $ mirror r

@@ -3,6 +3,7 @@  ( implies , symmetric+, anti_symmetric , transitive , irreflexive , reflexive@@ -15,6 +16,7 @@ , min_out_degree , empty , complete+, total , disjoint , equals )@@ -44,6 +46,9 @@ complete :: (Ix a, Ix b) => Relation a b -> Bit complete r = empty $ complement r +total :: ( Ix a) => Relation a a -> Bit+total r = complete $ symmetric_closure r+ disjoint :: (Ix a, Ix b) => Relation a b -> Relation a b -> Bit disjoint r s = empty $ intersection r s @@ -53,6 +58,9 @@ symmetric :: ( Ix a) => Relation a a -> Bit symmetric r = implies r ( mirror r ) +anti_symmetric :: ( Ix a) => Relation a a -> Bit+anti_symmetric r = implies (intersection r (mirror r)) (identity (bounds r))+ irreflexive :: ( Ix a ) => Relation a a -> Bit irreflexive r = and $ do     let ((a,_),(c,_)) = bounds r@@ -65,7 +73,7 @@     x <- range (a,c)     return $ r ! (x,x) -regular, regular_in_degree, regular_out_degree, max_in_degree, min_in_degree, max_out_degree, min_out_degree :: ( Ix a ) => Int -> Relation a a -> Bit+regular, regular_in_degree, regular_out_degree, max_in_degree, min_in_degree, max_out_degree, min_out_degree :: (Ix a, Ix b) => Int -> Relation a b -> Bit  regular deg r = and [ regular_in_degree deg r, regular_out_degree deg r ]