# LANGUAGE NoImplicitPrelude 
            , CPP 
            , GeneralizedNewtypeDeriving 
   #
           , CPP
           , GeneralizedNewtypeDeriving
  #-}

-----------------------------------------------------------------------------
-- |
-- Module      :  Math.Combinatorics.Species.Types
  Copyright    :   ( c )   2010
-- License     :  BSD-style (see LICENSE)
-- Maintainer  :  
-- 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
#if MIN_VERSION_numeric_prelude(0,2,0)
#else
import PreludeBase
#endif
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 .  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 x | x /= zero
                    -> genericReplicate n zero ++ [x]
                  _ -> []

---------------------------------------------------------------------------
 |
 Module      :  Math.Combinatorics.Species.Types
 License     :  BSD-style (see LICENSE)
 Maintainer  :  
 Stability   :  experimental

 Some common types used by the species library, along with some
 utility functions.

---------------------------------------------------------------------------
 * Miscellaneous
 * Series types
 * Series utility functions
 | A representation of the cycle type of a permutation.  If @c ::
   cycles of size @k@.
----------------------------------------------------------
----------------------------------------
----------------------------------------------------------
 | Exponential generating functions, for counting labeled species.
 | Ordinary generating functions, for counting unlabeled species.
 | Cycle index series.
----------------------------------------------------------
  Some series utility functions  -------------------------
----------------------------------------------------------
 | Filter the coefficients of a series according to a predicate.
# LANGUAGE NoImplicitPrelude 
            , CPP 
            , GeneralizedNewtypeDeriving 
   #
           , CPP
           , GeneralizedNewtypeDeriving
  #-}

  Copyright    :   ( c )   2010

module Math.Combinatorics.Species.Types

      CycleType


    , EGF(..)
    , egfFromCoeffs
    , liftEGF
    , liftEGF2

    , GF(..)
    , gfFromCoeffs
    , liftGF
    , liftGF2

    , CycleIndex(..)
    , ciFromMonomials
    , liftCI
    , liftCI2


    , filterCoeffs
    , selectIndex

    ) where

import NumericPrelude
#if MIN_VERSION_numeric_prelude(0,2,0)
#else
import PreludeBase
#endif
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

    CycleType@ and @(k , n ) ` ` elem ` ` c@ , then the permutation has @n@
type CycleType = [(Integer, Integer)]


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)

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)

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)


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 .  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 x | x /= zero
                    -> genericReplicate n zero ++ [x]
                  _ -> []
