Monads from inductive and coinductive types

Dr Tarmo Uustalu

Institute of Cybernetics

Tuesday, 12 March 2002, 15:00
Cybernetica Bldg (Akadeemia tee 21), room B216

Abstract: It is well known that, given an endofunctor H on a category C, the initial (A + H -)-algebras for different objects A of C (if they all exist), i.e., the algebras of wellfounded H-branching trees-with-variables over different variable supplies A, give rise to a monad with substitution as the extension operation. A similar monad, but with the additional property of being "completely iterative", is induced by the inverses of the final (A + H -)-coalgebras (if they exist), i.e., the algebras of non-wellfounded H-branching trees-with-variables. Aczel, Adámek, Milius, Velebil (2001) have given one very neat generalization of these facts. We consider a different one: if T' is a bifunctor such that the functors T'(-, X) uniformly carry a monad structure, then the initial T'(A, -)-algebras (if existing) give rise to a monad and the inverses of the final T'(A, -)-coalgebras (if existing) yield an "iterative" monad.

Tarmo Uustalu