[Haskell-beginners] operations on cyclic data structures

[Brent Yorgey]

On Sun, Apr 07, 2013 at 11:38:23AM -0700, Josh Stratton wrote:
> I'm new to haskell and functional programming in general.  One of the
> things I've tried to wrap my brain around is dealing with cyclic immutable
> data structures like the half-edge data structure.
> 
> First, how would an experienced haskeller design their data structures to
> perform an operation on this structure?  I've implemented this structure
> with mutable structures in c++ but when when I've asked about cyclic
> structures I'm pointed to research papers which overwhelm my experience in
> immutable data structures like those in haskell.

Immutability and cyclic data structures do not mix very well at all.
"Updating" an immutable structure of course really means generating a
new structure.  However, because of immutability any parts that do not
change can be shared between the old and new structures.  The parts
the must be rebuilt are only those nodes from which the updated part
is reachable.  Typically, with acyclic data structures (i.e. trees),
this part that must be updated is small, and large parts of the
structure remain unchanged and can be shared between the old and new
structures.  However, with cyclic data structures, typically every
part of the structure is reachable from every other part --- hence,
any update necessitates rebuilding the entire structure.

Another problem with cyclic data structures is that one often cannot
perform operations such as "map" without losing all the sharing.

There are solutions to this but you're right that they tend to require
a fair bit of background to understand.  The simplest way to proceed
is to assign unique identifiers to nodes and store the data structure
implicitly, e.g. by storing in each node the identifiers of its
neighbors rather than actual references to them.  In essence this is
"simulating" the ability to have mutable pointers.

Another possibility is to use a "zipper" structure to be able to "move
around" within a structure and make modifications at the "current
location".  However, this gets rather complicated for things like 2D
meshes.

A more sophisticated solution uses "abstract syntax graphs" but now we
are into cutting-edge research territory.

-Brent