Monday, June 4, 2012

Finding Connected Graphs in F#

I've been learning F# and functional programming.  I first got interested in functional languages when Ben Lee introduced me to Erlang at CodeMash by doing the greed kata with me.  Then I bought Programming F# and started to learn the F# language.  As I was going through the book, I was playing with a little Team City/FogBugz integration script in F#.  Then Anthony Coble told me he wanted to do a talk at Burning River Developers on Falling In Love With Haskell.  His talk was great, and Haskell looks like a mind-blowing language.

So that is how I got interested in playing with this stuff.  In order to actually learn it, and not just read about it, I've been finding and inventing little exercise problems and solving them in F#.  F# is a multiparadigm language, but I've been focusing on the pure Functional portions of the language for now.  I thought I'd share these problems and my solutions on the blog.  The best thing that could come from this is if you, dear reader, would also solve these problems in the language of your choice and share back your solution.  Or if you know F# but don't want to actually fully implement a solution to these, I'd love feedback on how you might have solved the problems differently.

The first problem I want to share is a Graph parsing problem:
Given a graph G, return a list of all the connected graphs in G: [G1, G2, ...].
Here's an example input graph and the expected output:
 The git repo with my solutions is here:

And here's the code:

Some of things I really enjoy about this code:

  • I love nesting simple little functions inside other functions to give names to boilerplate code (ex: isSeen and notSeenOnly)
  • The recursive walk method is stunningly elegant
  • "Map.ofList g" is a cool line of code.  g is a Graph record, but it's defined as a list, and so can be treated like a list.
  • List.collect combines all the returned lists into one list
  • It's also cool that the map variable is in scope inside of the walk function because it's closed over from the findConnectedGraph method.
  • The recursive list comprehension of findAllConnectedGraphsWorker totally blows my mind.  Using yield as expected, but then calling itself with yield! is crazy!
I'm sure there is a lot about this code that could be improved.  There are probably better algorithms too. I'd love to hear your ideas and read your implementations of this problem!

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.