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          

• download meta.tar.gz
• gunzip and untar the archive
• start hugsc(I have tested the programs with Hugs 1.4, Version of June 1998)
• enter :load ADTprog

Metamorphic Programming: Structured Recursion for Abstract Data Types

The category theory background is given in the papers

Categorical Programming with Abstract Data Types and
Random Access To Abstract Data Types

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.

The Categorical Imperative - Or: How to Hide Your State Monads