species 0.3.1 → 0.3.2

raw patch · 14 files changed

+215/−199 lines, 14 filesPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

API changes (from Hackage documentation)

Files

• CHANGES +5/−0
• Math/Combinatorics/Species.hs +5/−4
• Math/Combinatorics/Species/AST.hs +1/−1
• Math/Combinatorics/Species/Class.hs +1/−1
• Math/Combinatorics/Species/CycleIndex.hs +2/−2
• Math/Combinatorics/Species/Enumerate.hs +11/−11
• Math/Combinatorics/Species/Labeled.hs +95/−0
• Math/Combinatorics/Species/Labelled.hs +0/−89
• Math/Combinatorics/Species/Structures.hs +2/−2
• Math/Combinatorics/Species/TH.hs +1/−1
• Math/Combinatorics/Species/Types.hs +2/−2
• Math/Combinatorics/Species/Unlabeled.hs +86/−0
• Math/Combinatorics/Species/Unlabelled.hs +0/−82
• species.cabal +4/−4

@@ -13,3 +13,8 @@ 0.3.1      18 July 2010   * rename 'unerase' to the more descriptive 'annotate'   * export more stuff from Math.Combinatorics.Species and add some docs++0.3.2      31 July 2010+  * rename M.C.S.Unlabelled to M.C.S.Unlabeled and M.C.S.Labelled to M.C.S.Labeled;+    add 'labeled' and 'unlabeled' as aliases for 'labelled' and 'unlabelled'+  * export Interp from M.C.Species

@@ -61,8 +61,8 @@        -- * Counting species structures       -- $counting-    , labelled-    , unlabelled+    , labeled, labelled+    , unlabeled, unlabelled        -- * Enumerating species structures       -- $enum@@ -102,6 +102,7 @@       -- $rec      , ASTFunctor(..)+    , Interp     , newtonRaphsonRec     , newtonRaphson @@ -112,8 +113,8 @@     ) where  import Math.Combinatorics.Species.Class-import Math.Combinatorics.Species.Labelled-import Math.Combinatorics.Species.Unlabelled+import Math.Combinatorics.Species.Labeled+import Math.Combinatorics.Species.Unlabeled import Math.Combinatorics.Species.Structures import Math.Combinatorics.Species.Enumerate import Math.Combinatorics.Species.AST

@@ -159,7 +159,7 @@     -- Note, the above interval for functor composition is obviously     -- overly conservative.  To do this right we'd have to compute the     -- generating function for g --- and actually it would depend on-    -- whether we were doing labelled or unlabelled enumeration, which+    -- whether we were doing labeled or unlabeled enumeration, which     -- we don't know at this point. interval (TDer f)             = decrI (getI f) interval (TOfSize f p)        = fromI $ smallestIn (getI f) p

@@ -71,7 +71,7 @@ --   differentiation, i.e. adjoining a distinguished element). -- --   Minimal complete definition: 'singleton', 'set', 'cycle', 'o',---   'cartesian', 'fcomp', 'ofSize'.+--   '><', '@@', 'ofSize'. -- --   Note that the 'o' operation can be used infix to suggest common --   notation for composition, and also to be read as an abbreviation

@@ -31,7 +31,7 @@  import Math.Combinatorics.Species.Types import Math.Combinatorics.Species.Class-import Math.Combinatorics.Species.Labelled+import Math.Combinatorics.Species.Labeled  import Math.Combinatorics.Species.NewtonRaphson @@ -228,7 +228,7 @@   where for     = flip map          -- Convert g to an EGF for later reference.-        gEGF    = labelled $ zToEGF g+        gEGF    = labeled $ zToEGF g          -- Given a cycle type @nn@ (corresponding to a permutation         -- sigma on @n@ elements), compute the cycle type of G[sigma],

