
\section{\label{lattices}Generalised Arrays}

     A straightforward way to store the values of, for example,
the potential function $u$ in section \ref{poisson} is in
a Haskell array.  This works well, provided the lattice is a
regular grid and its extent is rectangular.  It works less
well in the case of lattice gauge theory (section \ref{lgt}).
There the variables naturally live on the links of the lattice.
One can still use an array indexed by lattice sites, with
an extra dimension taking values in $1, \ldots, d$ to access the
$d$ links rooted at each site ($d$ is the dimension of the lattice).
This is quite clumsy.

     We can think of the sites of a lattice as the 0-dimensional
cells of the lattice, the links as the 1-dimensional cells, the
plaquettes as 2-dimensional cells, and so on.  Occurrence
of variables which naturally live on cells with
dimension higher than 0 is more common than one might initially
suppose.  Even in the Poisson equation the electric field, which
is the gradient of the potential, sits most naturally on the
links of the lattice.  The field in the $x$-direction
is associated with links in that direction; its value is just the
difference of the potential at the two ends of its link.
In the XY model there occur certain ``vortex configurations'' centred
on the plaquettes of the lattice---one can define a function which
counts the density of vortices in a general configuration, and this
function sits naturally on the plaquettes of the lattice.  As
explained in section \ref{lgt}, the energy function of a gauge theory
also ``lives'' on the plaquettes of a lattice.

     This suggests that it may be useful to generalise the usual model
of an array so that it is defined on an arbitrary (not necessarily
rectangular) lattice, and that the index space of a particular array can
be cells of that lattice of arbitrary (fixed) dimension.  This
generalised kind of array will be called a ``form''\footnote{This
terminology is motivated by an analogy between this kind of array and
the $p$-forms of differential geometry \cite{geometry}.}.

     The lattice itself is no longer thought of just as a set of
connected sites, but as a ``cell complex'' containing cells of
all dimensionality up to that of the lattice itself.

\subsection{Cells, lattices and forms}

     This section assumes some knowledge of the Haskell class
system.  The standard prelude defines, for example, the class
\verb$Ix$.  All types which can be used as index types for an
array belong to this class.  A type specification involving
type variables may be preceded by an assertion that some of
those variables belong to class \verb$Ix$.
Array operations like the array subscripting operator \verb$(!)$
(which, by the way, is an ordinary infix function---not special
syntax) are {\em overloaded} to apply to all instances of
\verb$Ix$.

     We need a Haskell class \verb$Cell$ which parallels the
index class \verb$Ix$ associated with ordinary arrays.
Two type constructors \verb$Lattice$ and \verb$Form$ go with this class.
They construct the following types\footnote{The \verb$(Cell a) =>$ prefix asserts that the type \verb$a$
must be an instance of class \verb$Cell$.}:
\begin{verbatim}
  (Cell a) => Lattice a
  (Cell a) => Form a b
\end{verbatim}
The latter is directly analogous to the ordinary Haskell
\verb$Array$ constructor---\verb$Form a b$ is the type of a form with
cell-type \verb$a$ and elements of type \verb$b$.  \verb$Lattice a$
is the type of a data structure describing a lattice with
cells of type \verb$a$.  It takes over the role of the
bounds pair for an ordinary array.

     To make this more concrete, a possible instance of the
\verb$Cell$ class, suitable for handling 2-dimensional rectangular
lattices, is
\begin{verbatim}
  data Cell2d = Cell2d0 (Int, Int)     |
                Cell2d1 (Int, Int) Int |
                Cell2d2 (Int, Int)
\end{verbatim}
which can represent a site, link or plaquette of the
lattice\footnote{\verb$Form$ and \verb$Lattice$
types will be treated, in this section at least, as abstract types.
There seems to be
little advantage in treating the cell types themselves as abstract---it is
convenient to have access to the constructors, for referring to an element
of the lattice at known coordinates}.  The numeric fields are the
cell coordinates, and in the 1-cell case, the link direction.
The cell type alone does not
define the lattice shape.  We need at least to know the size of a
rectangular lattice, and besides that, the ``edge conditions'' have to
be specified---the lattice may have a boundary at the edges, or be
connected cyclically, etc.  We will assume the existence of
a predefined function such as
\begin{verbatim}
  torus2d :: Int -> Int -> Lattice Cell2d
