# Applicative-order languages don't support constant time array writes? If not, why not?

I'm reading Steven Skiena's "The Algorithm Design Manual", and in one of his War Stories on page 155 he states:

Efficiency is a great challenge in Mathematica, due to its applicative model of computation (it does not support constant-time write operations to arrays) and the overhead of interpretation (as opposed to compilation).

I've already read SICP so I'm familiar with the difference between applicative and normal-order languages (i.e. that normal-order languages delay evaluation of procedure arguments until they're needed, whereas applicative-order languages evaluate them as soon as the procedure is called). But Skiena's sentence above appears to link the idea of applicative-order languages with the idea of worse-than-constant-time array writes. I don't remember Abelson and Sussman mentioning this in their text, so this came as a surprise.

If true, what are the under-the-hood reasons for why applicative-order languages don't write to arrays in constant time? Why would the order of evaluation matter in determining array write time?

I'm also curious what the Big-O write performance is in this case, but I imagine that depends on the language implementation, so I'll skip that question unless there's a definitive answer.

Skiena didn't say "applicative order", just "applicative". This is sometimes used as meaning something like "purely functional", or a language that evaluates via the application of functions as opposed to the execution of state manipulating commands. Mathematica (at least nowadays) isn't purely functional, but it does seem that it strongly encourages a purely functional style of programming.

In a purely functional language, such as Haskell, you apply functions to values and produce new values just as in mathematics. Like math, in such a language, variables are just names for values. If you say "let $x$ be $1$", then $x$ and $1$ are everywhere interchangeable. It makes no more sense to talk of "mutating" $x$ to be $2$ than it does to say to set $1$ to be $2$. For array this means that to "update" an array, you build a new array with the changes. Obviously, building an entire copy of an array except for the one entry you're changing is expensive. This is almost certainly the issue Skiena is referring to.

There is, to my knowledge, no fully satisfactory answer to this. That is, there is no purely functional data structure that provides constant time lookup and updates to all versions. You can make (externally) pure data structures that provide constant time lookup and update for the latest versions, but accesses to older versions of the array become slower. You can use monads or uniqueness types to enforce a usage of arrays that allows the compiler to use in-place updates, but this is tantamount to using an imperative approach (albeit in a controlled and contained manner). In practice, programmers in purely functional languages simply don't use arrays nearly as much as imperative programmers, and when they do use arrays, they tend to use bulk operations. If you are going to touch every element of an array anyway, then the cost of copying the array is constant per element.

While there are definitely times where the limitations of purely functional programming make efficient implementation non-obvious, most of the time it is just a matter of applying different design and implementation techniques than are typical/practical in imperative languages. Purity also affords guarantees that make many designs, optimizations, and sometimes entire technologies practical. For the first, most purely functional data structures are designed to share as much as possible. For the second, a major technique for improving performance of bulk operations is fusion which combines multiple bulk operations into one to avoid intermediates. For the last, there was an attempt to add Software Transactional Memory to C# that was given up because it relied on the programmer not using side-effecting procedures in the transactions but could not enforce this practically.

• Also, a tree data structure with a large fan-out is "practically constant". E.g. a 64-ary tree with 4 billion elements is at most 7 hops from the root to the leaf. That is 7 pointer lookups as opposed to 1 for an array. Not too bad. As Rich Hickey, the designer of Clojure, is fond of saying: Clojure's vectors are O(log_32 n), and the 32 is important, because for many practical problem sizes, constants do matter. O(log_X n) for X>30 is pretty darn close to O(1) for even very large n ~ billions. Aug 2 '18 at 8:24
• @JörgWMittag And even in an imperative world, O(1) array access is a small lie, since the hardware has to traverse O(log n) gates to access a memory cell. The RAM cost model conveniently postulates O(1) access, and we accept that only because it's close enough to practice (where we don't have zillions of bytes of memory, anyway).
– chi
Aug 2 '18 at 8:38
• @JörgWMittag: Perhaps I'm misunderstanding, but -- in a purely functional tree structure like you describe, a get would be 7 times as expensive, but an update would be 7x64 times as expensive, even discounting the cost of allocating all the new arrays. Unless the ratio of reads to writes is very high, that's not a trivial tradeoff. Aug 24 '18 at 0:26