Needed revision in this page (major): observe that f = ((b*a←a)←b [for which f(b,a) = b*a] enables us to compose relations such as f(b); deploy this to compare (f(a)&on;f(b))(c) with f(a, f(b,c)); c.f. Also, describe (:f|) as such rather than bothering to name it.
Start with the classical definition of associativity. Explain how it becomes bulk action. Define bulk action, regardless of associativity, bracket as a composition of a*z ←a relations, show that associativity makes bracketing irrelevant. Express bulk action of arbitrary * in terms of that of &on; This can even be done so as to make a binop (C:|A×B) discussible mainly in terms of composition of relations (B:|B).
Following the old form's account: one binary operator, * characterised by
star = (b*a ←a) ←b, associates before
another, % characterised
by rats = (b%c←c)←b, when:
In a relation-based view, rats(a) and rats(b) are relations (hence so is their composite) and star(a,b) is, like a and b, one of the values rats will accept; associativity is saying that the result in this case coincides with the composite of rats(a) and rats(b).
Thus combining things with star before passing them to rats has the same effect as passing each to rats, then composing the results: star is a pull-back, through rats, of composition. The question naturally arises: to what extent may such a pull-back be inferred from rats itself ?
Actually, it's not a pull-back, I think it may be a functor, or a transformation ... better look that up ...
... uh-oh ! digression warning ... back to the main thread:
A binary operator, *, is described as associative iff, whenever a*(b*c) and (a*b)*c are meaningful, they are equal: in such a case, it may be written a*b*c without ambiguity.
Applying associativity repeatedly, we arrive at similar equal when
meaningful
for ((a*b)*c)*d, (a*(b*c))*d, a*((b*c)*d), a*(b*(c*d)),
(a*b)*(c*d) which can thus be written a*b*c*d; this process can be repeated
indefinitely to combine any finite sequence of values. Where only some of the
bracketings are meaningful, so long as the meaningful ones remain equal, the
same un-bracketed expression may unambiguously be used (though the brackets
would have pedagogic value). Thus an associative binary operator becomes
synonymous with a mechanism for combining finite sequences of values.
Representing sequences as lists, this bulk action
of * on sequences
of values can be expressed as a mapping which consumes a list of values and
emits a single value: write this as bulk(*, [a,...,z]) = a*...*z and I'll refer
to bulk(*) as star [instead of using that name for (a*b←a)←b]. We may
regard * itself as the restriction of star to lists of length two: a*b =
star([a, b]). Formally, star only acts on lists of length at least two: but it
is natural to extend it to lists of length one by star([a]) = a; so star accepts
non-empty lists. If * has an identity (some e for which a*e = a = e*a for each
a) one may sensibly identify it with star([]): otherwise, star([]) is
undefined.
For bulk action to be well-defined, * must be associative. This may be
expressed in terms of star by saying that, when star accepts a non-empty list,
S, which can be broken into two non-empty lists, L and R, the result of
combining star(L) with star(R), i.e. star([star(L), star(R)]), is the same as
star(S). Breaking the list in two is to be understood in terms of the natural
append
binary operator on lists, which I'll denote using @ and define by
[a,...,m] @ [n,...,z] = [a,...,m,n,...,z]. In these terms, L@R=S is what it
means for S to break apart into L and R. This means we can write the
associativity constraint as star(L@R) = star([star(L), star(R)]) and I can
define
A bulk action (possibly what some folk refer to as a monad) is a mapping, (: star :{lists}) for which:
Define the mapping bulk =
and note that its reverse is the mapping
[or use the latter to define bulk's reverse and, hence, bulk]. Thus bulk provides an isomorphism between associative binary operators and bulk actions. Various common binary operators have standard names for their bulk actions: addition's bulk(+) is called sum, multiplication's bulk(×) is called product, composition's bulk(&on;) is called composite and bulk(@) may sensibly be called flatten. Particular contexts may introduce names for bulk actions of other associative binary operators; for the generic binary operator * I'll routinely use star as bulk(*)'s name.
The bulk action construction effectively casts @, the append binary operator
of lists, in the rôle of a universal associative binary operator: it
should be clear that @ is associative; and the bulk action of any
binary operator flows round
@ in the manner stipulated by the definition
of bulk action. Proof of the structural properties which allow us to define
bulk follows directly from the special case of @ and its bulk action.
A binary operator, *, is effectively synonymous with the mapping (: (:
a*b←b :) ←a :) whose outputs (left values) are mappings: if we allow,
in place of this mapping, a relation, star, whose left values are relations, a*b
reads as an arbitrary value related to b by some relation that star relates to a
- were star a mapping, this would reading corresponds to star(a) relates each
a*b to b
and, were star(a) also a mapping, to a*b = star(a,b)
.
Using a relation ({relations}:star:) to define an ambiguous binary operator *, as above, still enables us to construct (: (: a*b←b :) ←a :) which is again a mapping; for given a, (: a*b ←b :) is the relation unite(|star:{a}). So a general binary operator is characterised by a mapping; in so far as this mapping's outputs (left values) are mappings, the binary operator is unambiguous.
In the same spirit as this ambiguity, we can define a*b*c to denote an arbitrary value that either (a*b)*c or a*(b*c) can denote; this extends naturally to longer chains of values combined using * and transforms the definition of associativity into a simple statement that all such composites are unambiguous - not only is * unambiguous, so is its bulk action. In general, bulk(*) may relate several values to each list of values that * can combine.
Thus bulk's generalisation is:
with the former ambiguous not just through ambiguity in bulk(*,L), bulk(*,R) and ambiguity arising from combining these two with *, but also through the ambiguity of choice of distinct decompositions of the list L@R into two lists in (:bulk(*)|). An associative binary operator is then simply a binary operator whose bulk action is unambiguous - i.e. a mapping.
While I shall entertain ambiguous binary operators, even these fit into a standard framework which may be built using append, @ as outlined above, and composition, &on;.
For a general binary operator, *, with bulk(*) as generalised above, and non-empty list S which bulk(*) accepts: S is L@[s] for some list L and value s; let star = (: (:a*b←b:) ←a :) and observe that star&on;L is a list of relations, [star(L(0)),...], which we can compose using bulk(&on;); &on; has an identity, namely (:x←x:), so can use this as bulk(&on;,[]) to cope with the case where L is empty, S = [s]. We thus obtain bulk(&on;, star&on;L, s); when L is [a,...,r], this is just a*(...*(r*s)...), which is one of the bracketings allowed by bulk(*,L@[s]); so (: bulk(*,L@[s]) ←s :) subsumes bulk(&on;, star&on;L), in general. A softer contraint than associativity would require the two to be equal, without necessarily obliging them to be mappings (as associativity does).
We can do better, though. Instead of popping an item off the list's end to be fed to the composite: (C:star:A) embeds *'s left operands (members of A; for a in A, star(a) = a*b←b) in some collection, C, of relations; bulk(&on;) will compose arbitrary non-empty lists of C's members; so bulk(&on;)&on;(: star&on;s ←s :{lists (A:|n)}) maps any non-empty list of A's members, via the corresponding list of C's members, to a relation. If C = (|star:) is closed under composition, the resulting relation must be star(a) for at least some a in A; leading to consideration of (: a← star(a) :)&on;bulk(&on;)&on;(: star&on;s ←s :) as a natural bulk action on A, yielding answers in A; this will indeed coincide with bulk(*) at least when * is associative.
Written by Eddy.