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