F-coalgèbre

In mathematics, specifically in , an -coalgebra is a structure defined according to a functor , with specific properties as defined below. For both algebras and coalgebras, a functor is a convenient and general way of organizing a signature. This has applications in computer science: examples of coalgebras include lazy, infinite data structures, such as streams, and also transition systems. coalgebras are to -algebras. Just as the class of all algebras for a given signature and equational theory form a variety, so does the class of all -coalgebras satisfying a given equational theory form a covariety, where the signature is given by . Let be an endofunctor on a category . An -coalgebra is an object of together with a morphism of , usually written as . An -coalgebra homomorphism from to another -coalgebra is a morphism in such that Thus the -coalgebras for a given functor F constitute a category. Consider the endofunctor that sends a set to its disjoint union with the singleton set . A coalgebra of this endofunctor is given by , where is the so-called conatural numbers, consisting of the nonnegative integers and also infinity, and the function is given by , for and . In fact, is the terminal coalgebra of this endofunctor. More generally, fix some set , and consider the functor that sends to . Then an -coalgebra is a finite or infinite stream over the alphabet where is the set of states and is the state-transition function. Applying the state-transition function to a state may yield two possible results: either an element of together with the next state of the stream, or the element of the singleton set as a separate "final state" indicating that there are no more values in the stream. In many practical applications, the state-transition function of such a coalgebraic object may be of the form , which readily factorizes into a collection of "selectors", "observers", "methods" . Special cases of practical interest include observers yielding attribute values, and mutator methods of the form taking additional parameters and yielding states.