Primitive species and species operations

In this second post about my new combinatorial species library, I plan to begin writing about the species DSL itself: what are the primitive combinatorial species and the primitive operations on species? (The first post described the concept of combinatorial species in general. Also, for those following along at home, I’ve just uploaded version 0.2.1 of the species library, which is a vast improvement over 0.1, with many new features and a few bug fixes; just cabal update && cabal upgrade species. Also also, note that it currently only builds on ghc 6.10.x.)

The Species type class

The central point of the combinatorial species formalism is that there is a deep and fruitful analogy between species and certain types of generating functions: every species corresponds to (several different types of) generating functions, and every species operation corresponds, in a fairly natural way, to operations on generating functions. For example, “adding” two species has the combinatorial interpretation of disjoint sum, but also corresponds to generating function addition—that is, the generating function of a sum of species is the sum of their generating functions. Like every good generating function, these generating functions encode various sorts of information about species (such as counting labelled or unlabelled structures), so once we have written down a description of a combinatorial structure using primitive species and species operations, we can use the generating function analogy to compute various properties of the species.

So, how to represent combinatorial species in our library? With a Species type class, of course! The type class mechanism is perfectly suited to this situation—we have an abstract algebraic structure (species and species operations) which can be interpreted in several ways. So we can write down an expression of type Species s => s, and then choose to compute certain things about it simply by choosing what type it should be. Without further ado, let’s see (an idealized version of) the type class itself, defined in Math.Combinatorics.Species.Class:

class (Algebra.Differential.C s) => Species s where
  singleton :: s
  set       :: s
  cycle     :: s

  o         :: s -> s -> s
  cartesian :: s -> s -> s
  fcomp     :: s -> s -> s
  ofSize    :: s -> (Integer -> Bool) -> s

(I’ve actually left out a few methods, but they all share the property that they have default implementations in terms of the other methods, and are only in the class so they can be given specialized implementations in certain instances. I’ve left them out for now to simplify the discussion.)

So we can now write expressions like

(set `ofSize` (>3)) `fcomp` (cycle `o` singleton) :: Species s => s

but what does it mean? (Actually, this particular example is pretty meaningless. =) And what’s that Algebra.Differential.C constraint? Let’s start at the beginning.

0

The Algebra.Differential.C constraint requires any instance of Species to be a differentiable ring. In particular, it (transitively) implies the constraint Algebra.Additive.C, which means that instances of Species must form an additive group: there must be a species operation (+), and a species 0 which is the identity for (+). (It also requires an operation negate which produces additive inverses, but that isn’t implemented yet!) Let’s see what these correspond to.

The species is the Scrooge of the species world: it refuses to create a single structure, no matter how many labels you give it!

The species 0

Let’s see how to use this species with the library:

> take 10 $ labelled 0
[0,0,0,0,0,0,0,0,0,0]
> take 10 $ unlabelled 0
[0,0,0,0,0,0,0,0,0,0]
> generate 0 ([1..3] :: [Int])
[]


Pretty boring, huh? Well, it’s supposed to be. doesn’t get explicitly used very much, but it’s nice to know it’s there.

(Also, remember that to follow along, you’ll have to start ghci with the -XNoImplicitPrelude flag, then remove the loaded Prelude module with :m -Prelude, and then load MyPrelude (from the NumericPrelude library) and the species library: :m +MyPrelude Math.Combinatorics.Species.)

Species sum

And what about species addition? Addition just corresponds to disjoint (i.e. tagged) union: an -structure is either an -structure or a -structure, along with a tag so you know which it is. If you have -structures and -structures, then you have -structures.


> take 10 $ labelled lists
[1,1,2,6,24,120,720,5040,40320,362880]
> take 10 $ labelled octopi
[0,1,3,14,90,744,7560,91440,1285200,20603520]
> take 10 $ labelled (lists + octopi)
[1,2,5,20,114,864,8280,96480,1325520,20966400]
> generate (lists + octopi) ([1,2] :: [Int])
[inl([1,2]),inl([2,1]),inr(<[1,2]>),inr(<[2,1]>),
inr(<[1],[2]>)]


