[Haskell-cafe] Re: compilation related questions

[Achim Schneider]

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.


[1] http://www.cse.unsw.edu.au/~dons/papers/CLS07.html
[2] http://article.gmane.org/gmane.comp.lang.haskell.general/13561

-- 
(c) this sig last receiving data processing entity. Inspect headers
for copyright history. All rights reserved. Copying, hiring, renting,
performance and/or quoting of this signature prohibited.