{-# LANGUAGE NoImplicitPrelude
, GeneralizedNewtypeDeriving
#-}
-----------------------------------------------------------------------------
-- |
-- Module : Math.Combinatorics.Species.Types
-- Copyright : (c) Brent Yorgey 2010
-- License : BSD-style (see LICENSE)
-- Maintainer : byorgey@cis.upenn.edu
-- Stability : experimental
--
-- Some common types used by the species library, along with some
-- utility functions.
--
-----------------------------------------------------------------------------
module Math.Combinatorics.Species.Types
( -- * Miscellaneous
CycleType
-- * Series types
, EGF(..)
, egfFromCoeffs
, liftEGF
, liftEGF2
, GF(..)
, gfFromCoeffs
, liftGF
, liftGF2
, CycleIndex(..)
, ciFromMonomials
, liftCI
, liftCI2
-- * Series utility functions
, filterCoeffs
, selectIndex
) where
import NumericPrelude
import PreludeBase
import Data.List (genericReplicate)
import qualified MathObj.PowerSeries as PS
import qualified MathObj.MultiVarPolynomial as MVP
import qualified MathObj.Monomial as Monomial
import qualified Algebra.Additive as Additive
import qualified Algebra.Ring as Ring
import qualified Algebra.Differential as Differential
import qualified Algebra.ZeroTestable as ZeroTestable
import qualified Algebra.Field as Field
-- | A representation of the cycle type of a permutation. If @c ::
-- CycleType@ and @(k,n) ``elem`` c@, then the permutation has @n@
-- cycles of size @k@.
type CycleType = [(Integer, Integer)]
------------------------------------------------------------
-- Series types ------------------------------------------
------------------------------------------------------------
-- | Exponential generating functions, for counting labeled species.
newtype EGF = EGF { unEGF :: PS.T Rational }
deriving (Additive.C, Differential.C, Ring.C, Show)
egfFromCoeffs :: [Rational] -> EGF
egfFromCoeffs = EGF . PS.fromCoeffs
liftEGF :: (PS.T Rational -> PS.T Rational) -> EGF -> EGF
liftEGF f (EGF x) = EGF (f x)
liftEGF2 :: (PS.T Rational -> PS.T Rational -> PS.T Rational)
-> EGF -> EGF -> EGF
liftEGF2 f (EGF x) (EGF y) = EGF (f x y)
-- | Ordinary generating functions, for counting unlabeled species.
newtype GF = GF (PS.T Integer)
deriving (Additive.C, Ring.C, Show)
gfFromCoeffs :: [Integer] -> GF
gfFromCoeffs = GF . PS.fromCoeffs
liftGF :: (PS.T Integer -> PS.T Integer) -> GF -> GF
liftGF f (GF x) = GF (f x)
liftGF2 :: (PS.T Integer -> PS.T Integer -> PS.T Integer)
-> GF -> GF -> GF
liftGF2 f (GF x) (GF y) = GF (f x y)
-- | Cycle index series.
newtype CycleIndex = CI (MVP.T Rational)
deriving (Additive.C, Ring.C, Differential.C, Show)
ciFromMonomials :: [Monomial.T Rational] -> CycleIndex
ciFromMonomials = CI . MVP.Cons
liftCI :: (MVP.T Rational -> MVP.T Rational)
-> CycleIndex -> CycleIndex
liftCI f (CI x) = CI (f x)
liftCI2 :: (MVP.T Rational -> MVP.T Rational -> MVP.T Rational)
-> CycleIndex -> CycleIndex -> CycleIndex
liftCI2 f (CI x) (CI y) = CI (f x y)
------------------------------------------------------------
-- Some series utility functions -------------------------
------------------------------------------------------------
-- | Filter the coefficients of a series according to a predicate.
filterCoeffs :: (Additive.C a) => (Integer -> Bool) -> [a] -> [a]
filterCoeffs p = zipWith (filterCoeff p) [0..]
where filterCoeff p n x | p n = x
| otherwise = Additive.zero
-- | Set every coefficient of a series to 0 except the selected
-- index. Truncate any trailing zeroes.
selectIndex :: (Ring.C a, Eq a) => Integer -> [a] -> [a]
selectIndex n xs = xs'
where mx = safeIndex n xs
safeIndex _ [] = Nothing
safeIndex 0 (x:_) = Just x
safeIndex n (_:xs) = safeIndex (n-1) xs
xs' = case mx of
Just 0 -> []
Just x -> genericReplicate n 0 ++ [x]
_ -> []