\end{verbatim}
which takes the width and height of the lattice as parameters, and
returns an instance of an abstract data type representing (in this
example, let's say) a periodic lattice of the specified size.
A possible implementation of \verb$torus2d$ is given in appendix
\ref{topologyExample}.  Now, we can
start building forms.  The function analogous to the ordinary
Haskell \verb$array$ is
\begin{verbatim}
  form :: (Cell a) => Lattice a -> Int -> [Assoc a b] -> Form a b
\end{verbatim}
This constructs a form from an ``association list''.
The first parameter is the lattice on which the form is to be
defined; the second is the ``rank'', $r$, of the form---that is, the
dimension of the cells on which it is defined; the third is
an association list completely analogous to the corresponding
argument of \verb$array$---a list of pairs associating each cell
of dimension $r$ in the lattice with a value.  As a mundane
example, the expression
\begin{verbatim}
  form l 1 [c := 0.0 | c <- cells l 1]
\end{verbatim}
is 1-form with value $0.0$ on each link of lattice \verb$l$.
\begin{verbatim}
  cells :: (Cell a) => Lattice a -> Int -> [a]
\end{verbatim}
is analogous to \verb$range$, returning a list
of all cells of a specified dimension in the given lattice.
Ultimately, the following operations on forms will also be needed
\begin{verbatim}
  accumForm :: (Cell a) => Lattice a -> Int -> [Assoc a b] -> Form a [b]
  lattice   :: (Cell a) => Form a b -> Lattice a
  rank      :: (Cell a) => Form a b -> Int
  (!#)      :: (Cell a) => Form a b -> a -> b
   
  (//#)     :: (Cell a) => Form a b -> [Assoc a b] -> Form a b
   
  listForm  :: (Cell a) => (Lattice a) -> Int -> [b] -> Form a b
   
  fassocs   :: (Cell a) => Form a b -> [Assoc a b]
  findices  :: (Cell a) => Form a b -> [a]
  felems    :: (Cell a) => Form a b -> [b]
   
  fmap      :: (Cell a) => (b -> c) -> Form a b -> Form a c
  fmapi     :: (Cell a) => (a -> b -> c) -> Form a b -> Form a c
  fzipWith  :: (Cell a) => (b -> c -> d) -> Form a b -> Form a c
                                                     -> Form a d
\end{verbatim}
Most of these are fairly self-explanatory generalisations of similarly-named
Haskell prelude functions.  A possible implementation of them
is given in appendix \ref{formLibrary}.  Use of those
definitions requires an instance of the cell class.  An example
instance is given in appendicix \ref{cellInstance}.

     \verb$(!#)$ is the infix subscripting operation on a form, so
if \verb$a$ is a form and \verb$c$ is a cell of the right type and
dimension, \verb$a !# c$ is the corresponding element of \verb$a$.
\verb$lattice$ and \verb$rank$ generalise the standard \verb$bounds$
function, returning the lattice and rank of a given form.
\verb$accumForm$ is similar to \verb$form$ but the requirement
of one association for every cell is relaxed---the result is
a form containing for each cell a list of all values the association
list binds to that cell.
\verb$fmap$ is a straightforward
mapping function.  \verb$fmapi$ is similar, but the mapping function
is passed an extra argument, the cell on which
the function map is being applied.  \verb$fzipWith$ is similar
to the \verb$zipWith$ function on lists.  It takes two conforming
forms and produces a third by applying the zipping function
at each cell.

\subsection{\label{latticeTopology}Lattice topology}

     The final and most interesting ingredient is the \verb$boundary$
operation.

     A powerful way of representing the topology of a cell complex
is through its {\em incidence function}.  This is a function $I$
from pairs of cells to the set $\{-1, 0, +1\}$.  Its value is
non-zero only when the cell pair is of the form $(c^{(r)}, c^{(r - 1)})$,
where $c^{(r)}$ is an $r$-dimensional cell, and $c^{(r - 1)}$
is an $(r-1)$-dimensional cell, {\em and $c^{(r - 1)}$ is on the
boundary of $c^{(r)}$}.  When it is non-zero, its value is $+1$ or
$-1$ according to whether $c^{(r - 1)}$ is positively or negatively
oriented on the boundary of $c^{(r)}$.  Orientation is easier to
grasp through pictures than by formal definition---see
figure \ref{incidence}.
\begin{figure}[hbt]
\centerline{
\begin{picture}(220, 130)(-20, -30)
\multiput(-10,  0)( 0, 40){3}{\line(1, 0){100}}
\multiput( 0, -10)(40,  0){3}{\line(0, 1){100}}
%
\put(40, 80){\circle*{6}}
\put(30, 84){$H$}
\put(80, 80){\circle*{6}}
\put(84, 70){$G$}
\put(45, 80){\rule[-1pt]{30pt}{3pt}}
\put(57, 70){$F$}
%
%\put(5,  5){\rule{30pt}{30pt}}
\put(5,  5){\rule{10pt}{30pt}}
\put(5,  5){\rule{30pt}{10pt}}
\put(5, 26){\rule{30pt}{10pt}}
\put(26,  5){\rule{10pt}{30pt}}
\put(17, 17){$A$}
%
\put(5,  0){\rule[-1pt]{30pt}{3pt}}
\put(17, -10){$B$}
\put(5, 40){\rule[-1pt]{30pt}{3pt}}
\put(17, 44){$D$}
\put(-1,  5){\rule{3pt}{30pt}}
\put(-10, 17){$E$}
\put(39,  5){\rule{3pt}{30pt}}
\put(44, 17){$C$}
%
\put(100, 110){
\begin{minipage}[t]{2in}
\begin{eqnarray*}
I (A, B) & = & +1 \\
I (A, C) & = & +1 \\
I (A, D) & = & -1 \\
I (A, E) & = & -1 \\
I (F, H) & = & -1 \\
I (F, G) & = & +1 \\
I (A, F) & = & 0 \\
I (B, H) & = & 0
\end{eqnarray*}
\end{minipage}
}
\end{picture}
}
\caption{\label{incidence}Example values of the incidence function on a 2d lattice.}
\end{figure}
In the figure the conventions are adopted that the links are directed
from left to right or from bottom to top, and the boundary of
a plaquette is oriented anti-clockwise around the square.
So, for example, link $B$ has positive incidence on plaquette $A$,
because it follows the direction of the boundary path, whereas $D$ has
negative incidence because it is directed left to right while
the top boundary of $A$ goes right to left.  For the incidence
of a site on a link, the convention is that it is positive
if the link is directed in to of the site, and negative if it
is directed out of the site\footnote{Reversing any of these conventions on
orientation may change local signs in the incidence function, but {\em not} the
final, scalar results of computations.}.

     Now the \verb$boundary$ function,
\begin{verbatim}
  boundary  :: (Cell a, Num b) => Lattice a -> a -> [Assoc a b],
\end{verbatim}
applied to an $r$-cell \verb$c$
returns the list of $(r-1)$-cells on the boundary of that cell,
paired with the incidence function of the boundary cell on \verb$c$.
Taking examples in figure \ref{incidence}:
\begin{tabbing}
\verb$  $\= \kill
\>\verb$boundary l $$A$\verb$ = [$$B$\verb$ := 1, $$C$\verb$ := 1, $$D$\verb$ := -1, $$E$\verb$ := -1]$ \\
\>\verb$boundary l $$F$\verb$ = [$$H$\verb$ := -1, $$G$\verb$ := 1]$ \\
\>\verb$boundary l $$H$\verb$ = []$
\end{tabbing}
where \verb$l$ is the associated lattice data structure.
The result for $H$ is empty, because by convention 0-cells
have no boundary.
(There is no huge significance in the choice of \verb$Assoc$
pairs as the result of \verb$boundary$.  In principle, any type capable of
representing a cell and a numeric object would do.)
Appendix \ref{topologyExample} shows how a particular lattice
topology can be set up---defining an instance of the
\verb$boundary$ function.

     The \verb$boundary$ operation probably looks a bit contrived
at first sight.  The idea comes from homology \cite{topology}.
As the examples in the next section show, it is a convenient
practical method of encoding the shape of a lattice.

    To close this section we record a couple more functions which will be
used later, and which occur frequently in other applications of the
``form'' technology introduced above.  First, a function which
``contracts'' a form on an association list containing cells and values
of the same type:
\begin{verbatim}
  cntrct :: (Cell a, Num b) => Form a b -> [Assoc a b] -> b
  cntrct a c = sum [v * (a !# j) | j := v <- c]
\end{verbatim}
(This is a sort of scalar product between a form and an association
list).

    Second, \verb$mltply$ multiplies all values
in an association list by its first argument.
\begin{verbatim}
  mltply :: (Cell a, Num b) => b -> [Assoc a b] -> [Assoc a b]
  mltply m ivs = [i := m * v | i := v <- ivs]
\end{verbatim}

