Functional Programming with Graphs

Posted on December 22, 2017 by Marko Dimjašević

A graph by futtetennista

Back in elementary and high school days I used to attend algorithmic problem solving competitions where one would have to implement in code solutions to given problems. At the time I knew nothing about programming paradigms and I used a paradigm that everyone else was using: imperative programming. Recently I’ve been wondering how to implement data structures and algorithms in a pure functional language such as Haskell. For example, how to do graph theory in functional programming?

I am still going through it, but there is a nice overview of graph theory data structures and algorithms for pure functional programming, (implemented in Haskell) such as adjacency lists, depth- and breath-first search, minimum spanning tree and shortest path (Dijkstra). The referenced implementations are suboptimal when it comes to running times. However, there is an optimized implementation in the Functional Graph Library.