Do you see why the species is the identity element for species sum? If you have a structure of the species , it must be either a -structure, or an -structure: but there are no -structures! Now, you may complain that is not really an identity, since the addition still introduces an extra tag:


> generate subsets ([1..3] :: [Int])
[{1,2,3},{1,2},{1,3},{1},{2,3},{2},{3},{}]
> generate (0 + subsets) ([1..3] :: [Int])
[inr({1,2,3}),inr({1,2}),inr({1,3}),inr({1}),
inr({2,3}),inr({2}),inr({3}),inr({})]


That’s true, but we really only care about species identity up to isomorphism, and the species , , and are clearly all isomorphic for any species , even if they are not identical.

1

The Algebra.Differential.C constraint also implies a Algebra.Ring.C constraint, which requires a multiplication operation (*) and identity element 1.

So, what is the species ? It puts a singleton structure on the empty set of labels, but no structures on any nonempty label sets:

The species 1


> take 10 $ labelled 1
[1,0,0,0,0,0,0,0,0,0]
> take 10 $ unlabelled 1
[1,0,0,0,0,0,0,0,0,0]
> generate 1 ([] :: [Int])
[1]
> generate 1 ([1..3] :: [Int])
[]


So you can see that on the empty set, generates a single structure which is also called 1 (although it could be called anything, really).

Species product

And species product? An -structure on a set of labels is a pair consisting of an -structure on a subset of the labels, and a -structure on whatever labels are left over. In other words, to form all -structures on a set of labels , we first partition into an ordered pair of subsets in all possible ways, and for each pair, take all possible combinations of an -structure on the first subset, and a -structure on the second subset. For example:


> generate (list * list) ([1..3] :: [Int])
[([1,2,3],[]),([1,3,2],[]),([2,1,3],[]),([2,3,1],[]),([3,1,2],[]),([3,2,1],[]),([1,2],[3]),([2,1],[3]),([1,3],[2]),([3,1],[2]),([1],[2,3]),([1],[3,2]),([2,3],[1]),([3,2],[1]),([2],[1,3]),([2],[3,1]),([3],[1,2]),([3],[2,1]),([],[1,2,3]),([],[1,3,2]),([],[2,1,3]),([],[2,3,1]),([],[3,1,2]),([],[3,2,1])]


Can you see why is the identity element for this operation? The only partition of the label set that will produce any -structures is : in any other case, produces no structures. But a -structure paired with an -structure on is really just an -structure on , since there is only one -structure.

As an exercise, can you figure out what the species , , … ought to be?

I think I’ll stop there for now. In my next post, I’ll talk about the other primitive species in the Species type class: singletons, sets, and cycles.

New Haskell diagrams library

For the past week or so I’ve been working on an embedded domain-specific language for rendering simple diagrams with Haskell, and I’m excited to actually release version 0.1 today! You can now find it on Hackage. Version 0.1 is still fairly primitive, and there are a bunch more planned features, but you can already use it to create some pretty pictures. Here are a few examples.

We’ll start with a basic ‘hello world’ type diagram: a two-by-five rectangle, no frills:

module Main where
import Graphics.Rendering.Diagrams

main = renderToPng "hello.png" 100 100 (rect 2 5)

OK, not too exciting, but at least it was easy. Here’s another silly example that shows off a few more available features:

module Main where
import Graphics.Rendering.Diagrams

shapes :: Diagram
shapes = hcat [ fc blue $ circle 10
              , (fc goldenrod . lc green . lw 3 $ poly 5 10)
                ## (fc red . rotate (1/10) $ rect 4 4)
              , fc grey . lw 0 . scaleY 3 $ circle 5
              ]

main = renderToPng "shapes.png" 200 200 shapes

