Graphs à la carte

I received an overwhelming response to the introductory blog post about the algebra of graphs; thank you all for your remarks, questions and suggestions! In the second part of the series I will show that the algebra is not restricted only to directed graphs, but can be extended to axiomatically represent undirected graphs, reachability and dependency graphs (i.e. preorders and partial orders), their various combinations, and even hypergraphs.

Update: This series of blog posts was published as a functional pearl at the Haskell Symposium 2017.

Continue reading Graphs à la carte

An algebra of graphs

Graph theory is my favourite topic in mathematics and computing science and in this blog post I’ll introduce an algebra of graphs that I’ve been working on for a while. The algebra has become my go-to tool for manipulating graphs and I hope you will find it useful too.

The roots of this work can be traced back to my CONCUR’09 conference submission that was rightly rejected. I subsequently published a few application-specific papers gradually improving my understanding of the algebra. The most comprehensive description can be found in ACM TECS (a preprint is available here). Here I’ll give a general introduction to the simplest version of the algebra of graphs and show how it can be implemented in Haskell.

Update: This series of blog posts was published as a functional pearl at the Haskell Symposium 2017.

Continue reading An algebra of graphs

Towards Cloud Build Systems with Dynamic Dependency Graphs

I’ve recently submitted an application to the Royal Society Industry Fellowship scheme, aiming to continue my journey into the world of build systems. Below is the technical section, which I think is worth sharing regardless of the outcome of my application. I’d like to thank Neil Mitchell, Simon Peyton Jones, Simon Marlow and Nick Benton for many enlightening discussions on build systems that helped me understand both the problem and possible approaches to solving it.

Continue reading Towards Cloud Build Systems with Dynamic Dependency Graphs

Build GHC on Windows using Hadrian and Stack

To build GHC on Windows you usually need to jump through a lot of hoops, which may be confusing even for experienced GHC developers.

Hadrian to the rescue!

Hadrian, a new build system for GHC that I’ve been developing, is written in Haskell and can therefore be built and run via Stack that can install appropriate bootstrapping GHC and MSYS2 environment in an automated and robust way. This was first pointed out by Neil Mitchell, and I’ve recently simplified build instructions even further. The latest version of the instructions is maintained here.

Continue reading Build GHC on Windows using Hadrian and Stack

Walking on trees

Yesterday I learned a cool algorithm, which can be intuitively described as follows:

Pick a starting node, walk as far as you can, turn around, and walk as far as you can again.

Doesn’t sound too complicated, right? But it actually solves a non-trivial problem: it finds the diameter of a tree in linear computation time. The diameter of a tree is the length of the longest possible walk on it. For example, the tree below has diameter 8, because the longest walk on it goes through 8 links. There are actually three walks of length 8, we show the one between nodes p and q:

Tree diameter

Continue reading Walking on trees

Fibonacci concat primes

A Fibonacci concat prime is a prime number obtained by concatenating several first elements of the Fibonacci sequence (1, 1, 2, 3, 5, 8, 13, …). These numbers showed up in Evelyn Lamb’s tweet and got me interested, especially since I wanted to play with primality testing of big numbers in Haskell. (‘Fibonacci concat prime’ is a completely made up name; shout if you know the right one!)

Known trivial examples:

  • 11 = 1 • 1
  • 1123 = 1 • 1 • 2 • 3

I got curious if there were any other Fibonacci concat primes and wrote a generator in Haskell using this implementation of Miller-Rabin primality test.

Continue reading Fibonacci concat primes

Shaking up GHC

As part of my 6-month research secondment to Microsoft Research in Cambridge I am taking up the challenge of migrating the current GHC build system based on standard make into a new and (hopefully) better one based on Shake. If you are curious about the project you can find more details on the wiki page.

During this week I’ve been trying to wrap my head around the current build system and so far I’ve felt rather intimidated by the scale of this undertaking. Yet I am optimistic because I’m helped by several much smarter people 🙂 If you are a Haskell fan and would like to help make GHC better, please join this team effort!

Continue reading Shaking up GHC

Inverting the universe with two inverters

Recently I came across an interesting puzzle from MIT Tech Review March/April 2013:

Howard Cohen has plenty of AND and OR gates but just two inverters. How can he invert three signals a, b, and c?

More generally, he wonders if the ratio I/S can ever be less than 2/3, where I is the number of inverters and S is the number of signals to invert (once again, unlimited AND and OR gates are available).

I couldn’t quickly solve the first part of the puzzle with a pen and paper, so I decided to write a brute force solver. And to make it a bit more fun I did it in Haskell (any suggestions for improving the code are welcome, by the way!).

Continue reading Inverting the universe with two inverters