
\section{Introduction}

     Lazy functional languages haven't, to date, made an enormous
impact in scientific computing.  Partly, this has to do with
performance---codes written in these languages usually run an
order of magnitude (or two) slower than imperative codes,
which limits their appeal for number-crunching production codes.
Apart from that, there is a suspicion that programming without
assignments or side-effects is difficult, or restrictive.
(Evidently, this isn't the opinion of functional
programmers---but maybe there's something peculiar lurking
in scientific computation which really can't be {\em done}
easily without assignments.)

     This article gives detailed Haskell implementations of
three ``scientific'' algorithms.  In order of increasing
complexity they are: solution of a partial differential equation
by the relaxation method; Monte Carlo simulation of a statistical
mechanics system; and a similar simulation of a lattice
gauge theory.  These problems are taken from theoretical
physics---a strongly mathematical discipline.  Functional
programming also has a very mathematical feel to it.
So it shouldn't be too surprising that these problems actually
come out rather neatly in a functional language.
(Other examples of scientific functional programming
can be found in \cite{scientific1,scientific2,scientific3}).

     Haskell is a relatively new language, put forward as
an international standard for functional programming \cite{haskell1,haskell2,
haskell3}.  It is a lazy, pure functional language.  Beyond that, the choice of
Haskell as a mode of expression in this article is fairly incidental---any
lazy functional language would probably have done as well.
Having chosen Haskell, however, free use has been made of its
more innovative features, including the array and
class systems (the latter for achieving overloading, or {\em ad hoc}
polymorphism, in the array manipulation functions we introduce).
A fair understanding of Haskell is probably a prerequisite
for reading this article.  By and large, the ``prelude''
functions of Haskell will be used without much comment,
so a Haskell reference may be necessary.

     Full understanding of the problems and algorithms described will
require a certain amount of mathematical knowledge---some
familiarity with simple partial differential equations,
differential operators like the gradient and Laplacian,
complex numbers, and a rough grasp of probability distributions.
I won't assume any detailed knowledge of the physics behind
the problems, but the footnotes fill in some details for those
who are interested.  Section \ref{problems} describes the systems involved
and the associated algorithms.  The problems are all based on lattices
(i.e., grids).  They make important use of arrays.

     Rather than work directly with standard Haskell arrays, it
proved convenient work with a kind of generalised array, with more
geometric significance.  Section \ref{lattices}
describes the approach taken to lattice geometry,
and arrays defined on these lattices.
The appendices give details of a possible Haskell implementation
of the generalised arrays and operations on them.
To further illustrate their use there is also an appendix containing
some examples based on finite-difference approximations to various
differential operators.

     I chose to handle the lattices in a rather abstract way, which
is why there's a whole section on geometry and generalised arrays.
The payoff is that the geometry factors out from the problems
in a nice way---the implementations in section \ref{implementations}
make almost no reference to the details of this geometry.
Abstraction certainly has dividends, but understanding
it also requires some investment of effort.  Needless to say,
Haskell doesn't {\em enforce} this level of abstraction.
It does enable it.

     The implementations of the main algorithms are given
in section \ref{implementations}.  The paradigm used in
each case is one of interacting parallel processes, modelled by
lazy lists (streams) representing the output of the processes.
Partly this choice can be attributed to the source of funding for this
work---the FAST project aims to provide
a parallel implementation of annotated functional programs written
in essentially this style \cite{fast1}.  Apart from that, the style
comes quite naturally and is reasonably efficient in a lazy
language, especially for algorithms with some ``locality of
reference''.

