[Hs-Generics] Complex Traversal Methods

[William Pearson]

I have recently been thinking about traversing procedural graphs (e.g.
L-systems and possible game state graphs), and have needed to develop
ways of traversing them beyond doing stuff to everything (due to
cycles and potentially being infinite). This may have been covered
already, if so I would be interested in references.

I thought the shape of the methods I developed might be of use to the
generic community. The types of thing the idea might be useful for is
something like giving karma to all of a certain persons friends and
also their friends, but only once, in a social networking site.

Basically it involves transforming the data type to another that has
the information you need and then automatically deconstructing the
data type after you have traversed the structure. What I think makes
it more interesting is I decided that the functions to construct and
deconstruct should be a data structure, and you can have functions to
compose them so you could have a traversal controller to avoid loops
and one to only go down two steps and add them together so the
construction and deconstruction are done in the right order*, so you
can combine them together.

Some basic examples of the way I am going to code stuff I use for my
procedural graphs can be found on my blog
http://vrrm.wordpress.com/2009/03/03/unbounded-graphs2/. If I have
some spare time, I'll have a look at a way to do this for Generics.

  Will Pearson

* The loop avoidance would add make the data a tuple with a bool and
didn't do anything if the Bool had been set to true. The depth
controller would make the data a tuple with an Int that got
incremented as you go down recursion levels which you then checked to
see if it was above 2, in which case you could halt recursion.