Lambda the Ultimate

Regarding low-level data storage, no, at least for all sensible definitions that I can think of right now.

With lambdas you can do pairs, which enable you to build lists (arrays) and lists of lists (matrices).

Have a look at An exercise from the Wizard Book and Church encoding, to implement natural-number indices in pure lambda calculus.

Presumably you mean "can we have contiguous-memory storage of matrices and arrays which have constant time (i.e. not dependent on the size of the matrix) updates with a pure functional language?"

The implementation of a pure functional language can give you contiguous arrays and matrices. After all, having lists represented as linked lists of individually allocated memory cells is "just" an implementation detail (albeit one that seems pretty hard to avoid).

Your compiler could offer you a native contiguous matrix (or array) and represent updates to it with a small object linking to it. Then as you update it, processing the updated matrix gets slower and slower (because any access requires potentially checking all of these updates). Your compiler could give its garbage collector knowledge of these updates and merge them together when the older ones are no longer required, to regain speed.

Your compiler could, instead, sidestep the issue of keeping multiple versions around by keeping the matrix in a monad. A monad is a way of representing serialized operations on something, allowing the implementation to keep only one copy of the matrix (or allowing only explicit copies) and updating it with the series of operations. It is generally best to avoid monads with things like matrices, which would normally be considered normal value types though. Note that this monadic representation is not something you can actually implement in a functional programming language -- it has to be implemented in your compiler or in a non-functional language (or in lower-level monads); but the monad technique allows functional programs to access objects that are implemented in other languages and break the functional rule (i.e. no updates!).

Lambda calculus (along with several others) provides a means of specifying the meaning of a computation — where meaning is taken to mean "a mathemtically precise and unambiguous set of evaluation rules by which to determine the value resulting from a computation". In this view, to the extent that lambda calculus can simulate the behavior of arrays, yes, lambda forms can "do" things like arrays and matrices.

Usually, when people talk about arrays and matrices, they are concerned about representation. Representation is an important aspect of program efficiency and pragmatics. It is rarely relevant to the program's semantics — it becomes semantic when a particular representation becomes prescriptively required. Within the PL community, representation is universally considered to be independent of semantics. There exist lambda calculi that incorporate a notion of locations, but I'm not aware of any that deal with representation (nor should they).

The other issue people are concerned about with arrays and matrices is state. There are stateful lambda calucli, but the basic lambda calculus does not provide state. The trend in semantic calculi has been to avoid state altogether (as in Haskell), or push it to the "edge" of the semantics (as in ML) so that the semantic implications of state can be evaded. State makes a complete mess of the term substitution approach to program analysis, which makes it much more difficult to specify what a program means and how it behaves.