## 16.2 Functions, Factors and Arrays

Many of the algorithms in this book manipulate representations of
functions. We extend the standard definition of function on sets to include
functions on (sets of) variables. A **factor** is a representation of a
function. An **array** is an explicit representation of a function that
can have its individual components modified.

If *S* is a set, we write *f(S)* to be a function, with domain
*S*. Thus, if *c∈S*, then *f(c)* is a value in the range of *f*. *f[S]* is like *f(S)*, but
individual components can be updated. This notation is based on that
of C and Java (but these languages only allow for the case
where *S* is the set of integers *{0,...,n-1}* for arrays of size
*n*). Thus *f[c]* is a value in the range of *f*. If *f[c]* is
assigned a new value, it will return that new value.

This notation can be extended to (algebraic) variables. If *X* is an
algebraic variable with domain *D*, then *f(X)* is a function that
given a value *x∈D*, returns a value in the range of *f*. This
value is often written as *f(X=x)* or simply as *f(x)*. Similarly,
*f[X]* is an array indexed by *X*, that is, it is a function of *X*
whose components can be modified.

This notation can also be extended to set of variables. *f(X _{1},X_{2},...,X_{n})*
is a function such that given a value

*v*for

_{1}*X*, a value

_{1}*v*for

_{2}*X*, ..., and a value

_{2}*v*for

_{n}*X*returns a value in the range of

_{n}*f*. Note that it is the name of the variable that is important, not the position. This factor applied to the specific values is written as

*f(X*. The set of variables,

_{1}=v_{1},X_{2}=v_{2},...,X_{n}=v_{n})*X*is called the

_{1},X_{2},...,X_{n}**scope**of

*f*. The array

*f[X*is a function on

_{1},X_{2},...,X_{n}]*X*where the values can be updated.

_{1},X_{2},...,X_{n}Assigning just some of the variables gives a function on the remaining
variables. Thus, for example, if *f* is a function with scope *X _{1},X_{2},...,X_{n}*,
then

*f(X*is a function of

_{1}=v_{1})*X*, such that

_{2},...,X_{n}(f(X_{1}=v_{1}))(X_{2}=v_{2},...,X_{n}=v_{n})=f(X_{1}=v_{1},X_{2}=v_{2},...,X_{n}=v_{n})

Factors can be added, multiplied or composed with any other operation
level on the elements. If *f _{1}* and

*f*is a factor, then

_{2}*f*is a factor with scope the union of the scopes of

_{1}+f_{2}*f*and

_{1}*f*, defined pointwise:

_{2}

(f _{1}+f_{2})(X_{1}=v_{1},X_{2}=v_{2},...,X_{n}=v_{n})= f _{1}(X_{1}=v_{1},X_{2}=v_{2},...,X_{n}=v_{n}) + f_{2}(X_{1}=v_{1},X_{2}=v_{2},...,X_{n}=v_{n})

where we assume that *f _{1}* and

*f*ignore variables not in their scope. Multiplication and other binary operators work similarly.

_{2}**Example 16.1:**Suppose

*f*and

_{1}(X,Y)=X+Y*f*. Then

_{2}(Y,Z)=Y+Z*f*is

_{1}+f_{2}*X+2Y+Z*, which is a function of

*X*,

*Y*and

*Z*. Similarly

*f*.

_{1}×f_{2}=(X+Y)×(Y+Z)*f _{1}(X=2)* is a function of

*Y*, defined by

*2+Y*.

Suppose that variable *W* has domain *{0,1}* and *X* has domain
*{1,2}*, the factor *f _{3}(W,X)* can be defined by a table such as:

W | X | value |

0 | 1 | 2 |

0 | 2 | 1 |

1 | 1 | 0 |

1 | 2 | 3 |

*f _{3}+f_{1}* is a function on

*W,X,Y*, such that, for example,

(f_{3}+f_{1})(W=1,X=2,Y=3) = 3+5=8

Similarly, *(f _{3}×f_{1})(W=1,X=2,Y=3)
= 3×5=15*.

Other operations on factors are defined in the book.