begriffs

FP Graph Algorithms

September 4, 2015

Manipulating graphs has traditionally been seen as a place where imperative programming reigns supreme. Tikhon Jelvis begs to differ, and shows a trick where graph traversal can be expressed by a form of pattern matching. After explaining the approach he simulates how it works on a sample graph.

Summary

  • Traditionally graph algorithms are seen as one of the things that are really hard in functional programming
  • To some extent it is because the graph algorithms and representations you’ve learned have a very imperative bent
  • One insight into making a graph algorithm functional is to find a way to use pattern matching on a graph structure
    • What does this even mean?
    • Start with what we already know: pattern matching is easy on lists or trees
    • Translates to any algebraic data type really
    • But there is no algebraic data type for graphs
    • Graphs are not inductive — there is more than one way to build them up or take them apart
  • But we can pretend! We can treat graphs as if they were inductive
  • So how do we break a graph apart in a pattern match?
    • We’ll use a a “view”
    • match :: Node -> Graph -> Maybe View
  • Depth first search
    • We don’t update flags on nodes to say which we have visited
    • Our recursion just happens on a subgraph that does not re-visit nodes
    • Example of the operation on a specific graph
  • You can find the implementation in the Functional Graph Library
  • Slides for this talk are available here
  • For an example of generating mazes using functional programming, check out this blog post
  • Q&A