What does FP do well? (was How to get ...)

[Bjorn Lisper]

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