Higher-Order Catamorphisms as Bases for Program Structuring and Design Recovery

Paul Bailes, Leighton Brough, and Colin Kemp


Software design and development, Programming Tools and languages, Functional programming, Recursion pattern


Catamorphisms (“foldr” on lists, but generally applicable to any regular recursive datatype) are not just useful but are an effective basis for a recursion-pattern-based discipline of program design. A new presentation for catamorphisms makes it clear how they provide functional semantics for symbolic datatypes, with the capacity to expose significant variations in program design. A further development of the new presentation exploits the higher-order capabilities of functional languages. This is the key enabler for a comprehensive replacement of symbolic data and their interpreters, either implicit or explicit, with direct functional representations. These extensions, of the applicability of catamorphisms and of their presentations, make them even more attractive as bases for program structuring and design, and likewise as targets for software reverse engineering and design recovery.

Important Links:

Go Back