@@ -16,7 +16,7 @@ -- Stability   :  experimental -- -- Enumeration (i.e. exhaustive generation of structures) of both--- labelled and unlabelled species.+-- labeled and unlabeled species. -- ----------------------------------------------------------------------------- @@ -72,12 +72,12 @@ --   existentially quantified; see 'enumerateE'. -- --   Generating structures over base elements from a /multiset/---   unifies labelled and unlabelled generation into one framework.---   To enumerate labelled structures, use a multiset where each---   element occurs exactly once; to enumerate unlabelled structures,+--   unifies labeled and unlabeled generation into one framework.+--   To enumerate labeled structures, use a multiset where each+--   element occurs exactly once; to enumerate unlabeled structures, --   use a multiset with the desired number of copies of a single---   element.  To do labelled generation we could get away without the---   generality of multisets, but to do unlabelled generation we need+--   element.  To do labeled generation we could get away without the+--   generality of multisets, but to do unlabeled generation we need --   the full generality anyway. -- --   'enumerate'' does all the actual work, but is not meant to be used@@ -290,7 +290,7 @@ enumerate :: (Enumerable f, Typeable a, Eq a) => SpeciesAST -> [a] -> [f a] enumerate s = enumerateM s . MS.fromListEq --- | Labelled enumeration: given a species expression and a list of+-- | Labeled enumeration: given a species expression and a list of --   labels (which are assumed to be distinct), compute the list of --   all structures built from the given labels.  If the type given --   for the enumeration does not match the species expression (via an@@ -311,9 +311,9 @@ enumerateL :: (Enumerable f, Typeable a) =>  SpeciesAST -> [a] -> [f a] enumerateL s = enumerateM s . MS.fromDistinctList --- | Unlabelled enumeration: given a species expression and an integer+-- | Unlabeled enumeration: given a species expression and an integer --   indicating the number of labels to use, compute the list of all---   unlabelled structures of the given size.  If the type given for+--   unlabeled structures of the given size.  If the type given for --   the enumeration does not match the species expression, call --   'error' with an error message explaining the mismatch. --@@ -336,7 +336,7 @@ enumerateM :: (Enumerable f, Typeable a) => SpeciesAST -> Multiset a -> [f a] enumerateM s m = map unsafeExtractStructure $ enumerateE (annotate s) m --- | Lazily enumerate all unlabelled structures.+-- | Lazily enumerate all unlabeled structures. -- --   For example: --@@ -347,7 +347,7 @@ enumerateAllU :: Enumerable f => SpeciesAST -> [f ()] enumerateAllU s = concatMap (enumerateU s) [0..] --- | Lazily enumerate all labelled structures, using [1..] as the+-- | Lazily enumerate all labeled structures, using [1..] as the --   labels. -- --   For example:

