Aidan Delaney’s weblog

I use Inkscape a lot. Particularly for drawing diagrams for my research. I use the TexText plugin for Inkscape to allow me to embed arbitrary LaTeX in documents. However, recently I’ve had an issue with it.

TexText uses pdf2svg to convert PDFs to SVGs to embed into an Inkscape project. Under the hood it runs pdflatex on the LaTeX fragment you provide, then it converts this to an SVG with a tight bounding box. This has been generating horribly pixelated fonts for me. The output of X+y=z is the following:

Having looked into it there are two ways to solve the problem

• The quick and simple way is to \usepackage{lmodern} at the top of your LaTeX preamble input to TexText – this forces latex to use type1 (scalable) fonts as opposed to type3 (bitmap) fonts.
• The longer term way is to maintain textext for our research group to use. This will involve dropping all backends other than the pdf2svg one. Simply for the reason that I have neither the resources nor inclination to support multiple backends. Each supported backend is a deep mine of bugs and I’m comfortable with the pdf2svg/poppler/cairo mine.

I do wonder though, why LaTeX prefers type3 fonts over their type1 brethren.

Lets suppose you’ve got two similar recursive types that differ only in their “payload”. For example, you want a binary tree of boolean operations to store a Char and another similar tree to store a set of Char. Let’s call them Tree and STree. Something like in the following, non-working, code

data Tree = And Tree Tree
  | Or Tree Tree
  | Leaf Char

data STree = And STree STree
  | Or STree STree
  | Leaf (Set Char)

We’re repeating a lot of boiler plate here. It’d be great if I could parameterise the tree, which I can.

data MTree t = And (MTree t) (MTree t)
  | Or (MTree t) (MTree t)
  | Leaf t

This is great, it removes boilerplate, and gives me less code to test.

Take our Tree as defined above. It’s easy to create an Arbitrary Tree. The following code creates an arbitrary tree with a maximum branch depth (generally for efficiency reasons you don’t want test trees that are either (arbitrary :: Int) or infinitely deep)

import Test.QuickCheck
import Control.Monad

data Tree = And Tree Tree
  | Or Tree Tree
  | Leaf Char
  deriving Show

arbitraryTree :: Int -> Gen Tree
arbitraryTree 0        =
  do
    c <- arbitrary
    return (Leaf c)
arbitraryTree maxDepth =
  do
    t <- oneof [arbitraryTree 0,
                liftM2 And (arbitraryTree depth') (arbitraryTree depth'),
                liftM2 Or (arbitraryTree depth') (arbitraryTree depth')]
    return t
  where
    depth' = maxDepth -1

instance Arbitrary Tree where
  arbitrary = do
    maxDepth <- choose (1, 10)
    t <- arbitraryTree maxDepth
    return t

So how do you create an arbitrary MTree? The following code makes it all work.

import Test.QuickCheck
import Control.Monad

data MTree t = And (MTree t) (MTree t)
  | Or (MTree t) (MTree t)
  | Leaf t
  deriving Show

arbitraryMTree :: Arbitrary t => Int -> Gen (MTree t)
arbitraryMTree 0        =
  do
    c <- arbitrary
    return (Leaf c)
arbitraryMTree maxDepth =
  do
    tr <- oneof [arbitraryMTree 0,
                liftM2 And (arbitraryMTree depth') (arbitraryMTree depth'),
                liftM2 Or (arbitraryMTree depth') (arbitraryMTree depth')]
    return tr
  where
    depth' = maxDepth -1

instance Arbitrary t => Arbitrary (MTree t) where
  arbitrary = do
    maxDepth <- choose (1, 10)
    tr <- arbitraryMTree maxDepth
    return tr

This is remarkably neat. QuickCheck, for me, is the killer feature of functional programming!

Returning to the Squad example from the other day. We can create Arbitrary instances of Squad.

import Data.Set
import Data.List
import Test.QuickCheck
import Control.Monad

data Squad a = Squad { players :: (Set a), team :: a}

instance (Ord a, Arbitrary a) => Arbitrary (Squad a) where
  arbitrary =
    do
    ps <- listOf1 arbitrary
    t <- elements ps
    return (Squad (fromList ps) t)

