Can contiguous arrays be lazily evaluated?

Question

Contiguous arrays with variable length, such as C++'s std::vector, have been a major sequential container for languages whose evaluation is eager. However, it has been commonly considered that contiguous arrays do not mix well with lazy evaluation. Indeed, Arrays that Haskell provides are strictly evaluated for its entries. Not to mention that strictly evaluated arrays cannot have infinitely many entries, unlike lazily evaluated lists can.

Yet I don't think arrays cannot be lazily evaluated anyway. I aimed to build a datastructure that can represent infinitely many entries like lazily evaluated lists can, while still being randomly accessible. To give a sketch, I think such datastructure can be implemented as cached lists. That means, the datastructure could consist of a strictly evaluated array and a lazily evaluated linked list, where the strict array acts as caches for already identified entries, and where the lazy list contains unevaluated entries. This should give amortized random access.

Yet still, I don't think Haskell can do this natively. All memory allocation/deallocation operations that Haskell provides are bound within the IO monad. If the idea above can be implemented in our machines anyway, I would conclude that this is just language design fault of Haskell. So can contiguous arrays be lazily evaluated anyway? If so, what programming languages do have that?

Answer 1

Haskell supports immutable arrays in the obvious way. This is an extremely useful data structure when used in conjunction with lazy evaluation, because you can store unevaluated thunks in the array which get evaluated at most once when you read them.

Many dynamic programming algorithms become much simpler when you implement them this way, but there are also exotic uses such as hash consing (akin to the flyweight pattern in OOP). Haskellers sometimes to refer to this technique as memoising CAFs, since an immutable array is a constant applicative form.

For mutable arrays, there are essentially two possibilities: persistent and non-persistent.

Non-persistent mutable functional arrays store updates so they can be undone to get to a previous point in time. This is more common in logic languages, since they have a notion of backtracking.

Persistent functional arrays give you the best of all worlds: arbitrary updates, and they don't alter existing arrays. Of course, something has to give, and that means either storage (e.g. copying the whole array on every update; the standard library of Mercury has a slow_set operation which does this) or access time complexity (e.g. representing the array as a binary tree).

However, there is a middle-ground. What you might like is for the array to have:

• $O(n)$ initialisation time
• $O(1)$ read time on the original array
• $O(1)$ (amortised?) modification time
• $O(\log k)$ read time on a modified array, where $k$ is the number of modified array entries since initialisation

The idea here is that you start with an array, but it slowly turns into a tree as it gets modified. Something like ropes will do this. The idea is to implement a binary tree whose leaves are either a new entry, or a sub-range of the original array.