From: "Al Vilcius" <al.r@vilcius.com> concatenation of lists and streams from an alphabet A: - formally given by the unique arrow to a terminal coalgebra - heuristically it is supposed to be thought of as erasing the comma between a pair of streams (a,b)
But how is this to be understood computationally?
I'm unclear as to the benefits if any of addressing Al's concern in the context of coalgebras, or of anything to do with categories for that matter. Forgetting for the moment any effectiveness that might be implicit in the notion of "stream", the underlying structures here become accessible to a broader audience when presented as labeled chains (linear orders), call these lists, with the list members being the labels. The concatenation of a linearly ordered family of lists is their marked union (with the family's index set providing the marks), augmented to a linear order in the evident way (formally, dependent lexicographic product). With regard to effectiveness, I would expect Al's intuitions to be satisfied by defining the effective part eff(L) (or fin(L) for finite) of a list L as the sublist consisting of those elements having only finitely many predecessors, necessarily a prefix of L. So for example eff(N) = eff(N @ L) = N eff(Z) = eff(R) = eff(Z @ [3,1,4]) = [] eff(R+) = [0] eff([3,1,4] @ Z) = [3,1,4] eff(eff(L)) = eff(L) eff(L @ M) = L @ eff(M) if eff(L) = L = eff(L) otherwise eff(L @ M) = eff(L @ eff(M)) but not eff(L @ M) = eff(eff(L) @ eff(M)) where L,M are any lists, N,Z,R,R+ are the lists of natural numbers, integers, reals, and nonnegative reals standardly ordered, @ (McCarthy's MLISP notation c.1959 for APPEND) is binary concatenation, and [a,b,c] parallels set theory's {a,b,c}. The n-th element (n in N) of L is defined for L iff it is defined for eff(L). The head of a list is its first element, the tail is the sublist that omits just the head, and the domain of both head and tail consists of those lists with nonempty effective part. Al's example of the concatenation of the list of positive odd integers with the reverse of the list of even such then has as its effective part just the positive odd integers. Let me hasten to add that I am not here raising any objection to coalgebraic notions of concatenation in the context of an overall coalgebraic framework, where considerations of uniformity fully justify the use of coalgebraic definitions throughout. For the purposes of answering Al's question however, uniformity merely for its own sake has the potential to become an obstacle to understanding such an elementary issue, at least for those not already thoroughly steeped in the coalgebraic method. Vaughan Pratt