Class.hs

{-# LANGUAGE NoImplicitPrelude #-}

-----------------------------------------------------------------------------
-- |
-- Module      :  Math.Combinatorics.Species.Class
-- Copyright   :  (c) Brent Yorgey 2010
-- License     :  BSD-style (see LICENSE)
-- Maintainer  :  byorgey@cis.upenn.edu
-- Stability   :  experimental
--
-- 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

    , oneHole
    , x

      -- ** Plurals

      -- | It can be grammatically convenient to define plural
      -- versions of species as synonyms for the singular versions.
      -- For example, we can use @'set' ``o`` 'nonEmpty' 'sets'@
      -- instead of @'set' ``o`` 'nonEmpty' 'set'@.
    , sets
    , cycles
    , linOrds
    , subsets
    , ksubsets
    , elements

      -- * Derived operations
      -- $derived_ops

    , pointed

      -- * Derived species
      -- $derived

    , octopus, octopi
    , partition, partitions
    , permutation, permutations
    , ballot, ballots
    , simpleGraph, simpleGraphs
    , directedGraph, directedGraphs

    ) where

import qualified Algebra.Differential as Differential

import NumericPrelude
import PreludeBase hiding (cycle)

import Math.Combinatorics.Species.AST

-- | 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).
--
--   Minimal complete definition: 'singleton', 'set', 'cycle', 'o',
--   '><', '@@', 'ofSize'.
--
--   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. Puts a singleton structure on an
  --   underlying label set of size 1, and no structures on any other
  --   underlying label sets.  'x' is also provided as a synonym.
  singleton :: s

  -- | The species @E@ of sets.  Puts a singleton structure on /any/
  --   underlying label set.
  set :: s

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

  -- | The species @L@ of linear orderings (lists). Since linear
  --   orderings are isomorphic to cyclic orderings with a hole, we
  --   may take @'linOrd' = 'oneHole' 'cycle'@ as the default
  --   implementation; 'linOrd' is included in the 'Species' class so it
  --   can be special-cased for enumeration.
  linOrd :: s
  linOrd = oneHole cycle

  -- | The species @p@ of subsets is given by @'subset' = 'set' *
  --   'set'@. 'subset' is included in the 'Species' class so it can
  --   be overridden when enumerating structures: by default the
  --   enumeration code would generate a pair of the subset and its
  --   complement, but normally when thinking about subsets we only
  --   want to see the elements in the subset.  To explicitly
  --   enumerate subset/complement pairs, you can use @'set' * 'set'@
  --   directly.
  subset :: s
  subset = set * set

  -- | Subsets of size exactly k, @'ksubset' k = ('set'
  -- ``ofSizeExactly`` k) * 'set'@.  Included with a default definition
  -- in the 'Species' class for the same reason as 'subset'.
  ksubset :: Integer -> s
  ksubset k = (set `ofSizeExactly` k) * set

  -- | Structures of the species @e@ of elements are just elements of
  --   the underlying set, @'element' = 'singleton' * 'set'@.  Included
  --   with a default definition in 'Species' class for the same
  --   reason as 'subset' and 'ksubset'.
  element :: s
  element = singleton * set

  -- | Partitional composition.  To form all @(f ``o`` g)@-structures on
  --   the underlying label set U, first form all set partitions of U;
  --   for each partition @p@, put an @f@-structure on the classes of
  --   @p@, and a separate @g@-structure on the elements in each
  --   class.
  o :: s -> s -> s

  -- | Cartisian product of two species.  An @(f '><' g)@-structure
  -- consists of an @f@-structure superimposed on a @g@-structure over
  -- the same underlying set.
  (><) :: s -> s -> s

  -- | Functor composition of two species.  An @(f '@@' g)@-structure
  --   consists of an @f@-structure on the set of all @g@-structures.
  (@@) :: 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.  A
  --   default implementation of @ofSize (==k)@ is provided, but this
  --   method is included in the 'Species' class as a special case
  --   since it can be more efficient: we get to turn infinite lists
  --   of coefficients into finite ones.
  ofSizeExactly :: s -> Integer -> s
  ofSizeExactly s n = s `ofSize` (==n)

  -- | Don't put a structure on the empty set.  The default definition
  --   uses 'ofSize'; included in the 'Species' class so it can be
  --   overriden in special cases (such as when reifying species
  --   expressions).
  nonEmpty :: s -> s
  nonEmpty = flip ofSize (>0)

  -- | 'rec f' is the least fixpoint of (the interpretation of) the
  --   higher-order species constructor 'f'.
  rec :: ASTFunctor f => f -> s

  -- | Omega is the pseudo-species which only puts a structure on
  --   infinite label sets.  Of course this is not really a species,
  --   but it is sometimes a convenient fiction to use Omega to stand
  --   in for recursive occurrences of a species.
  omega :: s

-- | A convenient synonym for differentiation.  @'oneHole'
-- 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 'singleton'.
x :: Species s => s
x = singleton

sets :: Species s => s
sets = set

cycles :: Species s => s
cycles = cycle

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

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

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

linOrds :: Species s => s
linOrds = linOrd

elements :: Species s => s
elements = element

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

-- | The species of set partitions is just the composition @'set'
-- ``o`` 'nonEmpty' 'sets'@.
partitions, partition :: Species s => s
partition  = set `o` nonEmpty sets
partitions = partition

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

subsets :: Species s => s
subsets = subset

-- | The species of ballots consists of linear orderings of
--   nonempty sets: @'ballot' = 'linOrd' ``o`` 'nonEmpty' 'sets'@.
ballots, ballot :: Species s => s
ballot = linOrd `o` nonEmpty sets
ballots = ballot

ksubsets :: Species s => Integer -> s
ksubsets = ksubset

-- | Simple graphs (undirected, without loops). A simple graph is a
--   subset of the set of all size-two subsets of the vertices:
--   @'simpleGraph' = 'subset' '@@' ('ksubset' 2)@.
simpleGraphs, simpleGraph :: Species s => s
simpleGraph = subset @@ (ksubset 2)
simpleGraphs = simpleGraph

-- | A directed graph (with loops) is a subset of all pairs drawn
--   (with replacement) from the set of vertices: @'subset' '@@'
--   ('element' '><' 'element')@.  It can also be thought of as the
--   species of binary relations.
directedGraphs, directedGraph :: Species s => s
directedGraph = subset @@ (element >< element)
directedGraphs = directedGraph