|
Martin Erwig. 7th Int. Conf. on Algebraic Methodology and Software Technology (AMAST'98), LNCS 1548, 406-421, 1998
We show how to define fold operators for abstract data types. The main idea is to represent an ADT by a bialgebra, that is, an algebra/coalgebra pair with a common carrier. A program operating on an ADT is given by a mapping to another ADT. Such a mapping, called metamorphism, is basically a composition of the algebra of the second with the coalgebra of the first ADT. We investigate some properties of metamorphisms, and we show that the metamorphic programming style offers far-reaching opportunities for program optimization that cover and even extend those known for algebraic data types.
If constructors are best represented using algebras, and observers are best represetned using colgebras, it is only natural to combine the two into a bialgebra!
This papers explores Metamorphic Programming. Haskell code for doing metamorphic programming is available.
Posted to theory by Ehud Lamm on 12/22/01; 8:41:46 AM
|
|
Categorical Programming with Abstract Data Types
