```-- | 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
```