In computer science, a stream is a finite or infinite sequence, distinguished from a list (usually assumed finite) or a sequence (usually assumed infinite).
Let be a set (or object of any category where the following makes sense). Consider the functor from Set (or ) to itself that maps to , where is the singleton set (or terminal object of ) and is the operation of disjoint union (or coproduct in ). It is well known that the initial algebra of is the set (or object) of lists on , which is the free monoid (or free monoid object in ) on . Less well known is the final coalgebra of ; it is the set (or object) of streams on .
Classically, , where is the set of natural numbers, in Set; that is, the set of streams is the disjoint union of the set of (finite) lists and the set of (infinite) sequences. In other categories, as well as in in constructive mathematics, this need not hold. Intuitively, we cannot necessarily decide whether a given stream is a finite list or an infinite sequence until we reach the end, and we may never reach the end. (Of course, if we know that we will never reach the end, then we know that it is infinite, but we do not know this just because we haven’t reached the end so far.) In categories very different from , will not even be a subobject of (although there will always be a morphism from to , indeed a unique such -morphism, since these are initial and final objects of the category of -algebras).
An extended natural number is an element of (much as a natural number is an element of ). Classically, such an element is either a natural number or infinity (the unique element of ).
Last revised on November 5, 2022 at 13:34:08. See the history of this page for a list of all contributions to it.