species 0.2 → 0.2.1
raw patch · 8 files changed
+42/−32 lines, 8 files
Files
- Math/Combinatorics/Species.hs +1/−1
- Math/Combinatorics/Species/AST.hs +11/−9
- Math/Combinatorics/Species/Class.hs +8/−6
- Math/Combinatorics/Species/Generate.hs +5/−3
- Math/Combinatorics/Species/Labelled.hs +10/−6
- Math/Combinatorics/Species/Types.hs +3/−3
- Math/Combinatorics/Species/Unlabelled.hs +3/−3
- species.cabal +1/−1
Math/Combinatorics/Species.hs view
@@ -32,6 +32,7 @@ , madeOf , (><), (@@) , x, sets, cycles+ , lists , subsets , ksubsets , elements@@ -40,7 +41,6 @@ , pointed -- ** Derived species- , list, lists , octopus, octopi , partition, partitions , permutation, permutations
Math/Combinatorics/Species/AST.hs view
@@ -38,11 +38,11 @@ -- for that purpose the existential wrapper 'SpeciesAST' is -- provided. data SpeciesTypedAST s where- O :: SpeciesTypedAST Z- I :: SpeciesTypedAST (S Z)+ N :: Integer -> SpeciesTypedAST Z X :: SpeciesTypedAST X E :: SpeciesTypedAST E C :: SpeciesTypedAST C+ L :: SpeciesTypedAST L Subset :: SpeciesTypedAST Sub KSubset :: Integer -> SpeciesTypedAST Sub Elt :: SpeciesTypedAST Elt@@ -63,11 +63,11 @@ NonEmpty :: SpeciesTypedAST f -> SpeciesTypedAST f instance Show (SpeciesTypedAST s) where- showsPrec _ O = showChar '0'- showsPrec _ I = showChar '1'+ showsPrec _ (N n) = shows n showsPrec _ X = showChar 'X' showsPrec _ E = showChar 'E' showsPrec _ C = showChar 'C'+ showsPrec _ L = showChar 'L' showsPrec _ Subset = showChar 'p' showsPrec _ (KSubset n) = showChar 'p' . shows n showsPrec _ (Elt) = showChar 'e'@@ -112,13 +112,14 @@ show (SA f) = show f instance Additive.C SpeciesAST where- zero = SA O+ zero = SA (N 0) (SA f) + (SA g) = SA (f :+: g) negate = error "negation is not implemented yet! wait until virtual species..." instance Ring.C SpeciesAST where (SA f) * (SA g) = SA (f :*: g)- one = SA I+ one = SA (N 1)+ fromInteger n = SA (N n) instance Differential.C SpeciesAST where differentiate (SA f) = SA (Der f)@@ -127,6 +128,7 @@ singleton = SA X set = SA E cycle = SA C+ list = SA L subset = SA Subset ksubset k = SA (KSubset k) element = SA Elt@@ -142,7 +144,7 @@ -- example: -- -- > > reify octopus--- > C . C'++-- > C . L+ -- > > reify (ksubset 3) -- > E3 * E @@ -151,11 +153,11 @@ -- | Reflect an AST back into any instance of the 'Species' class. reflectT :: Species s => SpeciesTypedAST f -> s-reflectT O = zero-reflectT I = one+reflectT (N n) = fromInteger n reflectT X = singleton reflectT E = set reflectT C = cycle+reflectT L = list reflectT Subset = subset reflectT (KSubset k) = ksubset k reflectT Elt = element
Math/Combinatorics/Species/Class.hs view
@@ -17,6 +17,7 @@ , x , sets , cycles+ , lists , subsets , ksubsets , elements@@ -29,7 +30,6 @@ -- * Derived species -- $derived - , list, lists , octopus, octopi , partition, partitions , permutation, permutations@@ -80,6 +80,13 @@ -- | The species C of cyclical orderings (cycles/rings). cycle :: s + -- | The species L of linear orderings (lists): since lists are+ -- isomorphic to cycles with a hole, we may take L = C' as the+ -- default implementation; list is included in the 'Species' class+ -- so it can be special-cased for generation.+ list :: s+ list = oneHole cycle+ -- | The species p of subsets is given by p = E * E. 'subset' has a -- default implementation of @set * set@, but is included in the -- 'Species' class so it can be overridden when generating@@ -186,11 +193,6 @@ -- $derived -- Some species that can be defined in terms of the primitive species -- operations.---- | The species L of linear orderings (lists): since lists are--- isomorphic to cycles with a hole, we may take L = C'.-list :: Species s => s-list = oneHole cycle lists :: Species s => s lists = list
Math/Combinatorics/Species/Generate.hs view
@@ -46,14 +46,14 @@ -- existentially quantified as well; see 'generate' and -- 'generateTyped' below. generateF :: SpeciesTypedAST s -> [a] -> [StructureF s a]-generateF O _ = []-generateF I [] = [Const 1]-generateF I _ = []+generateF (N n) [] = map Const [1..n]+generateF (N _) _ = [] generateF X [x] = [Identity x] generateF X _ = [] generateF E xs = [Set xs] generateF C [] = [] generateF C (x:xs) = map (Cycle . (x:)) (sPermutations xs)+generateF L xs = sPermutations xs generateF Subset xs = map (Set . fst) (pSet xs) generateF (KSubset k) xs = map Set (sKSubsets k xs) generateF Elt xs = map Identity xs@@ -221,6 +221,8 @@ showsPrecST p t = case splitTyConApp t of (tycon, []) -> showString (dropQuals $ tyConString tycon)+ (tycon, [x]) | tyConString tycon == "[]" + -> showChar '[' . showsPrecST 11 x . showChar ']' (tycon, args) -> showParen (p > 9) $ showString (dropQuals $ tyConString tycon) . showChar ' '
Math/Combinatorics/Species/Labelled.hs view
@@ -39,11 +39,12 @@ ofSizeExactly s n = (liftEGF . PS.lift1 $ selectIndex n) s -- | Extract the coefficients of an exponential generating function as--- a list of Integers. 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. For example:+-- a list of Integers. 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]@@ -51,7 +52,10 @@ -- gives the number of labelled octopi on 0, 1, 2, 3, ... 9 elements. labelled :: EGF -> [Integer]-labelled (EGF f) = map numerator . zipWith (*) (map fromInteger facts) . map unLR +labelled (EGF f) = (++repeat 0) + . map numerator + . zipWith (*) (map fromInteger facts) + . map unLR $ PS.coeffs f -- A previous version of this module used an EGF library which
Math/Combinatorics/Species/Types.hs view
@@ -60,7 +60,7 @@ -- * Type-level species -- $typespecies - , Z, S, X, E, C, Sub, Elt, (:+:), (:*:), (:.:), (:><:), (:@:), Der+ , Z, X, E, C, L, Sub, Elt, (:+:), (:*:), (:.:), (:><:), (:@:), Der , StructureF ) where @@ -327,10 +327,10 @@ -- dependently typed language. data Z-data S n data X data E data C+data L data Sub data Elt data (:+:) f g@@ -346,10 +346,10 @@ -- @a@, has type @StructureF s a@. type family StructureF t :: * -> * type instance StructureF Z = Const Integer-type instance StructureF (S s) = Const Integer type instance StructureF X = Identity type instance StructureF E = Set type instance StructureF C = Cycle+type instance StructureF L = [] type instance StructureF Sub = Set type instance StructureF Elt = Identity type instance StructureF (f :+: g) = Sum (StructureF f) (StructureF g)
Math/Combinatorics/Species/Unlabelled.hs view
@@ -32,12 +32,12 @@ ofSizeExactly s n = (liftGF . PS.lift1 $ selectIndex n) s unlabelledCoeffs :: GF -> [Integer]-unlabelledCoeffs (GF p) = PS.coeffs p+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.--- For example:+-- 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]
species.cabal view
@@ -1,5 +1,5 @@ name: species-version: 0.2+version: 0.2.1 license: BSD3 license-file: LICENSE build-type: Simple