Camlp4 have a generator for a "map" style traversal of a data structure.
The filter Camlp4MapGenerator reads OCaml type definitions and generate a class that implements a map traversal. The resulting class have a method per type that you can override to do something more interesting than just copying the tree.
Using the generated map
open Camlp4.PreCast let simplify = object inherit Ast.map as super method expr e = match super#expr e with | <:expr< $x$ + 0 >> | <:expr< 0 + $x$ >> -> x | x -> x end in AstFilters.register_str_item_filter simplify#str_item
In this code one inherits from Ast.map and override the case for expression. In this particular case one starts by applying the transformation on sub-trees (super#expr e). Then one matches (x + 0 or 0 + x) and removes it, or does nothing when it does not match. The simplify object is then used as a structure item transformer (simplify#str_item) and given to Camlp4 through a registration mechanism that is automatically used by Camlp4.
$ ocamlc -c -pp camlp4of -I +camlp4 camlp4/test/fixtures/simplify.ml $ camlp4o ./camlp4/test/fixtures/simplify.cmo -str '(x + 0 + (0 + 42)) + 0'
However using this class mechanism is somewhat cumbersome for classical tasks. Camlp4 provides some trivial functions for common transformations.
For instance Ast.map_expr maps expressions:
let map_expr f = object inherit map as super; method expr x = f (super#expr x); end
One can then rewrite the previous example like that:
open Camlp4.PreCast let simplify = Ast.map_expr begin function | <:expr< $x$ + 0 >> | <:expr< 0 + $x$ >> -> x | x -> x end in AstFilters.register_str_item_filter simplify#str_item
You can register functions on implementation items/phrases (str_item), signature items (sig_item) and toplevel phrase (topphrase).
AstFilters.register_str_item_filter AstFilters.register_sig_item_filter AstFilters.register_topphrase_filter
Generate your own map for your types
Camlp4MapGenerator act as a filter, therefor it does not extend the syntax in a useless way but statically expands the class name Camlp4MapGenerator.generated (or Camlp4Filters.GenerateMap.generated for compatibility with older versions) by its definition.
type t1 = ... and t2 = ... ... and tN = ... ;; class map = Camlp4MapGenerator.generated;;
A complete example is proposed in Camlp4MapGenerator Example.