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 _______________________________________________ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
