Unlabelled.hs

-- | 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.Algebra
import Math.Combinatorics.Species.CycleIndex

import qualified MathObj.PowerSeries as PS

import qualified Algebra.Differential as Differential

import NumericPrelude
import PreludeBase hiding (cycle)

instance Differential.C GF where
  differentiate = error "unlabelled differentiation must go via cycle index series."

instance Species GF where
  singleton         = gfFromCoeffs [0,1]
  set               = gfFromCoeffs (repeat 1)
  cycle             = set
  o                 = error "unlabelled composition must go via cycle index series."
  ofSize s p        = (liftGF . PS.lift1 $ filterCoeffs p) s
  ofSizeExactly s n = (liftGF . PS.lift1 $ selectIndex n) s

  (GF (PS.Cons (x:_))) .: GF (PS.Cons xs)
    = GF (PS.Cons (x:tail xs))

unlabelledCoeffs :: GF -> [Integer]
unlabelledCoeffs (GF p) = PS.coeffs p

-- | 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:
--
-- > > 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 'SpeciesAlg' 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,
--   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 whether it uses
--   composition or differentiation, and using operations on cycle
--   index series if it does, and (much faster) operations directly on
--   ordinary generating functions otherwise.
unlabelled :: SpeciesAlg -> [Integer]
unlabelled s 
  | needsZ s = unlabelledCoeffs . zToGF . reflect $ s
  | otherwise             = unlabelledCoeffs . reflect $ s