Metamorphic Programming Extension to Haskell

Metamorphic programming is an approach to extend the structured recursive programming discipline, which favors the use of fold operations over general recursion, to abstract data types.cThe key idea is to represent an ADT by two parts, a constructorand a destructor,which are essentially functions to/from a common representation.cThen a fold can work on an ADT by applying parameter functions to values that are delivered by the ADT's own destructor.cFold operations that use as a parameter the constructor of another ADT, called ADT transformers,play an important role and offer a concise programming style.cSeveral laws for ADT folds and transformers exist that can be used for program optimization and verification.

rdup = via list set list          rdup animation
To experiment with metamorphic programming: The idea of metamorphic programming is explained and motivated in the paper That paper uses Haskell notation and presents most of the examples contained in the distribution.
I am collecting laws/equations here.

The category theory background is given in the papers

See also this related page.

Metamorphic programming offers many opportunities for program optimization. One aspect is to introduce state monads to improve the efficiency of data structures.cIn programs that are expressed as ADT transformers, we can observe restricted usage patterns for ADTs, and this can be exploited to derive (i) partial data structurescorrectly implementing the ADTs and (ii) imperative realizations of these partial data structures. With a library of ADTs together with (some of) their imperative implementations, efficient versions of functional programs can be obtained without being concerned or even knowing about state monads. This is described in the paper below. One example is the optimization of a graph ADT resulting in an optimal imperative implementation of depth-first search.


last change: October 24, 2015 Martin Erwig  erwig@cs.orst.edu