Informatica Logo

International Journal

Main Page
Editorial Board
Instructions to Authors
Subscription Information

Author Index
Papers in Production

INFORMATICA, 1999, Vol. 10, No. 1, 5-26
© Institute of Mathematics and Informatics, Vilnius, 1998

ISSN 0868-4952

Primitive (Co)Recursion and Course-of-Value (Co)Iteration, Categorically

Tarmo UUSTALUa, Varmo VENEb

aDept. of Teleinformatics, Royal Inst.of Technology, Electrum 204, SE-164 40 Kista, Sweden E-mail:

bInst.of Computer Science, Univ.of Tartu, J. Liivi 2, EE-2484 Tartu, Estonia E-mail:


In the mainstream categorical approach to typed (total) functional programming, datatypes are modelled as initial algebras and codatatypes as terminal coalgebras. The basic function definition schemes of iteration and coiteration are modelled by constructions known as catamorphisms and anamorphisms. Primitive recursion has been captured by a construction called paramorphisms. We draw attention to the dual construction of apomorphisms, and show on examples that primitive corecursion is a useful function definition scheme. We also put forward and study two novel constructions, viz., histomorphisms and futumorphisms, that capture the powerful schemes of course-of-value iteration and its dual, respectively, and argue that even these are helpful.


typed (total) functional programming, category theory, program calculation, (co)data-\break types, forms of (co)recursion

To preview Lithuanian abstract see full article text

PDFTo preview full article text in PDF format click here

Get Free ReaderYou could obtain free Acrobat Reader from Adobe

TopTop Copyright © INFORMATICA, Vilnius University Institute of Mathematics and Informatics, 2010