Hopefully, this example is fairly self-explanatory. We can alter the appearance of diagrams by applying functions to them like fc (fill color), lc (line color), lw (line width), rotate, and scaleY. We can superimpose two diagrams with ##. And we can lay out a list of diagrams horizontally with hcat. There are many other combinators along similar lines, with various options for distributing and aligning subdiagrams.

Now for a couple cooler examples. How about a Sierpinski triangle?

module Main where

import Graphics.Rendering.Diagrams
import Graphics.Rendering.Diagrams.Types

import qualified Graphics.Rendering.Cairo as C
import Graphics.Rendering.Diagrams.Shapes (draw)

data EqTri = EqTri  deriving Show
instance ShapeClass EqTri where
  shapeSize _   = (2, sqrt 3)
  renderShape _ = do
    c $ C.moveTo 1 s
    c $ C.lineTo 0 (-s)
    c $ C.lineTo (-1) s
    c $ C.closePath
    draw
   where s = sqrt 3 / 2

sierpinski :: Int -> Diagram
sierpinski 0 = fc black $ lw 0 $
               shape EqTri
sierpinski n = vcatA hcenter [         s
                             ,      s <> s]
  where s = sierpinski (n-1)

main = renderToPng "sierpinski.png" 300 300 (sierpinski 6)

This example illustrates a couple key points. One is that the library is easy to extend with new shapes. The built-in poly function is too general to provide a nice equilateral triangle for use in making a sierpinski triangle (its bounding box is too large, which would lead to ugly spaces in the diagram), so we can define our own shape just by making an instance of ShapeClass, and using the Cairo library to draw a path defining the shape. This is probably not the best way to accomplish this particular task — future versions of the diagrams library will include easier ways — but it’s a nice example of how easy it is to extend the basic library functionality.

The other key point is how much power we get for free from the fact that this is an embedded DSL. We can use the full power of Haskell to define a recursive function for computing sierpinski triangle diagrams.

For a final example, here are some nice Ford circles:

module Main where

import Graphics.Rendering.Diagrams

import Data.Ratio
import System.Random

(<+>) :: Rational -> Rational -> Rational
r1 <+> r2 = (numerator r1 + numerator r2) % (denominator r1 + denominator r2)

farey :: Integer -> [Rational]
farey 0 = [0%1, 1%1]
farey n = insertMediants (farey (n-1))

insertMediants :: [Rational] -> [Rational]
insertMediants [] = []
insertMediants [x] = [x]
insertMediants (x:y:zs) = x : (x <+> y) : insertMediants (y:zs)

fordCircles :: Integer -> [Diagram]
fordCircles n = map toCircle (filter ((<= n) . denominator) $ farey n)

toCircle r = translateX r' $
             circle (1 / (2 * d'^2))
  where r' = fromRational r
        d' = fromIntegral (denominator r)

dia :: [Color] -> Diagram
dia colors = view (0,-1/2) (1,0) $
             unionA hcenter bottom $
             zipWith fc colors (fordCircles 20)

randomColors :: [Double] -> [Color]
randomColors (r:g:b:ds) = rgb r g b : randomColors ds

main :: IO ()
main = do
  g <- newStdGen
  let rs = randoms g
  renderToPng "ford.png" 400 205 (dia $ randomColors rs)

Plans for future versions of the library include:

• text objects
• settable backgrounds and better support for transparency
• support for line join style and dashing
• more primitive shapes: special triangles, ellipses, bezier curves, lines, arrows…
• more layouts: grid, tree, circle…
• constraint-based placement of objects, e.g. to connect diagrams with arrows
• more output modes: ps, svg, pdf
• and more!

If this looks interesting to you, I hope you’ll download the library and play around with it! (Note that it does require the Cairo bindings, which are packaged as part of gtk2hs, which is unfortunately not yet Cabalized.) I would be happy to receive any and all feedback, including feature suggestions, bug reports, and pretty pictures. If you’re interested in contributing code, the darcs repository can be found at http://code.haskell.org/diagrams/.

Enjoy!