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
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. 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
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) 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).