@@ -0,0 +1,95 @@+{-# LANGUAGE NoImplicitPrelude+           , GeneralizedNewtypeDeriving+           , PatternGuards+  #-}++-----------------------------------------------------------------------------+-- |+-- Module      :  Math.Combinatorics.Species.Labeled+-- Copyright   :  (c) Brent Yorgey 2010+-- License     :  BSD-style (see LICENSE)+-- Maintainer  :  byorgey@cis.upenn.edu+-- Stability   :  experimental+--+-- An interpretation of species as exponential generating functions,+-- which count labeled structures.+--+-----------------------------------------------------------------------------++module Math.Combinatorics.Species.Labeled+    ( labeled+    , labelled+    ) where++-- A previous version of this module used an EGF library which+-- explicitly computed with EGFs.  However, it turned out to be much+-- slower than just computing explicitly with normal power series and+-- zipping/unzipping with factorial denominators as necessary, which+-- is the current approach.++import Math.Combinatorics.Species.Types+import Math.Combinatorics.Species.Class++import Math.Combinatorics.Species.AST+import Math.Combinatorics.Species.AST.Instances+import Math.Combinatorics.Species.NewtonRaphson++import qualified MathObj.PowerSeries as PS+import qualified MathObj.FactoredRational as FQ++import NumericPrelude+import PreludeBase hiding (cycle)++facts :: [Integer]+facts = 1 : zipWith (*) [1..] facts++instance Species EGF where+  singleton  = egfFromCoeffs [0,1]+  set        = egfFromCoeffs (map (1%) facts)+  cycle      = egfFromCoeffs (0 : map (1%) [1..])+  o          = liftEGF2 PS.compose+  (><)       = liftEGF2 . PS.lift2 $ \xs ys ->+                 zipWith3 mult xs ys (map fromIntegral facts)+                   where mult x y z = x * y * z+  (@@)       = liftEGF2 . PS.lift2 $ \fs gs ->+                 map (\(n,gn) -> let gn' = numerator $ gn+                                 in  (fs `safeIndex` gn') *+                                     toRational (FQ.factorial gn' / FQ.factorial n))+                     (zip [0..] $ zipWith (*) (map fromIntegral facts) gs)+    where safeIndex [] _     = 0+          safeIndex (x:_)  0 = x+          safeIndex (_:xs) n = safeIndex xs (n-1)++  ofSize s p        = (liftEGF . PS.lift1 $ filterCoeffs p) s+  ofSizeExactly s n = (liftEGF . PS.lift1 $ selectIndex n) s++  -- XXX Think about this more carefully -- is there a way to make this actually+  --   return a lazy, infinite list?+  rec f = case newtonRaphsonRec f 100 of+            Nothing -> error $ "Unable to express " ++ show f ++ " in the form T = TX*R(T)."+            Just ls -> ls++-- | Extract the coefficients of an exponential generating function as+--   a list of 'Integer's.  Since 'EGF' is an instance of 'Species', the+--   idea is that 'labeled' can be applied directly to an expression+--   of the species DSL.  In particular, @'labeled' s '!!'  n@ is the+--   number of labeled @s@-structures on an underlying set of size @n@+--   (note that @'labeled' s@ is guaranteed to be an infinite list).+--   For example:+--+-- > > take 10 $ labeled octopi+-- > [0,1,3,14,90,744,7560,91440,1285200,20603520]+--+--   gives the number of labeled octopi on 0, 1, 2, 3, ... 9 labels.++labeled :: EGF -> [Integer]+labeled (EGF f) = (++repeat 0)+                . map numerator+                . zipWith (*) (map fromInteger facts)+                $ PS.coeffs f++-- | A synonym for 'labeled', since both spellings are acceptable and+--   it's annoying to have to remember which is correct.+labelled :: EGF -> [Integer]+labelled = labeled+

@@ -1,89 +0,0 @@-{-# LANGUAGE NoImplicitPrelude-           , GeneralizedNewtypeDeriving-           , PatternGuards-  #-}---------------------------------------------------------------------------------- |--- Module      :  Math.Combinatorics.Species.Labelled--- Copyright   :  (c) Brent Yorgey 2010--- License     :  BSD-style (see LICENSE)--- Maintainer  :  byorgey@cis.upenn.edu--- Stability   :  experimental------ An interpretation of species as exponential generating functions,--- which count labelled structures.-----------------------------------------------------------------------------------module Math.Combinatorics.Species.Labelled-    ( labelled-    ) where---- A previous version of this module used an EGF library which--- explicitly computed with EGFs.  However, it turned out to be much--- slower than just computing explicitly with normal power series and--- zipping/unzipping with factorial denominators as necessary, which--- is the current approach.--import Math.Combinatorics.Species.Types-import Math.Combinatorics.Species.Class--import Math.Combinatorics.Species.AST-import Math.Combinatorics.Species.AST.Instances-import Math.Combinatorics.Species.NewtonRaphson--import qualified MathObj.PowerSeries as PS-import qualified MathObj.FactoredRational as FQ--import NumericPrelude-import PreludeBase hiding (cycle)--facts :: [Integer]-facts = 1 : zipWith (*) [1..] facts--instance Species EGF where-  singleton  = egfFromCoeffs [0,1]-  set        = egfFromCoeffs (map (1%) facts)-  cycle      = egfFromCoeffs (0 : map (1%) [1..])-  o          = liftEGF2 PS.compose-  (><)       = liftEGF2 . PS.lift2 $ \xs ys ->-                 zipWith3 mult xs ys (map fromIntegral facts)-                   where mult x y z = x * y * z-  (@@)       = liftEGF2 . PS.lift2 $ \fs gs ->-                 map (\(n,gn) -> let gn' = numerator $ gn-                                 in  (fs `safeIndex` gn') *-                                     toRational (FQ.factorial gn' / FQ.factorial n))-                     (zip [0..] $ zipWith (*) (map fromIntegral facts) gs)-    where safeIndex [] _     = 0-          safeIndex (x:_)  0 = x-          safeIndex (_:xs) n = safeIndex xs (n-1)--  ofSize s p        = (liftEGF . PS.lift1 $ filterCoeffs p) s-  ofSizeExactly s n = (liftEGF . PS.lift1 $ selectIndex n) s--  -- XXX Think about this more carefully -- is there a way to make this actually-  --   return a lazy, infinite list?-  rec f = case newtonRaphsonRec f 100 of-            Nothing -> error $ "Unable to express " ++ show f ++ " in the form T = TX*R(T)."-            Just ls -> ls---- | Extract the coefficients of an exponential generating function as---   a list of 'Integer's.  Since 'EGF' is an instance of 'Species', the---   idea is that 'labelled' can be applied directly to an expression---   of the species DSL.  In particular, @'labelled' s '!!'  n@ is the---   number of labelled @s@-structures on an underlying set of size @n@---   (note that @'labelled' s@ is guaranteed to be an infinite list).---   For example:------ > > take 10 $ labelled octopi--- > [0,1,3,14,90,744,7560,91440,1285200,20603520]------   gives the number of labelled octopi on 0, 1, 2, 3, ... 9 labels.--labelled :: EGF -> [Integer]-labelled (EGF f) = (++repeat 0)-                 . map numerator-                 . zipWith (*) (map fromInteger facts)-                 $ PS.coeffs f-

@@ -58,9 +58,9 @@ data Void a   deriving Typeable instance Functor Void where-  fmap _ _ = undefined+  fmap = undefined instance Show (Void a) where-  show _   = undefined+  show = undefined  -- | The (constantly) unit functor. data Unit a = Unit

@@ -415,7 +415,7 @@ --   to any function expecting a species.  For example, to count your --   data type's distinct shapes, you can do -----   > take 10 . unlabelled $ myType+--   > take 10 . unlabeled $ myType -- deriveDefaultSpecies :: Name -> Q [Dec] deriveDefaultSpecies nm = do

@@ -68,7 +68,7 @@ --  Series types  ------------------------------------------ ------------------------------------------------------------ --- | Exponential generating functions, for counting labelled species.+-- | Exponential generating functions, for counting labeled species. newtype EGF = EGF { unEGF :: PS.T Rational }   deriving (Additive.C, Differential.C, Ring.C, Show) @@ -82,7 +82,7 @@          -> EGF -> EGF -> EGF liftEGF2 f (EGF x) (EGF y) = EGF (f x y) --- | Ordinary generating functions, for counting unlabelled species.+-- | Ordinary generating functions, for counting unlabeled species. newtype GF = GF (PS.T Integer)   deriving (Additive.C, Ring.C, Show) 

@@ -0,0 +1,86 @@+-----------------------------------------------------------------------------+-- |+-- Module      :  Math.Combinatorics.Species.CycleIndex+-- Copyright   :  (c) Brent Yorgey 2010+-- License     :  BSD-style (see LICENSE)+-- Maintainer  :  byorgey@cis.upenn.edu+-- Stability   :  experimental+--+-- An interpretation of species as ordinary generating functions,+-- which count unlabeled structures.+--+-----------------------------------------------------------------------------++module Math.Combinatorics.Species.Unlabeled+    ( unlabeled, unlabelled ) where++import Math.Combinatorics.Species.Types+import Math.Combinatorics.Species.Class+import Math.Combinatorics.Species.AST+import Math.Combinatorics.Species.AST.Instances (reflect)+import Math.Combinatorics.Species.CycleIndex+import Math.Combinatorics.Species.NewtonRaphson++import qualified MathObj.PowerSeries as PS++import qualified Algebra.Differential as Differential++import NumericPrelude+import PreludeBase hiding (cycle)++ciErr :: String -> a+ciErr op = error ("unlabeled " ++ op ++ " must go via cycle index series.")++instance Differential.C GF where+  differentiate = ciErr "differentiation"++instance Species GF where+  singleton         = gfFromCoeffs [0,1]+  set               = gfFromCoeffs (repeat 1)+  cycle             = set+  o                 = ciErr "composition"+  (><)              = ciErr "cartesian product"+  (@@)              = ciErr "functor composition"+  ofSize s p        = (liftGF . PS.lift1 $ filterCoeffs p) s+  ofSizeExactly s n = (liftGF . PS.lift1 $ selectIndex n) s++  rec f             = case newtonRaphsonRec f 100 of+                        Nothing -> error $+                          "Unable to express " ++ show f ++ " in the form T = TX*R(T)."+                        Just ls -> ls++unlabeledCoeffs :: GF -> [Integer]+unlabeledCoeffs (GF p) = PS.coeffs p ++ repeat 0++-- | Extract the coefficients of an ordinary generating function as a+--   list of Integers.  In particular, @'unlabeled' s '!!'  n@ is the+--   number of unlabeled @s@-structures on an underlying set of size+--   @n@ (@unlabeled s@ is guaranteed to be infinite).  For example:+--+-- > > take 10 $ unlabeled octopi+-- > [0,1,2,3,5,7,13,19,35,59]+--+--   gives the number of unlabeled octopi on 0, 1, 2, 3, ... 9 elements.+--+--   Actually, the above is something of a white lie, as you may have+--   already realized by looking at the input type of 'unlabeled',+--   which is 'SpeciesAST' rather than the expected 'GF'.  The reason+--   is that although products and sums of unlabeled species+--   correspond to products and sums of ordinary generating functions,+--   other operations such as composition and differentiation do not!+--   In order to compute an ordinary generating function for a species+--   defined in terms of composition and/or differentiation, we must+--   compute the cycle index series for the species and then convert+--   it to an ordinary generating function.  So 'unlabeled' actually+--   works by first reifying the species to an AST and checking which+--   operations are used in its definition, and then choosing to work+--   with cycle index series or directly with (much faster) ordinary+--   generating functions as appropriate.+unlabeled :: SpeciesAST -> [Integer]+unlabeled s+  | needsCI s = unlabeledCoeffs . zToGF . reflect $ s+  | otherwise = unlabeledCoeffs . reflect $ s++-- | A synonym for 'unlabeled', since both spellings are acceptable.+unlabelled :: SpeciesAST -> [Integer]+unlabelled = unlabeled

@@ -1,82 +0,0 @@--------------------------------------------------------------------------------- |--- Module      :  Math.Combinatorics.Species.CycleIndex--- Copyright   :  (c) Brent Yorgey 2010--- License     :  BSD-style (see LICENSE)--- Maintainer  :  byorgey@cis.upenn.edu--- Stability   :  experimental------ An interpretation of species as ordinary generating functions,--- which count unlabelled structures.-----------------------------------------------------------------------------------module Math.Combinatorics.Species.Unlabelled-    ( unlabelled ) where--import Math.Combinatorics.Species.Types-import Math.Combinatorics.Species.Class-import Math.Combinatorics.Species.AST-import Math.Combinatorics.Species.AST.Instances (reflect)-import Math.Combinatorics.Species.CycleIndex-import Math.Combinatorics.Species.NewtonRaphson--import qualified MathObj.PowerSeries as PS--import qualified Algebra.Differential as Differential--import NumericPrelude-import PreludeBase hiding (cycle)--ciErr :: String -> a-ciErr op = error ("unlabelled " ++ op ++ " must go via cycle index series.")--instance Differential.C GF where-  differentiate = ciErr "differentiation"--instance Species GF where-  singleton         = gfFromCoeffs [0,1]-  set               = gfFromCoeffs (repeat 1)-  cycle             = set-  o                 = ciErr "composition"-  (><)              = ciErr "cartesian product"-  (@@)              = ciErr "functor composition"-  ofSize s p        = (liftGF . PS.lift1 $ filterCoeffs p) s-  ofSizeExactly s n = (liftGF . PS.lift1 $ selectIndex n) s--  rec f             = case newtonRaphsonRec f 100 of-                        Nothing -> error $-                          "Unable to express " ++ show f ++ " in the form T = TX*R(T)."-                        Just ls -> ls--unlabelledCoeffs :: GF -> [Integer]-unlabelledCoeffs (GF p) = PS.coeffs p ++ repeat 0---- | Extract the coefficients of an ordinary generating function as a---   list of Integers.  In particular, @'unlabelled' s '!!'  n@ is the---   number of unlabelled @s@-structures on an underlying set of size---   @n@ (@unlabelled s@ is guaranteed to be infinite).  For example:------ > > take 10 $ unlabelled octopi--- > [0,1,2,3,5,7,13,19,35,59]------   gives the number of unlabelled octopi on 0, 1, 2, 3, ... 9 elements.------   Actually, the above is something of a white lie, as you may have---   already realized by looking at the input type of 'unlabelled',---   which is 'SpeciesAST' rather than the expected 'GF'.  The reason---   is that although products and sums of unlabelled species---   correspond to products and sums of ordinary generating functions,---   other operations such as composition and differentiation do not!---   In order to compute an ordinary generating function for a species---   defined in terms of composition and/or differentiation, we must---   compute the cycle index series for the species and then convert---   it to an ordinary generating function.  So 'unlabelled' actually---   works by first reifying the species to an AST and checking which---   operations are used in its definition, and then choosing to work---   with cycle index series or directly with (much faster) ordinary---   generating functions as appropriate.-unlabelled :: SpeciesAST -> [Integer]-unlabelled s-  | needsCI s = unlabelledCoeffs . zToGF . reflect $ s-  | otherwise = unlabelledCoeffs . reflect $ s

@@ -1,5 +1,5 @@ name:           species-version:        0.3.1+version:        0.3.2 license:        BSD3 license-file:   LICENSE build-type:     Simple@@ -11,7 +11,7 @@ synopsis:       Computational combinatorial species  description:    A DSL for describing and computing with combinatorial species,-                e.g. counting labelled or unlabelled structures, or generating+                e.g. counting labeled or unlabeled structures, or generating                 a list of all labeled structures for a species. homepage:       http://www.cis.upenn.edu/~byorgey/species extra-source-files: CHANGES@@ -28,8 +28,8 @@     Math.Combinatorics.Species     Math.Combinatorics.Species.Class     Math.Combinatorics.Species.Types-    Math.Combinatorics.Species.Labelled-    Math.Combinatorics.Species.Unlabelled+    Math.Combinatorics.Species.Labeled+    Math.Combinatorics.Species.Unlabeled     Math.Combinatorics.Species.CycleIndex     Math.Combinatorics.Species.AST     Math.Combinatorics.Species.AST.Instances