But now I have a complication (and this is where the Squad metaphor breaks down, but please bare with me). Suppose I want a Squad of players where I can in some instances choose a subset of them to play, and in other instances only choose one of them to play. So the Squad still constains a set of players, but the team can sometimes be a subset of the players, and sometimes is a single player. We’ve got to allow instances of TypeSynonyms:

{-# LANGUAGE TypeSynonymInstances #-}
import Data.Set
import Data.List
import Test.QuickCheck
import Control.Monad

data Squad a b = Squad { players :: (Set a), team :: b}
type SetSquad = Squad Char (Set Char)
type SingleSquad = Squad Char Char

instance Arbitrary SetSquad where
  arbitrary =
    do
    ps <- listOf1 arbitrary
    t <- elements (subsequences ps)
    return (Squad (fromList ps) (fromList t))

instance Arbitrary SingleSquad where
  arbitrary =
    do
    ps <- listOf1 arbitrary
    t <- elements ps
    return (Squad (fromList ps) t)

Which is awesome.

Mad props to my homeboy Eric (I’ve been told that’s how one addresses a USian) for listening to my overtired ramblings last night, and for pointing me at numerous ways to implement what I wanted to.

I want to build arbitrary sized trees of Compound

data Compound = And Compound Compound
  | Or Compound Compound
  | Product Compound Compound
  | Not Compound
  | Leaf { diagram :: Unitary} deriving (Show, Eq)

However, I want to limit to a max depth, and I want to have each branch to be of an arbitrary depth.

mkBinary :: (Compound -> Compound -
> Compound) -> Int -> Gen Compound
mkBinary f depth =
  liftM2 f (mkCompound depth') (mkCompound depth')
  where
    depth' = depth -1

mkNot :: Int -> Gen Compound
mkNot depth =
  liftM Not (mkCompound (depth-1))

mkLeaf :: Gen Compound
mkLeaf = liftM Leaf arbitrary

mkCompound :: Int -> Gen Compound
mkCompound 0 = mkLeaf
mkCompound depth = oneof [mkLeaf, mkBinary And depth, mkBinary Or depth, mkBinary Product depth, mkNot depth]

instance Arbitrary Compound where
  arbitrary =
    do depth <- choose (0, 4)
       d <- mkCompound depth
       return d

QuickCheck can do it. It’s nice. Use it.

I’ve been interested in functional programming for a while. I’ve hacked up a few things. Mira and Conferenceasaurus mainly. I’m not claiming that the code is great, I’d regard myself still as a n00b. I also have an interest in software testing, to this end the QuickCheck is both interesting and awesome. However, I’ve got one significant issue with my usage of it.

The types I’m playing with should probably be implemented using a dependent type system. For example, I’ve got a lot of

data Foo = Foo {bar::Set a, quux::Set a}

where quux should be a subset of bar. I’m not using a dependent type system, just regular Haskell, so the dependence is not enforced. However, I do want to generate instances of Arbitrary Foo where quux is a random subset of bar. Randomness is where my issues lie.

I could generate a random subset of a set

import Data.Set
import Data.Maybe
import Test.QuickCheck

randSubset :: Set a -> Gen (Set a)
randSubset xs = do {
mask <- vectorOf (size xs) (arbitrary::Gen Bool);
return (fromList (catMaybes [if b then (Just e) else Nothing | e <- l, b <- mask]))
}
where
l = toList xs

However, you’ll notice that the type signature is randSubset :: Set a -> Gen (Set a) and to create quux as a random subset of bar in an Arbitrary Foo I’d need this to return a Set a. I could unGen it, however this would require picking a seed which produces the same set of pseudo-random numbers each time, or generating a random seed, in which case I’d have to return an IO (Set a).

So, question time. Is it possible to generate arbitrary instances of Foo such that the property “quux is a subset of bar” is enforced in all arbitrary instances?

update:
As arbitrary :: Gen a then arbitrary = do x <- arbitrary; y <- randSubset x; return (Foo x y) is the solution.