Diagrams internals

This article covers a small part of the internals of Diagrams, a Haskell library for drawing static and animated diagrams. In particular, I give an overview of how a diagram is represented, how paths work, and how attributes are applied to diagrams. The Diagrams library has a lot in it, so not everything can be covered in great detail in such a short article.

Understanding the internals of Diagrams is not necessary for using it effectively – you can make complex diagrams without knowing any of how it works. You might be interested in the internals if you want to extend the library, or add a new rendering backend, or just fix a bug or add documentation. This material might also be of interest to people who want to see examples of type classes, existential types and heterogeneous lists.

Example

Throughout we’ll have a running example:

d :: Diagram SVG R2
d = unitSquare # fc red # clipBy (circle 0.3)

go = writeFile "example.svg" $ renderSvg $
       renderDia SVG (SVGOptions (Width 200)) d

Let’s ignore the renderSvg and writeFile parts, because they are just for producing the SVG format after the diagram has been rendered. For brevity’s sake let’s ignore renderDia, and concentrate on the diagram itself.

d = unitSquare # fc red # clipBy (circle 0.3)

The unit square is defined as a 4-sided polygon with radius sqrt(2)/2, oriented along the X-axis.

unitSquare = polygon with { polyType   = PolyRegular 4 (sqrt 2 / 2)
                          , polyOrient = OrientH }

This polygon ends up being defined as a closed path of straight lines between the corners of the square at points (±0.5, ±0.5).

Paths, trails and segments

To understand how this is represented, we need some Diagrams terminology. A “segment” is either a straight line or a Bézier curve, and doesn’t have any fixed position in space, which means translating a segment has no effect. A “trail” is a sequence of segments connected end-to-end. These still don’t have any fixed position, so can’t be translated. Trails can be open or closed. Finally, a “path” is a list of trails, plus a starting point for each trail. Because each trail in a path is fixed in some position, a path can be translated and one path can be placed on top of another.

So, our polygon above is a path with a single trail. The trail’s starting point is (0.5, -0.5), and the trail has three straight-line segments, defined by the vectors (0,1), (-1,0) and (0,-1). The trail is closed, so there is an implicit connection from the end of the trail back to the starting point.

Because it is being passed to renderDia, and the fc and clipBy modifications don’t alter its type, unitSquare must have the type Diagram b v. In this case, the backend b will be SVG and the vector space v will be R2. A diagram can be made from a path via the stroke function.

stroke and its friend stroke' deal with several things we’re not going to consider here: envelopes, traces, names and queries. For our purposes, all stroke does is wrap the path in a Prim type, and pass it mkQD, which makes a diagram from a single primitive.

Diagram representation

The basic diagram type QDiagram is a wrapper around a DUAL tree. A DUAL tree is an n-ary tree with data at the leaves and annotations that travel either up or down the tree. (A DUAL tree can also have data in the internal nodes, but Diagrams currently doesn’t use this feature.) For Diagrams, the primitives are the leaf data, transformations and styles are the downwards-travelling annotations, and envelopes, traces, names and queries are the upwards-travelling annotations. Here we will only concern ourselves with the leaves and the down-annotations, the L and D in DUAL.

Because all we have is a primitive – our path – we have only some leaf data and no annotations. The path is passed to the leaf function, which makes a leaf node. Now we have a diagram (tree) which consists of a single primitive (leaf node).

Attributes and styles

Now that we have a diagram, let’s consider next unitSquare # fc red. fc is defined, via fillColor as:

fillColor :: (Color c, HasStyle a) => c -> a -> a
fc = fillColor = applyAttr . FillColor . Last . SomeColor

Because Diagram is a member of the HasStyle type class, you can read the type informally as c -> Diagram -> Diagram. SomeColor is a wrapper that contains a value whose type is a member of the Color type class. The Last semigroup just keeps the “last” value: Last a <> Last b <> Last c == Last c. Finally, FillColor is a wrapper indicating which attribute we’re setting.

applyAttr is defined like this:

applyAttr :: (AttributeClass a, HasStyle d) => a -> d -> d
applyAttr = applyStyle . attrToStyle

attrToStyle converts an attribute into a Style. A Style is a container for carrying several attributes together: a Style value is just a Map from Strings to Attribute values:

newtype Style v = Style (M.Map String (Attribute v))

where an Attribute value is of some type in the AttributeClass type class – in this case, that type is FillColor. Let’s look at the definition of attrToStyle:

attrToStyle :: forall a v. AttributeClass a => a -> Style v
attrToStyle a =
  Style (M.singleton (show . typeOf $ (undefined :: a)) (mkAttr a))

The argument a is something like FillColor (Last (SomeColor red)). Starting from the left, you can see we are making a new Style value of a map containing a single key-value pair. The key is a string representation of whatever type a has – in this example it’s FillColor. The value part is a itself, wrapped up in type Attribute.

Note that there are two kinds of Attribute: transformable and non-transformable. FillColor is one of the non-transformable kind: transformations like scaling and translation don’t affect a diagram’s fill colour.

Now the style we have created needs to be applied to the diagram. The instance of HasStyle for a diagram defines applyStyle like this:

applyStyle =
    over QD . D.applyD . inj
    . (inR :: Style v -> Split (Transformation v) :+: Style v)

Intuitively, we know that applying a style to a diagram must somehow insert the style into the diagram tree as a down-annotation. The type of a down-annotation is:

type DownAnnots v = (Split (Transformation v) :+: Style v)
                ::: Name
                ::: ()

This is a heterogeneous list – you can think of ::: as a cons, like :, but at the type level. The Transformation type represents an affine transformation. The Split type is just like a regular monoid, but allows us to split the accumulated values into two halves. In Diagrams, this is used to separate the transformations into the frozen and unfrozen transformations. The :+: operator represents a monoid coproduct – we will skip the details, but here it means that we have an interleaving of the transformation pairs with style values, and every transformation acts on all the styles that follow it.

The definition of applyStyle can be read as: take the style, put it the right part of the coproduct (inR), put that into a DownAnnots value (inj), and insert the the DownAnnots value into the tree at the root (D.applyD). The “over QD” part just means to do all this inside the QD wrapper around the tree.

Let’s now apply the clipBy attribute.

unitSquare # fc red # clipBy (circle 0.3)

This is like the fill colour attribute, except the clip path is transformable. A circle is a like a unitSquare, except instead of being a path made of straight lines, it’s a path made of curves. The clipping attribute means that the only part of the square that will be shown is whatever overlaps with the circle. In this case, it’s like looking at the square through a circle-shaped hole.

Conclusion

Here I’ve only scratched the surface of Diagrams. If you want to learn more, the source code is easy to read once you’ve learned your way around the types and modules.


Christopher Mears, 18 November 2012