[<<][compsci][>>][..]

Sun Mar 25 13:10:56 CEST 2012

The usefulness of local state / working with graphs in Haskell

Some handwaving to follow.

I find it hard to do real work in Haskell.  Many, many algorithms take
advantage of in-place updates of data structures, moving from one
consistent configuration to another one in a (conceptually) single
step.  Often this incremental update is key to the efficiency of the
algorithm.  Creating a full duplicate of the data structure at each
algorithm step is often too expensive and probably also annoying,
since it often needs more info than a local update only.

It seems that most functional algorithms use some kind of inside-out
representation using zippers, which allows an abstraction of the
current edit point while keeping updates cheap: most of the deep
structure is reused while the only the local edit point needs a new
construction.

So let's dig into this a bit deeper.  Given a generic graph structure,
how to practically represent it in Haskell?

Google gives me this[1].  It describes how to work with graphs,
focusing on the operations: cata/ana-morphisms.  It's interesting how
abstraction is kept fairly high, while the nitty gritty uses an
imperative algorithm.

How to load this in my head?  Some take-away points:

 - knot tying requires node-equality to allow recursive traversal.
   since there is no pointer equality, this requires unique
   identifiers for each node.  overall it seems more of a hassle than
   anything else; finite lists of nodes/edges may make more sense from
   an implementation pov.

 - imperative algos (i.e. in ST[2]) aren't necessarily evil.  for
   graphs they are probably way too useful/efficient to dismiss
   (i.e. node marking vs recording node tags in a dictionary).


[1] http://www.haskell.org/haskellwiki/The_Monad.Reader/Issue5/Practical_Graph_Handling
[2] http://www.haskell.org/haskellwiki/Monad/ST

[Reply][About]

[<<][compsci][>>][..]