Class.hs

{-# LANGUAGE NoImplicitPrelude #-}

-- | The Species type class, which defines a small DSL for describing
--   combinatorial species.  Other modules in this library provide
--   specific instances which allow computing various properties of
--   combinatorial species.
module Math.Combinatorics.Species.Class
    (
      -- * The Species type class
      Species(..)

      -- * Convenience methods
      -- $synonyms

    , oneHole
    , madeOf
    , x
    , e
    , sets
    , cycles

      -- * Derived operations
      -- $derived_ops

    , pointed
    , nonEmpty

      -- * Derived species
      -- $derived

    , list, lists
    , element, elements
    , octopus, octopi
    , partition, partitions
    , permutation, permutations
    , subset, subsets
    , ballot, ballots
    , ksubset, ksubsets

    ) where

import qualified Algebra.Differential as Differential

import NumericPrelude
import PreludeBase hiding (cycle)

infixr 5 .:

-- | The Species type class.  Note that the @Differential@ constraint
--   requires s to be a differentiable ring, which means that every
--   instance must also implement instances for "Algebra.Additive"
--   (the species 0 and species addition, i.e. disjoint sum),
--   "Algebra.Ring" (the species 1 and species multiplication,
--   i.e. partitional product), and "Algebra.Differential" (species
--   differentiation, i.e. adjoining a distinguished element).
--
--   Note that the 'o' operation can be used infix to suggest common
--   notation for composition, and also to be read as an abbreviation
--   for \"of\", as in \"top o' the mornin'\": @set \`o\` nonEmpty
--   sets@.
class (Differential.C s) => Species s where

  -- | The species X of singletons
  singleton :: s

  -- | The species E of sets
  set       :: s

  -- | The species C of cyclical orderings (cycles/rings)
  cycle     :: s

  -- | Partitional composition
  o         :: s -> s -> s

  -- | Only put a structure on underlying sets whose size satisfies
  --   the predicate.
  ofSize    :: s -> (Integer -> Bool) -> s

  -- | Only put a structure on underlying sets of the given size.  We
  --   include this as a special case, instead of just using @ofSize
  --   (==k)@, since it can be more efficient: we get to turn infinite
  --   lists of coefficients into finite ones.
  ofSizeExactly :: s -> Integer -> s

  -- | @s1 .: s2@ is the species which puts an s1 structure on the
  --   empty set and an s2 structure on anything else.  Useful for
  --   getting recursively defined species off the ground.
  (.:)      :: s -> s -> s

-- $synonyms
-- Some synonyms are provided for convenience.  In particular,
-- gramatically it can often be convenient to have both the singular
-- and plural versions of species, for example, @set \`o\` nonEmpty
-- sets@.

-- | A convenient synonym for differentiation.  F'-structures look
--   like F-structures on a set formed by adjoining a distinguished
--   \"hole\" element to the underlying set.
oneHole :: (Species s) => s -> s
oneHole = Differential.differentiate

-- | A synonym for 'o' (partitional composition).
madeOf :: Species s => s -> s -> s
madeOf = o

-- | A synonym for 'singleton'.
x :: Species s => s
x          = singleton

-- | A synonym for 'set'.
e :: Species s => s
e          = set

sets :: Species s => s
sets       = set

cycles :: Species s => s
cycles     = cycle

-- $derived_ops
-- Some derived operations on species.

-- | Combinatorially, the operation of pointing picks out a
--   distinguished element from an underlying set.  It is equivalent
--   to the operator @x d/dx@.
pointed :: Species s => s -> s
pointed = (x *) . Differential.differentiate

-- | Don't put a structure on the empty set.
nonEmpty  :: Species s => s -> s
nonEmpty = flip ofSize (>0)


-- $derived
-- Some species that can be defined in terms of the primitive species
-- operations.

-- | The species L of linear orderings (lists): since lists are
--   isomorphic to cycles with a hole, we may take L = C'.
list :: Species s => s
list  = oneHole cycle

-- | A convenient synonym for 'list'.
lists :: Species s => s
lists = list

-- | Structures of the species eps of elements are just elements of
--   the underlying set: eps = X * E.
elements, element :: Species s => s
element = x * e
elements = element

-- | An octopus is a cyclic arrangement of lists, so called because
--   the lists look like \"tentacles\" attached to the cyclic
--   \"body\": Oct = C o E+ .
octopi, octopus :: Species s => s
octopus = cycle `o` nonEmpty lists
octopi  = octopus

-- | The species of set partitions is just the composition E o E+,
--   that is, sets of nonempty sets.
partitions, partition :: Species s => s
partition  = set `o` nonEmpty sets
partitions = partition

-- | A permutation is a set of disjoint cycles: S = E o C.
permutations, permutation :: Species s => s
permutation = set `o` cycles
permutations = permutation

-- | The species p of subsets is given by p = E * E.
subsets, subset :: Species s => s
subset = set * set
subsets = subset

-- | The species Bal of ballots consists of linear orderings of
--   nonempty sets: Bal = L o E+.
ballots, ballot :: Species s => s
ballot = list `o` nonEmpty sets
ballots = ballot

-- | Subsets of size exactly k, p[k] = E_k * E.
ksubsets, ksubset :: Species s => Integer -> s
ksubset k = (set `ofSizeExactly` k) * set
ksubsets = ksubset