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.
==============================================
Extensible and Modular Generics for the Masses
==============================================
Extensible and Modular Generics for the Masses (EMGM) is a library for
generic programming in Haskell using type classes and a
sum-of-products view.
-------
Updates
-------
emgm-0.3 is the third major release, and it arrives a little over a
month after emgm-0.2.
Deriving is now greatly improved! Due to recent reports from users, we
realized the current implementation just wasn't going to cut it. EMGM
already supports a wide range of datatypes, so why not make the
deriving code support just as many. Hopefully, it works well for you.
Please let us know if your datatype is not supported.
There are several new functions in the EMGM family. These include:
cast (a type-safe, configurable, generic cast) and everywhere and
everywhere' (functions similar to those of the same name in SYB that
apply a transformation everywhere a certain type is found).
-------
Changes
-------
Changes from emgm-0.2 include:
* Improved deriving can now handle datatype collections like this one:
http://www.haskell.org/pipermail/generics/2009-February/000429.html
* cast function
> cast :: Rep (Map a) b => a -> b
* everywhere and everywhere'
> everywhere :: Rep (Everywhere a) b => (a -> a) -> b -> b
> everywhere' :: Rep (Everywhere' a) b => (a -> a) -> b -> b
They both perform transformations on a-values in a b-value. The former
does them bottom-up, the latter top-down. The names come from similar
functions in SYB that use rank-2 types. Note the difference.
> everywhere :: (forall a. Data a => a -> a) -> forall a. Data a => a -> a
> everywhere' :: (forall a. Data a => a -> a) -> forall a. Data a => a -> a
------------
Known Issues
------------
Due to a problem with the template-haskell package and Cabal, you
cannot cabal-install the emgm package with GHC 6.8. However, take
heart! EMGM works very well with GHC 6.8. You merely have to download
the tar.gz package from Hackage yourself, build it, and install it.
Since it doesn't require any dependencies beyond what comes with GHC,
installation is a breeze!
-------------------
General Information
-------------------
Visit the home page:
http://www.cs.uu.nl/wiki/GenericProgramming/EMGM
----------------
General Features
----------------
The primary features of EMGM include:
* Datatype-generic programming using sum-of-product views
* Large collection of ready-to-use generic functions
* Included support for standard datatypes: lists, Maybe, tuples
* Easy to add support for new datatypes
* Type classes make writing new functions straightforward in a
structurally inductive style
* Generic functions are extensible with ad-hoc cases for arbitrary datatypes
* Good performance of generic functions
The features of this distribution include:
* The API is thoroughly documented with Haddock
* Fully tested with QuickCheck and HUnit
* Program coverage ensures that all useful code has been touched by tests
* Tested on both Mac and Windows systems
------------
Requirements
------------
EMGM has the following requirements:
* GHC 6.8.1 - It has been tested with versions 6.8.3 and 6.10.1
* Cabal library 1.2.1 - It has been tested with versions 1.2.4.0 and 1.6.0.1.
-----------------
Download & Source
-----------------
Use caball-install:
cabal install emgm
Get the package:
http://hackage.haskell.org/cgi-bin/hackage-scripts/package/emgm
Check out the current source with Subversion:
svn checkout https://svn.cs.uu.nl:12443/repos/dgp-haskell/EMGM/trunk
Or view it online:
https://svn.cs.uu.nl:12443/viewvc/dgp-haskell/EMGM/trunk/
--------
Examples
--------
Check out the examples:
https://svn.cs.uu.nl:12443/viewvc/dgp-haskell/EMGM/trunk/examples/
--------------
Bugs & Support
--------------
Report issues or request features:
http://code.google.com/p/emgm/issues/list
Discuss EMGM with the authors, maintainers, and other interested persons:
http://www.haskell.org/mailman/listinfo/generics
-------
Credits
-------
The research for EMGM originated with Ralf Hinze. It was extended with
work by Bruno Oliveira and Andres Löh. More details of the library
functionality were explored by Alexey Rodriguez. We are very grateful
to all of these people for the foundation on which this library was
built.
The current authors and maintainers of EMGM are:
* Sean Leather
* José Pedro Magalhães
* Alexey Rodriguez
* Andres Löh
