Two very closely related relations emerge which involve changing order.
A relation can be represented as a collection of pairs or, if all its final values are relations, as a collection of lists of length 3, or, if all the final values of these relations are also relations of length 4, and so on. One may formalise this by representing a relation r as {[r]} and allowing the following re-expression rule: if, in a representation of r as a collection, C, of lists of length 1+n (for some natural n), every s[n], with s in C, is a relation; then another representation of r is {list (2+n:t:): for some s in C, (n:t:) = (n:s:) and s(n) relates t(n) to t(1+n)}. Note, however, that any time a list in C ends in empty, that list gets ignored in the representation of one greater length: thus, for lengths greater than two, distinct relations may have identical representations (eg at length 3, every restriction of produce(empty) has empty representation).
In such representations, reverse and transpose appear as swap the
highest-numbered two entries in each list
in representations by lists of
lengths 2 and 3, respectively. The same operation for higher list lengths is
entirely well-defined: in general, any currying operator (shuffling the order of
arguments to a function, for example) can be obtained from this family, of which
reverse and transpose are the first two for which the definition (which calls
for at least two entries) is meaningful.
Formally, transpose is
but it may be more helpful to think of it as
For a general relation, f, transpose(f) is a mapping: its initial values (valid inputs) are the initial values of f's final values; its final values (outputs) are relations, whose initial values are initial values of f. If f relates y to h and h relates x to p, then x (as an initial value of h, which is a final value of f) is an initial value of transpose(f), which maps it to transpose(f,x), which relates y to p. Thus transpose is a reorganisation of relations whose final values are relations.
Transpose is most easily understood by examining what it does to a mapping whose outputs are all mappings. Then u=f(y), v=u(x) and transpose(f) accepts x precisely if there is some y (which f accepts and) for which f(y) accepts x: transpose(f,x) = (y-> f(y,x)) then maps any such y to the ensuing f(y)(x). Note that f(y,x) means f(y)(x), read as (f(y))(x), so f is given y as input and f(y) is given x as input.
Notice that if some of f's final values are not relations, the exceptions are simply ignored, as are all instances of empty as a final value: transpose(f) depends on f only via (: f :{non-empty relation}).
I apply transpose to a few other relations in my bestiary: on itself, we get
transpose(transpose), mapping an arbitrary value, x, to the relation f relates
v to x: f->v
, which is the transpose of final(x); so transpose(transpose) =
transpose&on;final.
Written by Eddy.