coalgebraic

One meaning (which is perhaps not so usual in math textbooks, but which you might encounter in the same kind of computer science literature where monads are popular) of the word algebraic is:

  • takes zero or more inputs, and produces exactly one output.

Even transcendental functions are algebraic in this sense; what matters is only that what one wishes to express can be put in classical function-of notation, like f(g(x,y),h(z)).

The source for Tcl programs not employing side-effects (upvar, uplevel, etc.) are algebraic in this sense, because each individual command takes zero or more arguments, and produces exactly one result.

The prefix co- makes everything go backwards, so something is coalgebraic if it:

  • produces zero or more outputs, and has exactly one input.

More generally, a notation for something can be coalgebraic if all fundamental components in it are coalgebraic.

Does such beasts actually exist in real life, though? Well, the traditional Unix composition in pipelines of many small programs that do simple things is kind of coalgebraic: the typical program has only stdin on the input side, but both stdout and stderr on the output side.

Flow diagrams are also sometimes considered as being coalgebraic. There is (in structured programming) only one place in which one can enter a block of code, but often several ways to leave it.

NEM Lazy data-structures, such as streams are coalgebraic. A normal data structure (such as a list or tree) is algebraic, in that it has a set of constructors that take 0 or more arguments and produce a single value of that type. A lazy data structure on the other hand, is coalgebraic as the emphasis is on destructors that take a value of that type (a stream) and produce 0 or more values from it (e.g. traversing a stream will produce a series of new values as they are calculated).