[Haskell-cafe] compilation related questions

Claus Reinke claus.reinke at talk21.com
Fri Apr 10 18:12:41 EDT 2009

> 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

    Techniques for the automatic selection of data structures
    Low, Rovner, 3rd POPL, 1976

    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. 


More information about the Haskell-Cafe mailing list