Under consideration for publication in J. Functional Programming 1 Embedding Quadtree Matrices in a Lazy Functional Language ∗

A technique for supporting quadtree matrices in a lazy functional langauge is presented that ameliorates tensions between performance and purity. In large matrix computations the facility to update in-place is a requisite for high performance. Thus, techniques for applying safe side effects to quadtree matrices are presented. Performance enhancements come via intrinsic properties of quadtree matrices, e.g., locality of reference. The expressiveness of quadtree matrix algorithms is enhanced by the tools of the higher-order, typed language, Haskell. Matrix-matrix multiply and Cholesky factorization are provided with time comparisons to C. In contrast to our earlier work, the protocol is convenient even for Fortran programmers and its performance scales nicely and compares well with Fortran enough to demonstrate that lazy languages can compete. Categories and Subject Descriptors: E.1 [Data Structures]: Arrays; D.3.2 [Programming Languages]: Language Classifications—concurrent, distributed, and parallel languages; applicative (functional) languages; D.4.2 [Operating Systems]: Storage Management—storage hierarchies; E.2 [Data Storage Representations]: contiguous representations