Corecursion exploits the existence of a morphism from a coalgebra for an endofunctor to a terminal coalgebra for the same endofunctor to define an operation. It is dual to recursion. See also coinduction.
For the endofunctor on Set, the terminal coalgebra is , the extended natural number system. Define a function :
where is as defined at extended natural number.
Then is an -coalgebra. The unique coalgebra morphism (to the terminal coalgebra ) is addition on the extended natural numbers.
Jiří Adámek, Introduction to Coalgebra (pdf)
Lawrence Moss, Norman Danner, On the Foundations of Corecursion (journal, pdf)
Revised on September 28, 2012 16:18:36
by Urs Schreiber