Jerzy:
Me:
...sometimes the length of a list being returned from a function can be a simple function of the function arguments (or the sizes of the arguments), think of map for instance. In such cases, a static program analysis can sometimes find the length function. If we know thee functions for all list-producing functions in a closed program, then the lists could be represented by arrays rather than linked structures.
I know Christoph Herrmann worked on such a program analysis some years ago. Also, I think Manuel Hermenegildo has done this for some logic language.
Andrew Appel wrote something about "pointer-less" lists as well.
What bothers me quite strongly is the algorithmic side of operations upon such objects.
Typical iterations map- (or zip-) style: do something with the head, pass recursively to the tail, would demand "intelligent" arrays, with the indexing header detached from the bulk data itself. The "consumed" part could not be garbage collected. In a lazy language this might possibly produce a considerable amount of rubbish which otherwise would be destroyed quite fast. The concatenation of (parts of) such lists might also have very bad behaviour.
Can you calm my anxiety?
No, since you're right. For instance, "stream"-type list computations, where list elements are used and then discarded, will not benefit from this kind of transformation. (They will be better optimized by deforestation.) List-to-array conversion will work best with computations where many different elements are used many times. Björn