Simple folding/unfolding

Identity: Folding
Category: Naming
Classifiers: simple folding specialisation expression definition
Internal cross references:
External cross references: XXX
Language: Haskell


Replace an instance of the right hand side of a definition by the corresponding left hand side. This is commonly known as folding, with the inverse termed unfolding or inlining.

showAll = (concat . format) . map show
table   = concat . format

showAll = table . map show
table   = concat . format

General comment:

The fold transformation of Burstall and Darlington we call a generative fold in that it generates a new recursive definition of a function or constant.

Left to right comment:

In the example, an instance of the definition of table is replaced by a call to table itself.

Note that the fold is not performed within the definition of table itself, nor in the body of any function called within the definition of table. A fold of this form will not change the meaning of the program.

Right to left comment:

The inverse is an example of unfolding or inlining in which a call to a function or constant is replaced by the appropriate instance of its right hand side.

Left to right conditions:

The definition which is folded needs to be in scope at the point of unfolding (this may be prevented by a redefinition of the identifier in an intervening scope).

Right to left conditions:

At the site of the unfolding the bindings for the free identifiers of the RHS of the unfolded definition (of foo, say) need to be the same as in the definition of foo.

Analysis required: Static analysis of bindings; call graph.