
\section{Introduction}

     Lazy functional languages have not, to date, made an enormous
impact in scientific computing.  Partly, this has to do with
performance---codes written in these languages often run an order of
magnitude slower than imperative codes, which limits their appeal for
number-crunching production codes\footnote{It seems that this caveat on
functional programming no-longer holds for some non-lazy functional
language---see \cite{scientific3}.}.  Apart from that, there is a
suspicion that programming without assignments or side-effects is
difficult, or restrictive.  Evidently, this is not the opinion of
functional programmers---but perhaps there are things in scientific
computation really cannot 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 should not 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,
complex numbers, and a rough grasp of probability distributions.
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 to introduce a kind of generalised array, with more
geometric significance.  Section \ref{lattices} describes the approach
taken to lattice geometry, and the arrays defined on these lattices.
The appendices give details of a possible Haskell implementation of the
generalised arrays and operations on them.

     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 naturally and is quite efficient in a lazy
language, especially for algorithms with some ``locality of
reference''.

     Finally, some conclusions are collected in section \ref{discussion}.

     We chose to handle the lattices in a rather abstract way.
The result is that the geometry factors out from the problems
in an attractive 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 does not {\em enforce} this level of abstraction.
It does enable it.

