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 ?
Do you mean "computer science"?-) Much of this field could be rephrased as the search for better representations, to enable better implementations of algorithms (for some measure of "better"): do we represent programs as data structures to be interpreted, or as code to be executed? do we use sets, lists, arrays, ..? how do we represent sets/lists/arrays/..? do we recompute properties of data, or do we store them (and is one better always, or sometimes, and when? or do we need to optimize for the average or the most common case? how do we define "better", anyway?)? which are the options, for a particular application domain, or a general class of data structure/algorithm, and how do they compare? and so on.. But if you limit your question sufficiently, you might have some luck looking for papers that reference any of these: Automatic data structure selection: an example and overview, James R. Low, Communications of the ACM, 1978 http://portal.acm.org/citation.cfm?id=359488.359498 Techniques for the automatic selection of data structures Low, Rovner, 3rd POPL, 1976 http://portal.acm.org/citation.cfm?id=811540 Rovner, P. Automatic representation selection for associative data structures. Ph.D. Th., Harvard U., Cambridge, Mass; Tech. Rep. TR10, U. of Rochester, Rochester, N.Y., Sept. 1976. Claus