The expression lemma

Short paper published in Proceedings of MPC 2008.
Full report to be submitted for journal publication.


Ralf Lämmel and Ondrej Rypacek

Algebraic data types and catamorphisms (folds) play a central role in functional programming as they allow programmers to define recursive data structures and operations on them uniformly by structural recursion. Likewise, in object-oriented (OO) programming, recursive hierarchies of object types with virtual methods play a central role for the same reason. There is a semantical correspondence between these two situations which we reveal and formalize categorically. To this end, we assume a coalgebraic model of OO programming with functional objects. The development may be helpful in deriving refactorings that turn sufficiently disciplined functional programs into OO programs of a designated shape and vice versa.

expression lemma, expression problem, functional object, catamorphism, fold, the composite design pattern, program calculation, distributive law, free monad, cofree comonad

Bibtex entry
 author = "Ralf L{\"a}mmel and Ondrej Rypacek",
 title = "{The expression lemma}",
 booktitle = "{Proceedings of Mathematics of Program Construction (MPC) 2008}",
 publisher = "Springer",
 series = "LNCS",
 year = 2008,
 month = jul,
 note = {To appear}


maintained by Ralf Lämmel (Email: