# A.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 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\in 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 Python, C and Java (but C and Java only allow $S$ to be the set of integers $\{0,\dots,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\in 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},\dots,X_{n})$ is a function such that given a value $v_{1}$ for $X_{1}$, a value $v_{2}$ for $X_{2}$, …, and a value $v_{n}$ for $X_{n}$ 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(X_{1}{=}v_{1},X_{2}{=}v_{2},\dots,X_{n}{=}v_{n})$. The set of variables, $X_{1},X_{2},\dots,X_{n}$ is called the scope of $f$. The array $f[X_{1},X_{2},\dots,X_{n}]$ is a function on $X_{1},X_{2},\dots,X_{n}$ 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 $X_{1},X_{2},\dots,X_{n}$, then $f(X_{1}=v_{1})$ is a function of $X_{2},\dots,X_{n}$, such that

 $(f(X_{1}{=}v_{1}))(X_{2}{=}v_{2},\dots,X_{n}{=}v_{n})=f(X_{1}{=}v_{1},X_{2}{=}% v_{2},\dots,X_{n}{=}v_{n})$

Factors can be added, multiplied or composed with any other operation level on the elements. If $f_{1}$ and $f_{2}$ are factors, then $f_{1}+f_{2}$ is a factor with scope the union of the scopes of $f_{1}$ and $f_{2}$, defined pointwise:

 $\displaystyle{(f_{1}+f_{2})(X_{1}{=}v_{1},X_{2}{=}v_{2},\dots,X_{n}{=}v_{n})}$ $\displaystyle\mbox{}=f_{1}(X_{1}{=}v_{1},X_{2}{=}v_{2},\dots,X_{n}{=}v_{n})+f_% {2}(X_{1}{=}v_{1},X_{2}{=}v_{2},\dots,X_{n}{=}v_{n})$

where we assume that $f_{1}$ and $f_{2}$ ignore variables not in their scope. Multiplication and other binary operators work similarly.

###### Example A.1.

Suppose $f_{1}(X,Y)=X+Y$ and $f_{2}(Y,Z)=Y+Z$. Then $f_{1}+f_{2}$ is $X+2Y+Z$, which is a function of $X$, $Y$ and $Z$. Similarly $f_{1}\times f_{2}=(X+Y)\times(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}\times f_{1})(W=1,X=2,Y=3)=3\times 5=15$.

Other operations on factors are defined in the book.