[Haskell-cafe] Re: compilation related questions

[minh thu]

2009/4/10 Achim Schneider <barsoap at web.de>:
> minh thu <noteed at gmail.com> wrote:
>
>> On a related note, I have another question. Say we have some data
>> structure, for instance a list, some functions on this data structure
>> (probably defined with some well known functions, such as map or
>> fold), and a program using them. Is there any research trying to
>> rewrite the program, and the data structure, to optimize them ?
>>
> Yes. The most advanced approach that I know of is Dons'
> stream-fusion[1]. I guess the technique of transforming a program so
> that Y-combinators are at their outermost possible position (and fused,
> in the process) could be generalised.
>
>> A contrived example is the length of a list : instead of traversing a
>> list to know its length, the list can have an additional field which
>> is incremented at each cons.
>>
> Well, that's not a list anymore, at least not with some additional
> ingenuity to deal with infinite ones. Statically-lengthed lists can be
> done with some type trickery, see e.g. [2], if that helps.

Oh, that's not what I meant by my question. My question is more about
the fact that the data structure can be augmented to include some
information which is computed while constructing the structure, not
afterward (to save an additional traversal).

Say you have an AST, with just the information after a parsing pass.
Then you compute 'derived' values at each node (maybe, I'm not sure if
it would be practical, type, strictness, ...). To do that, you can
have a function that, applied to any node, give the desired additional
information.

But for some functions, it can be seen clearly that such information
could have been constructed at the same time that the data structure.

So it is related to fusion techniques, but with the additional
possibility of adding fields to the original data structure.

Hope this makes sense,
Thu