Inductive graph algorithms

Here's a paper describing a very elegant view of graphs as an inductive (aka recursive) datatype.

Inductive datatypes essentially define a data structure as 1) a simple base case, and 2) a recursive case that composes the data structure with one additional unit of complexity. In the case of graphs, the base case is the empty graph, and the recursive case adds one new node to an existing graph.

This is very elegant because it lets functional languages define algorithms over graphs as easily as they define algorithms over lists, using primitive recursion. The resulting algorithms are quite straightforward and readable.

Unfortunately the paper doesn't do as good a job when it comes to the runtime efficiency is of the resulting data structure. It does explore the big-O efficiency of various alternatives, but unlike this paper, it doesn't report any empirical measurements. This makes me somewhat suspicious of using it in real "production-worthy" code.