minh thu
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.