species 0.3.2 → 0.3.2.1
raw patch · 15 files changed
+121/−38 lines, 15 filesdep ~basedep ~containersdep ~multiset-comb
Dependency ranges changed: base, containers, multiset-comb, numeric-prelude, template-haskell
Files
- CHANGES +3/−0
- Math/Combinatorics/Species/AST.hs +10/−6
- Math/Combinatorics/Species/AST/Instances.hs +7/−3
- Math/Combinatorics/Species/Class.hs +14/−2
- Math/Combinatorics/Species/CycleIndex.hs +7/−3
- Math/Combinatorics/Species/Enumerate.hs +13/−8
- Math/Combinatorics/Species/Labeled.hs +4/−0
- Math/Combinatorics/Species/NewtonRaphson.hs +5/−1
- Math/Combinatorics/Species/Simplify.hs +4/−1
- Math/Combinatorics/Species/Structures.hs +22/−1
- Math/Combinatorics/Species/TH.hs +5/−0
- Math/Combinatorics/Species/Types.hs +7/−3
- Math/Combinatorics/Species/Unlabeled.hs +4/−0
- Math/Combinatorics/Species/Util/Interval.hs +10/−4
- species.cabal +6/−6
CHANGES view
@@ -18,3 +18,6 @@ * 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++0.3.2.1 12 Sep 2011+ * update to build with GHC 7
Math/Combinatorics/Species/AST.hs view
@@ -1,4 +1,5 @@ {-# LANGUAGE NoImplicitPrelude+ , CPP , GADTs , TypeFamilies , KindSignatures@@ -56,7 +57,10 @@ import Data.Maybe (fromMaybe) import NumericPrelude+#if MIN_VERSION_numeric_prelude(0,2,0)+#else import PreludeBase hiding (cycle)+#endif ------------------------------------------------------------ -- Untyped AST -------------------------------------------@@ -142,15 +146,15 @@ -- structures. interval :: TSpeciesAST s -> Interval interval TZero = emptyI-interval TOne = 0-interval (TN n) = 0-interval TX = 1+interval TOne = zero+interval (TN n) = zero+interval TX = one interval TE = natsI-interval TC = fromI 1+interval TC = fromI one interval TL = natsI interval TSubset = natsI interval (TKSubset k) = fromI (fromInteger k)-interval TElt = fromI 1+interval TElt = fromI one interval (f :+:: g) = getI f `I.union` getI g interval (f :*:: g) = getI f + getI g interval (f :.:: g) = getI f * getI g@@ -164,7 +168,7 @@ interval (TDer f) = decrI (getI f) interval (TOfSize f p) = fromI $ smallestIn (getI f) p interval (TOfSizeExactly f n) = fromInteger n `I.intersect` getI f-interval (TNonEmpty f) = fromI 1 `I.intersect` getI f+interval (TNonEmpty f) = fromI one `I.intersect` getI f interval (TRec f) = interval (apply f TOmega) interval TOmega = omegaI
Math/Combinatorics/Species/AST/Instances.hs view
@@ -1,4 +1,4 @@-{-# LANGUAGE GADTs #-}+{-# LANGUAGE CPP, GADTs #-} ----------------------------------------------------------------------------- -- |@@ -24,8 +24,12 @@ ( reify, reifyE, reflect, reflectT, reflectE ) where +#if MIN_VERSION_numeric_prelude(0,2,0)+import NumericPrelude hiding (cycle)+#else import NumericPrelude import PreludeBase hiding (cycle)+#endif import Math.Combinatorics.Species.Class import Math.Combinatorics.Species.AST@@ -284,8 +288,8 @@ -- | Reflect an AST back into any instance of the 'Species' class. reflect :: Species s => SpeciesAST -> s-reflect Zero = 0-reflect One = 1+reflect Zero = zero+reflect One = one reflect (N n) = fromInteger n reflect X = singleton reflect E = set
Math/Combinatorics/Species/Class.hs view
@@ -1,4 +1,6 @@-{-# LANGUAGE NoImplicitPrelude #-}+{-# LANGUAGE NoImplicitPrelude+ , CPP+ #-} ----------------------------------------------------------------------------- -- |@@ -25,7 +27,7 @@ , oneHole , x - -- ** Plurals+ -- ** Plurals and synonyms -- | It can be grammatically convenient to define plural -- versions of species as synonyms for the singular versions.@@ -38,6 +40,8 @@ , ksubsets , elements + , bag, bags+ -- * Derived operations -- $derived_ops @@ -57,8 +61,12 @@ import qualified Algebra.Differential as Differential +#if MIN_VERSION_numeric_prelude(0,2,0)+import NumericPrelude hiding (cycle)+#else import NumericPrelude import PreludeBase hiding (cycle)+#endif import Math.Combinatorics.Species.AST @@ -180,6 +188,10 @@ sets :: Species s => s sets = set++bag, bags :: Species s => s+bag = set+bags = set cycles :: Species s => s cycles = cycle
Math/Combinatorics/Species/CycleIndex.hs view
@@ -1,4 +1,5 @@ {-# LANGUAGE NoImplicitPrelude+ , CPP , FlexibleInstances #-} @@ -50,7 +51,10 @@ import Control.Arrow ((&&&), first, second) import NumericPrelude+#if MIN_VERSION_numeric_prelude(0,2,0)+#else import PreludeBase hiding (cycle)+#endif -- | An interpretation of species expressions as cycle index series. -- For the definition of the 'CycleIndex' type, see@@ -86,7 +90,7 @@ -- | @'ezCoeff' js@ is the coefficient of the corresponding monomial in -- the cycle index series for the species of sets. ezCoeff :: CycleType -> Rational-ezCoeff js = toRational $ 1 / aut js+ezCoeff js = toRational . recip $ aut js -- | @aut js@ is is the number of automorphisms of a permutation with -- cycle type @js@ (i.e. a permutation which has @n@ cycles of size@@ -153,7 +157,7 @@ where insertZeros' _ [] = [] insertZeros' (n:ns) ((pow,c):pcs)- | n < pow = genericReplicate (pow - n) 0+ | n < pow = genericReplicate (pow - n) zero ++ insertZeros' (genericDrop (pow - n) (n:ns)) ((pow,c):pcs) | otherwise = c : insertZeros' ns pcs @@ -222,7 +226,7 @@ concat $ for [0..] $ \n -> for (intPartitions n) $ \nn -> Monomial.mkMonomial- (toRational (1 / aut nn) * (zFix f (gnn nn n) % 1))+ (toRational (recip (aut nn)) * (zFix f (gnn nn n) % 1)) nn where for = flip map
Math/Combinatorics/Species/Enumerate.hs view
@@ -1,4 +1,5 @@ {-# LANGUAGE NoImplicitPrelude+ , CPP , GADTs , FlexibleContexts , ScopedTypeVariables@@ -58,7 +59,10 @@ import Data.Typeable import NumericPrelude+#if MIN_VERSION_numeric_prelude(0,2,0)+#else import PreludeBase hiding (cycle)+#endif -- | Given an AST describing a species, with a phantom type parameter -- representing the structure of the species, and an underlying@@ -100,14 +104,8 @@ enumerate' (f :+:: g) xs = map Inl (enumerate' (stripI f) xs) ++ map Inr (enumerate' (stripI g) xs) - -- XXX working here. Need to change this to use the annotations- -- which are now contained in f and g. I suppose MS.splits should- -- be changed (?) to only return splits which are of appropriate- -- sizes. I guess a quick and dirty solution is just to filter the- -- things returned by splits to make sure they are in the- -- appropriate ranges.-- -- XXX use multiset operations instead of 'length'+ -- A better solution here might be to change MS.splits to only+ -- return splits which are of appropriate sizes. enumerate' (f :*:: g) xs = [ Prod x y | (s1,s2) <- MS.splits xs@@ -123,10 +121,17 @@ , xs' <- MS.sequenceMS . fmap (enumerate' (stripI g)) $ p , y <- enumerate' (stripI f) xs' ]+enumerate' (f :><:: g) xs+ | any (/= 1) $ MS.getCounts xs+ = error "Unlabeled enumeration does not (yet) work with cartesian product." enumerate' (f :><:: g) xs = [ Prod x y | x <- enumerate' (stripI f) xs , y <- enumerate' (stripI g) xs ]++enumerate' (f :@:: g) xs+ | any (/= 1) $ MS.getCounts xs+ = error "Unlabeled enumeration does not (yet) work with functor composition." enumerate' (f :@:: g) xs = map Comp . enumerate' (stripI f) . MS.fromDistinctList
Math/Combinatorics/Species/Labeled.hs view
@@ -1,4 +1,5 @@ {-# LANGUAGE NoImplicitPrelude+ , CPP , GeneralizedNewtypeDeriving , PatternGuards #-}@@ -38,7 +39,10 @@ import qualified MathObj.FactoredRational as FQ import NumericPrelude+#if MIN_VERSION_numeric_prelude(0,2,0)+#else import PreludeBase hiding (cycle)+#endif facts :: [Integer] facts = 1 : zipWith (*) [1..] facts
Math/Combinatorics/Species/NewtonRaphson.hs view
@@ -1,4 +1,5 @@ {-# LANGUAGE NoImplicitPrelude+ , CPP #-} -----------------------------------------------------------------------------@@ -28,7 +29,10 @@ ) where import NumericPrelude+#if MIN_VERSION_numeric_prelude(0,2,0)+#else import PreludeBase+#endif import Math.Combinatorics.Species.Class import Math.Combinatorics.Species.AST@@ -67,7 +71,7 @@ -- r k@ computes a species which has contact at least @k@ with the -- species @t = x '*' (r ``o`` t)@. newtonRaphson :: Species s => s -> Integer -> s-newtonRaphson r n = newtonRaphson' 0 0+newtonRaphson r n = newtonRaphson' zero 0 where newtonRaphson' a k | k >= n = a | otherwise = newtonRaphson' (newtonRaphsonIter r k a) (2*k + 2)
Math/Combinatorics/Species/Simplify.hs view
@@ -1,4 +1,4 @@-{-# LANGUAGE NoImplicitPrelude, GADTs #-}+{-# LANGUAGE CPP, NoImplicitPrelude, GADTs #-} ----------------------------------------------------------------------------- -- |@@ -18,7 +18,10 @@ ) where import NumericPrelude+#if MIN_VERSION_numeric_prelude(0,2,0)+#else import PreludeBase+#endif import Math.Combinatorics.Species.AST import Math.Combinatorics.Species.AST.Instances
Math/Combinatorics/Species/Structures.hs view
@@ -1,4 +1,5 @@ {-# LANGUAGE NoImplicitPrelude+ , CPP , GeneralizedNewtypeDeriving , FlexibleContexts , DeriveDataTypeable@@ -39,8 +40,11 @@ ) where import NumericPrelude+#if MIN_VERSION_numeric_prelude(0,2,0)+#else import PreludeBase-import Data.List (intercalate)+#endif+import Data.List (intercalate, foldl', delete, inits, tails) import Data.Typeable @@ -134,6 +138,10 @@ deriving (Functor, Typeable) instance (Show a) => Show (Cycle a) where show (Cycle xs) = "<" ++ intercalate "," (map show xs) ++ ">"+instance Eq a => Eq (Cycle a) where+ Cycle xs == Cycle ys = any (==ys) (rotations xs)+ where rotations xs = zipWith (++) (tails xs)+ (inits xs) -- | Set structure. A value of type @'Set' a@ is implemented as @[a]@, -- but thought of as an unordered set.@@ -141,6 +149,9 @@ deriving (Functor, Typeable) instance (Show a) => Show (Set a) where show (Set xs) = "{" ++ intercalate "," (map show xs) ++ "}"+instance Eq a => Eq (Set a) where+ Set xs == Set ys = xs `subBag` ys && ys `subBag` xs+ where subBag b = null . foldl' (flip delete) b -- | 'Star' is isomorphic to 'Maybe', but with a more useful 'Show' -- instance for our purposes. Used to implement species@@ -153,6 +164,16 @@ instance (Show a) => Show (Star a) where show Star = "*" show (Original a) = show a++-- Note, the above instance does not properly display structures+-- arising from higher derivatives, since the different holes are not+-- distinguished (although they should be). This could be fixed by+-- prefixing all the Original elements with some special character;+-- then you could tell the difference between, say, "*" and "~*" (if ~+-- was the special character). However, this solution seems a bit+-- heavyweight. Multiple differentiation is not that common, and you+-- can always do case analysis to correctly figure out the structure;+-- it's just the String representations which would be misleading. -- XXX add some examples for Mu/Interp
Math/Combinatorics/Species/TH.hs view
@@ -1,4 +1,5 @@ {-# LANGUAGE NoImplicitPrelude+ , CPP , TemplateHaskell , FlexibleInstances , TypeSynonymInstances@@ -46,8 +47,12 @@ , deriveSpecies ) where +#if MIN_VERSION_numeric_prelude(0,2,0)+import NumericPrelude hiding (cycle)+#else import NumericPrelude import PreludeBase hiding (cycle)+#endif import Math.Combinatorics.Species.Class import Math.Combinatorics.Species.Enumerate
Math/Combinatorics/Species/Types.hs view
@@ -1,4 +1,5 @@ {-# LANGUAGE NoImplicitPrelude+ , CPP , GeneralizedNewtypeDeriving #-} @@ -45,7 +46,10 @@ ) where import NumericPrelude+#if MIN_VERSION_numeric_prelude(0,2,0)+#else import PreludeBase+#endif import Data.List (genericReplicate) @@ -130,6 +134,6 @@ safeIndex 0 (x:_) = Just x safeIndex n (_:xs) = safeIndex (n-1) xs xs' = case mx of- Just 0 -> []- Just x -> genericReplicate n 0 ++ [x]- _ -> []+ Just x | x /= zero+ -> genericReplicate n zero ++ [x]+ _ -> []
Math/Combinatorics/Species/Unlabeled.hs view
@@ -1,3 +1,4 @@+{-# LANGUAGE CPP #-} ----------------------------------------------------------------------------- -- | -- Module : Math.Combinatorics.Species.CycleIndex@@ -26,7 +27,10 @@ import qualified Algebra.Differential as Differential import NumericPrelude+#if MIN_VERSION_numeric_prelude(0,2,0)+#else import PreludeBase hiding (cycle)+#endif ciErr :: String -> a ciErr op = error ("unlabeled " ++ op ++ " must go via cycle index series.")
Math/Combinatorics/Species/Util/Interval.hs view
@@ -1,4 +1,5 @@ {-# LANGUAGE NoImplicitPrelude+ , CPP #-} -----------------------------------------------------------------------------@@ -31,8 +32,13 @@ , natsI, fromI, emptyI, omegaI ) where +#if MIN_VERSION_numeric_prelude(0,2,0)+import NumericPrelude hiding (min, max, elem)+import Prelude (min, max)+#else import NumericPrelude import PreludeBase hiding (elem)+#endif import qualified Algebra.Additive as Additive import qualified Algebra.Ring as Ring@@ -109,14 +115,14 @@ -- | Intervals can be added by adding their endpoints pointwise. instance Additive.C Interval where- zero = I 0 0+ zero = I zero zero (I l1 h1) + (I l2 h2) = I (l1 + l2) (h1 + h2) negate = error "Interval negation: intervals only form a semiring" -- | Intervals form a semiring, with the multiplication operation -- being pointwise multiplication of their endpoints. instance Ring.C Interval where- one = I 1 1+ one = I one one (I l1 h1) * (I l2 h2) = I (l1 * l2) (h1 * h2) fromInteger n = I (Nat n) (Nat n) @@ -134,7 +140,7 @@ -- | The range [0,omega] containing all natural numbers. natsI :: Interval-natsI = I 0 Omega+natsI = I zero Omega -- | Construct an open range [n,omega]. fromI :: NatO -> Interval@@ -142,7 +148,7 @@ -- | The empty interval. emptyI :: Interval-emptyI = I 1 0+emptyI = I one zero -- | The interval which contains only omega. omegaI :: Interval
species.cabal view
@@ -1,10 +1,10 @@ name: species-version: 0.3.2+version: 0.3.2.1 license: BSD3 license-file: LICENSE build-type: Simple cabal-version: >= 1.6-tested-with: GHC >= 6.10 && < 6.11, GHC == 6.12.1+tested-with: GHC == 6.12.1, GHC == 7.0.3 author: Brent Yorgey maintainer: Brent Yorgey <byorgey@cis.upenn.edu> category: Math@@ -20,10 +20,10 @@ location: http://code.haskell.org/~byorgey/code/species Library- build-depends: base >= 3 && < 5, numeric-prelude >= 0.1.1 && < 0.2,- np-extras >= 0.2.0.2 && < 0.3, containers >= 0.2 && < 0.4,- multiset-comb >= 0.2.1,- template-haskell >= 2.4 && < 2.5+ build-depends: base >= 3 && < 4.5, numeric-prelude >= 0.1.1 && < 0.3,+ np-extras >= 0.2.0.2 && < 0.3, containers >= 0.2 && < 0.5,+ multiset-comb >= 0.2.1 && < 0.3,+ template-haskell >= 2.4 && < 2.7 exposed-modules: Math.Combinatorics.Species Math.Combinatorics.Species.Class