### begriffs

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?
• 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