The random graph

Today in my finite model theory class we learned about the Rado graph, which is a graph (unique up to isomorphism among countable graphs) with the extension property: given any two disjoint finite sets of vertices and , there exists some other vertex which is adjacent to every vertex in and none of the vertices in .

This graph has some rather astonishing properties. Here’s one: consider starting with vertices and picking each edge with probability . Clearly, there are different graphs you can get, each with equal probability; this defines a uniform random distribution over simple graphs with vertices. What if you start with a countably infinite number of vertices instead? The surprising answer is that with probability 1 you get the Rado graph. Yes indeed, the Rado graph is extremely random. It is so random that it is also called “THE random graph”.

SimpleGraph getRandomGraph()
{
    return radoGraph;  // chosen by fair coin flips.
                       // guaranteed to be random.
}

(See http://xkcd.com/221/.)

How to solve this differential equation?

How would you solve the differential equation

with the initial condition ? I know what the answer is supposed to be, but I don’t know how to directly solve it.

In case you’re wondering, is the exponential generating function for the Bell numbers, which count set partitions. The differential equation in question arises from noting that

(to make a partition of , you can put anywhere from to elements in the same set with ; there are ways to choose the elements to include, and ways to partition the rest).

Mgu’s and universal properties

Warning, poorly-explained categorical rambling follows…

The most general unifier (mgu) of two expressions and is a substitution for which , such that every other substitution for which can be expressed as for some . For example, the most general unifier of and is .

Now, I’d seen this definition before. But just yesterday I realized what a similar flavor it has to certain other definitions in mathematics. For example:

The greatest common divisor of two natural numbers and is a natural number which evenly divides both and , such that every other common divisor of and is also a divisor of .

See the similarity? Now, I’ve studied enough category theory to know that this is an example of a “universal property”. gcd in particular is the meet operation in the divisor poset, and meets are just products in a poset category… so, naturally, I wondered whether mgu’s could also be formalized as a particular universal construction in some category. After some fiddling around, I figured out that yes, mgu’s can be thought of as coequalizers in a category of substitutions (which I guess is sort of like the Kleisli category of the free monad on the structure functor for whatever term algebra you are using?). A Google search for “mgu coequalizer” seems to suggest that I am right! I’m rather pleased that I came up with this on my own. Anyone know of a link to where this was first discussed?

Collecting attributes

I’m proceeding with the redesign of my diagrams library slowly but surely. I don’t have a lot of time to work on it, hence the “slowly”. But progress is being made. It’s still very much in the design phase, which makes it difficult for others to help, but Lennart has created a diagrams page on the Haskell wiki which I hope can be a good way to have an open design process and get input from the community. There’s a lot of stuff I have written down that I haven’t gotten around to putting on that page yet, but I hope to do that soon.

Occasionally I plan to write some blog posts about interesting issues that arise in the design; today is the first.

Here’s the background: a diagram is essentially a tree of sub-diagrams (although there will be a principled way to refer to subdiagrams in other parts of the tree; more on this in a future post), with leaves corresponding to atomic primitives. Every node in the tree can (optionally) have some associated style attributes, such as stroke width and color, fill color, font, and other such things. When we encounter a primitive at a leaf, how do we know what attributes to use when rendering it? It may have some associated attributes, but its parent node might also have some associated attributes, and other ancestor nodes higher up the tree might have attributes as well.

What we’d really like to do is have a Style data type which has a Monoid instance:

data Style = Style { strokeWidth :: Double
                   , strokeColour :: Colour
                   ... }

instance Monoid Style where
  ...

Then to determine the style to use for a leaf, we just combine the styles of all its ancestors using the monoid.

So, how to implement this Monoid instance? Well, first of all, what I wrote above is slightly bogus; at the very least each particular attribute ought to be optional, so it should look something more like this:

data Style = Style { strokeWidth :: Maybe Double
                   , strokeColour :: Maybe Colour
                   ... }

To combine two Style records, we match them up field-by-field, and Just trumps Nothing.

So far, so good. But how do we combine two fields containing Just? It seems we have two choices: we can be biased towards the top of the tree (i.e. parent attributes override child attributes) or towards the bottom (i.e. child attributes override parent attributes). Indeed, Data.Monoid contains two newtypes, First and Last, whose Monoid instances exhibit exactly this behavior.

But here’s the problem: in this application, one of these choices isn’t obviously better than the other. In fact, it’s easy to imagine situations where each would be the desired behavior. For example, imagine that we have created a subdiagram that we want to use many times throughout a larger diagram. Most of the time it will be blue, so it makes sense to specify that attribute as part of the subdiagram itself. However, in one place we want it to be red, so we’d like to be able to override its attributes with parent attributes. On the other hand, imagine a situation where a diagram is going to be composed of many different subdiagrams, which all share the property that they are blue. To avoid repeating ourselves, it makes sense to specify “blueness” as an attribute of the parent diagram and have all the subdiagrams inherit it. However, one subdiagram should be red, so we’d like to be able to override the parent attribute in this particular child.

What to do? A first cut might look something like this:

data Override a = Default | OverrideUp a | OverrideDown a

data Style = Style { strokeWidth :: Override Double
                   , strokeColour :: Override Colour
                   ... }

The intention is that OverrideUp a overrides any attributes above/before it, and OverrideDown a overrides any attributes below/after it. However, there’s a problem: what should

(OverrideDown a) `mappend` (OverrideUp b)

be? The OverrideDown a claims to override the OverrideUp b… and vice versa! So this doesn’t really work. We need a way to specify relative priorities. So, another solution would just be to assign each attribute with a priority:

data Prioritized a = Default | Priority Double a

data Style = Style { strokeWidth :: Prioritized Double
                   , strokeColour :: Prioritized Colour
                   ... }

For the Monoid instance, we just take the value with maximum priority. This allows us to do what we wanted—overriding parent or child attributes is done simply by assigning a higher priority. However, I really dislike this solution. Having to specify a priority is annoying—but not only that, figuring out what priority to use to achieve your desired effect requires global knowledge about the value of the priorities used elsewhere. One improvement we could make is to adopt the solution used by CSS: attributes are leaf-biased by default, but assigning a priority can override this. That is,

data Prioritized a = Default | Priority (Maybe Double) a

where the Monoid instance chooses the value with the highest priority, or the right/leaf-most value if no priorities are specified. This might be the best option—but it’s still somewhat unsatisfactory.

I wonder about a solution that allows you to say, “I want to override the attribute on THAT node”—where “THAT” represents some way to refer to a particular node by name (what these names look like will be the subject of another post). This might solve the problem of arbitrariness with the numerical priorities, but might also be veering into the realm of the overengineered…

Typeclassopedia in Japanese!

Satoshi Nakamura has published a Japanese translation of the Typeclassopedia. I don’t read any Japanese, but it sure looks cool, and I hope this will be a great resource for Japanese learners of Haskell. A big thank you to Satoshi for his hard work; the Typeclassopedia is certainly not short!

Call for submissions: Monad.Reader issue 15

I’m excited to be taking over the editorship of the Monad.Reader. I’ll be putting together Issue 15 in January—the deadline for submissions will be January 8, 2010. Please consider writing something! You don’t need to be an expert; past articles have included things like tutorials, book reviews, new ideas, beginner perspectives, illustrations of nifty code, explanations of a new library or piece of software… Collaboration is encouraged, too. Have a great idea for an article but not sure you could pull it off for one reason or another? Send an email to haskell-cafe@haskell.org asking for a coauthor. Writing an article is a great way to learn and to create a high-quality resource for others learning FP.

If you plan to write something—or are considering it—let me know. Submission guidelines can be found on the Monad.Reader website.

diagrams 0.2.1, and future plans

First of all, I’ve just released version 0.2.1 of the Haskell diagrams library. This is a minor release which fixes a few bugs and adds a few new combinators, most notably a grid layout combinator contributed by Ganesh Sittampalam. For more information and a full list of the features new to 0.2.1, see the diagrams web page.

The real reason for the release, however, is to get existing new features out the door before gearing up for a planned major rewrite of the backend to use a constraint-solving layout engine. This will allow for much greater elegance and flexibility, as well as a number of features (such as arrows connecting different parts of the diagram) which would be difficult or impossible to implement in the current framework.

My ultimate vision is for the diagrams library to become a viable alternative to declarative drawing systems such as MetaPost and Asymptote, with the distinct advantages that it will be

• purely declarative, and
• an embedded DSL, providing the full power of Haskell and its ecosystem, as opposed to the ad-hoc specialized languages used by MetaPost and Asymptote.

If this sounds exciting to you, I hope you’ll join me, either by trying out diagrams for your projects and providing feedback, or by contributing some code. If you’re interested in helping with the rewrite itself, let me know; I also plan to set up a core/contrib model like that of xmonad, so there should also be plenty of opportunities for contributing independent add-on modules which enhance the core functionality.

Functional MetaPost

I just spent a very frustrating hour trying to get the functional MetaPost library (a Haskell DSL for generating MetaPost) working. It installs (via cabal-install) without a hitch, but I haven’t been able to get it to actually work. I can write a test program which imports the FMP module, and compile it, but then when I try to run it, it spews out a gazillion .log, .tmp, .mpx, .aux… files and a nasty-looking series of error messages (including a segfault). I’m happy to provide more details if anyone thinks they would actually be able to help…

All the more motivation to get back to a rewrite of my diagrams library…

Edinburgh

I’m having a great time in Edinburgh so far! I’m currently at Heriot-Watt University for the International Summer School on Advances in Programming Languages, learning some interesting things but more importantly meeting interesting people. I’m also looking forward to meeting yet more interesting people at Hac7 and at ICFP (if you’re reading this and plan to be at either, then you are one of them).

Here are a few pictures I took while sight-seeing on my first day; some pictures of the summer school itself will follow soon.

New 2D text layout library

I’ve just uploaded to Hackage a small library, boxes, for 2D text layout/pretty-printing. This is something I’ve wanted a couple times and have heard others ask for—Text.PrettyPrint.HughesPJ, as nice as it is, is intended for pretty-printing only linear output (such as source code), and is ill-suited for layout of a two-dimensional nature, such as columns of text, proof trees, and the like.

I wrote this library almost a year ago and have been sitting on it ever since, and finally decided that I really ought to just release what I have so others can make use of it. It’s quite usable as it is, and has (I hope) solid documentation. There’s nothing in the way of examples or tutorials or QuickCheck properties, and there are many more features one could imagine adding to it, but it’s simply not a priority for me right now, so it is what it is. However, if anyone is interested in taking over as maintainer and extending it, be my guest! Just fork off a new darcs repo and hack away.