Typeclassopedia v2: moving my efforts to the Haskell wiki

I said back in April that I was going to be working on a second edition of the Typeclassopedia. Since then I have worked on it some, but mostly I’ve dithered trying to work out a toolchain for publishing it in multiple formats including PDF and (commentable) HTML. But it’s become increasingly clear to me that this is really just getting in the way of the important work of actually updating the content, and I ought to just choose a simple solution, imperfect though it may be, and get on with it.

In the meantime, it turns out that Henk Krauss (geheimdienst) has been doing the tedious work of porting the Typeclassopedia to the Haskell wiki (thanks!). It looks much nicer than I thought possible for a wiki page, allaying one particular misgiving I had about publishing in wiki format. And this format obviously makes it extremely easy for others to contribute.

The path forward is clear: I hereby declare that the Haskell wiki version of the Typeclassopedia is now the official version, and from now on I will be focusing my efforts there. You can expect a bunch of updates, improvements, and expansions over the next few months. If you have any improvements to suggest, you can make them directly, or leave a comment on the talk page.

Modern art with diagrams: the face of progress

As an addendum to my previous post, here are a few outputs generated while I was debugging:

For extra credit, deduce what the bugs were. ;)

Generating plane tilings with diagrams

I’ve finally set up a diagrams-contrib package to serve as a home for user contributions to the diagrams project—generation of specialized diagrams, fun or instructive examples, half-baked ideas, stuff which is not sufficiently polished or general to go in the diagrams-lib package but is nonetheless worth sharing.

As the first “contribution” I put some code I wrote for fun that generates tilings of the Euclidean plane by regular polygons.

So how does it work? I’m sure there are more clever ways if you understand the mathematics better; but essentially it does a depth-first search along the edge graph, stopping when it reaches some user-defined limit, and drawing polygons and edges along the way. This sounds quite simple on the face of it; but there are two nontrivial problems to be worked out:

1. How can we tell whether we’ve visited a given vertex before?
2. How do we represent a tiling in a way that lets us easily traverse its edge graph?

The first question is really a question of representation: how do we represent vertices in such a way that we can decide their equality? Representing them with a pair of floating point coordinates does not work: taking two different paths to a vertex will surely result in slightly different coordinates due to floating point error. Another idea is to represent vertices by the path taken to reach them, but now we have to deal with the thorny problem of deciding when two paths are equivalent.

But it turns out we can do something a bit more clever. The only regular polygons that can appear in plane tilings are triangles, squares, hexagons, octagons, and dodecagons. If you remember your high school trigonometry, these all have “special” angles whose sines and cosines can be represented exactly using square roots. It suffices to work in , that is, the ring of rational numbers adjoined with and . Put simply, we use quadruples of rational numbers which represent the real number . Now we can represent vertices exactly, so remembering which we’ve already visited is easy.

The other question is how to represent tilings. I chose to use this “zipper-like” representation:

data Tiling = Tiling [TilingPoly] (Int -> Tiling)

Intuitively, a Tiling tells us what polygons surround the current vertex (ordered counterclockwise from the edge along which we entered the vertex), as well as what configurations we can reach by following edges out of the current vertex. Thanks to laziness and knot-tying, we can easily define infinite tilings, such as

t4 :: Tiling
t4 = Tiling (replicate 4 Square) (const t4)

This is a particularly simple example, but the principle is the same. You can look at the source for more complex examples.

Of course, this doesn’t really show off the capabilities of diagrams much (you can draw regular polygons with any old graphics library), but it sure was fun!

Wanted GHC feature: warn about unused constraints

Consider the following function:

foo :: (Show a, Ord a) => a -> a -> String
foo x y = show x ++ show y

Currently (as of GHC 7.2.1) when compiling this code with -Wall, no warnings are generated. But I’d really love to get a warning like

Foo.hs:1:1: Warning: Unused constraint: Ord a

I see no theoretical impediments here. At the level of fully desugared and elaborated GHC core, it is no harder to tell which constraints are unused than which arguments are unused, because constraints are arguments.

One possible objection is that there is some inherent ambiguity here. For example, consider:

bar :: (Eq a, Ord a) => a -> a -> String
bar x y | x == y    = "yay"
        | otherwise = "boo"

When elaborating bar, GHC has a free choice of where to get the needed (==) method: from the Eq constraint or from the Eq superclass of the Ord constraint. So we might get a warning about Eq being redundant or about Ord being redundant, depending on which one it decides to use. But I don’t see this as a big problem.

I think this could make for a nice project for someone wanting to dig into hacking on GHC. Perhaps I’ll do it myself at some point if no one else takes it on.