How do I implement graphs and graph algorithms in a functional programming language?

Question

Basically, I know how to create graph data structures and use Dijkstra's algorithm in programming languages where side effects are allowed. Typically, graph algorithms use a structure to mark certain nodes as 'visited', but this has side effects, which I'm trying to avoid.

I can think of one way to implement this in a functional language, but it basically requires passing around large amounts of state to different functions, and I'm wondering if there is a more space-efficient solution.

Intumescence

Answer 1

You might check out how Martin Erwig's Haskell functional graph library does things. For instance, its shortest-path functions are all pure, and you can see the source code for how it's implemented.

Another option, like fmark mentioned, is to use an abstraction which allows you to implement pure functions in terms of state. He mentions the State monad (which is available in both lazy and strict varieties). Another option, if you're working in the GHC Haskell compiler/interpreter (or, I think, any Haskell implementation which supports rank-2 types), another option is the ST monad, which allows you to write pure functions which deal with mutable variables internally.

Fitment

I pulled these links from the functional graph library page: This explains the theory: web.engr.oregonstate.edu/~erwig/papers/abstracts.html#JFP01 This documents the programming details: web.engr.oregonstate.edu/~erwig/fgl/haskell/old/fgl0103.pdf Together, these papers best answer my question, particulary the second one, which is a bit more practical. Thanks! – Intumescence

Answer 2

I just keep the visited set as a set and pass it as a parameter. There are efficient log-time implementations of sets of any ordered type and extra-efficient sets of integers.

To represent a graph I use adjacency lists, or I'll use a finite map that maps each node to a list of its successors. It depends what I want to do.

Rather than Abelson and Sussman, I recommend Chris Okasaki's Purely Functional Data Structures. I've linked to Chris's dissertation, but if you have the money, he expanded it into an excellent book.

---

Just for grins, here's a slightly scary reverse postorder depth-first search done in continuation-passing style in Haskell. This is straight out of the Hoopl optimizer library:

postorder_dfs_from_except :: forall block e . (NonLocal block, LabelsPtr e)
                          => LabelMap (block C C) -> e -> LabelSet -> [block C C]
postorder_dfs_from_except blocks b visited =
 vchildren (get_children b) (\acc _visited -> acc) [] visited
 where
   vnode :: block C C -> ([block C C] -> LabelSet -> a) 
                      -> ([block C C] -> LabelSet -> a)
   vnode block cont acc visited =
        if setMember id visited then
            cont acc visited
        else
            let cont' acc visited = cont (block:acc) visited in
            vchildren (get_children block) cont' acc (setInsert id     visited)
      where id = entryLabel block
   vchildren bs cont acc visited = next bs acc visited
      where next children acc visited =
                case children of []     -> cont acc visited
                                 (b:bs) -> vnode b (next bs) acc     visited
   get_children block = foldr add_id [] $ targetLabels bloc
   add_id id rst = case lookupFact id blocks of
                      Just b -> b : rst
                      Nothing -> rst

Autonomy

Answer 3

If you were using haskell, the only functional language with which I am familiar, I would recommend using the State monad. The State monad is an abstraction for a function that takes a state and returns an intermediate value and some new state value. This is considered idiomatic haskell for those situations where maintaining a large state is necessary.

It is a much nicer alternative to the naive "return state as a function result and pass it as a parameter" idiom that is emphasized in beginner functional programming tutorials. I imagine most functional programming languages have a similar construct.

Orlene

Would it be fair to describe a state monad as building up a single function piece by piece, and then applying the completed function to the state? – Droppings

@Greg: yes. Monadizing some programming idiom (in this case, read/writes on global state) is a way of turning that idiom into composable pieces. You bind the pieces together to get bigger pieces. – Sadism

Answer 4

Here is a Swift example. You might find this a bit more readable. The variables are actually descriptively named, unlike the super cryptic Haskell examples.

https://github.com/gistya/Functional-Swift-Graph

Pascia

Answer 5

I would love to hear about some really clever technique, but I think there are two fundamental approaches:

1. Modify some global state object. i.e. side-effects
2. Pass the graph as an argument to your functions with the return value being the modified graph. I assume this is your approach of "passing around large amounts of state"

That is what's done in functional programming. If the compiler/interpreter is any good, it will help manage memory for you. In particular, you'll want to make sure that you use tail recursion, if you happen to recurse in any of your functions.

Droppings

Answer 6

Most functional languages support inner functions. So you can just create your graph representation in the outermost layer and just reference it from the inner function.

This book covers it extensively http://www.amazon.com/gp/product/0262510871/ref=pd_lpo_k2_dp_sr_1?ie=UTF8&cloe_id=aa7c71b1-f0f7-4fca-8003-525e801b8d46&attrMsgId=LPWidget-A1&pf_rd_p=486539851&pf_rd_s=lpo-top-stripe-1&pf_rd_t=201&pf_rd_i=0262011530&pf_rd_m=ATVPDKIKX0DER&pf_rd_r=114DJE8K5BG75B86E1QS

Wismar