Functional Programming with Graphs

Project Description

Taking an inductive view of graphs facilitates the recursive definition of graph algorithms. One advantage of this approach over others is that the design of algorithms can proceed in a more declarative fashion; in particular, we do not have to care about node markings that are inherent in the imperative style of graph algorithms and that complicate the reasoning about programs considerably. The convenient formulation of recursive graph algorithms builds on a special kind of pattern matching that allows to extract particular representations from an abstract data type.

Related Publications

Inductive Graphs and Functional Graph Algorithms, Martin Erwig
Journal of Functional Programming Vol. 11, No. 5, 467-492, 2001

Pattern Guards and Transformational Patterns, Martin Erwig and Simon Peyton Jones
Electronic Notes in Theoretical Computer Science, Vol. 41, No. 1, 12.1-12.27, 2001

Fully Persistent Graphs - Which One to Choose?, Martin Erwig
9th Int. Workshop on Implementation of Functional Languages, LNCS 1467, 123-140, 1997

Functional Programming with Graphs, Martin Erwig
2nd ACM SIGPLAN Int. Conf. on Functional Programming, 52-65, 1997

Active Patterns, Martin Erwig
8th Int. Workshop on Implementation of Functional Languages, LNCS 1268, 21-40, 1996

Graph Algorithms = Iteration + Data Structures? The Structure of Graph Algorithms and a Corresponding Style of Programming, Martin Erwig
18th Int. Workshop on Graph Theoretic Concepts in Computer Science, LNCS 657, 277-292, 1992

Software

Participating Researchers