Updatable Folds

Program-Transformation.Org: The Program Transformation Wiki

Updatable folds are a notion connected to FunctionalTransformationSystems.


The bottom-up traversal scheme associated to a multi-sorted signature, or a system of mutually dependent datatypes, is captured by a family of fold functions. These fold functions are parameterized with a fold algebra, which stores the functions to be applied at each node during traversal. A fold algebra can be constructed by applying fold algebra updates to a basic fold algebra.

These notions were coined in DealingWithLargeBananas, and they were used in the FunctionalTransformationSystemsPaper and in StrategiesAsUpdatableFoldAlgebras.


For a concise example of updatable folds and their application to program transformation, see the FunctionalTransformationSystemsPaper.

See also