A.3 Functions, Factors, and Arrays

Many of the algorithms in this book manipulate representations of functions. We extend the standard definition of functions on sets to include functions on 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 cS, 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 Python, C, and Java (but C and Java only allow S to be the set of integers {0,,n1} 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 xD, 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(X1,X2,,Xn) is a function such that given a value v1 for X1, a value v2 for X2, …, and a value vn for Xn, returns a value in the range of 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(X1=v1,X2=v2,,Xn=vn). The set of variables, X1,X2,,Xn is called the scope of f. The array f[X1,X2,,Xn] is a function on X1,X2,,Xn where the values can be updated.

Assigning just some of the variables gives a function on the remaining variables. Thus, for example, if f is a function with scope X1,X2,,Xn, then f(X1=v1) is a function of X2,,Xn, such that

(f(X1=v1))(X2=v2,,Xn=vn)=f(X1=v1,X2=v2,,Xn=vn).

Factors can be added, multiplied, or composed with any other operation level on the elements. If f1 and f2 are factors, then f1+f2 is a factor with scope the union of the scopes of f1 and f2, defined point-wise:

(f1+f2)(X1=v1,X2=v2,,Xn=vn)
=f1(X1=v1,X2=v2,,Xn=vn)+f2(X1=v1,X2=v2,,Xn=vn)

where we assume that f1 and f2 ignore variables not in their scope. Multiplication and other binary operators work similarly.

Example A.1.

Suppose f1(X,Y)=X+Y and f2(Y,Z)=Y+Z. Then f1+f2 is X+2Y+Z, which is a function of X, Y, and Z. Similarly, f1×f2=(X+Y)×(Y+Z).

f1(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 f3(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

f3+f1 is a function on W, X, and Y such that, for example

(f3+f1)(W=1,X=2,Y=3)=3+5=8.

Similarly, (f3×f1)(W=1,X=2,Y=3)=3×5=15.

Other operations on factors are defined in the book.