{-# 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