Using Hindley-Milner type inference to optimise list representation

1 January 1994

conference paper
Published by Association for Computing Machinery (ACM)

Vol. VII (3) , 162-172
https://doi.org/10.1145/182409.156781

Abstract

Lists are a pervasive data structure in functional programs. The generality and simplicity of their structure makes them expensive. Hindley-Milner type inference and partial evaluation are all that is needed to optimise this structure, yielding considerable improvements in space and time consumption for some interesting programs. This framework is applicable to many data types and their optimised representations, such as lists and parallel implementations of bags, or arrays and quadtrees.

Keywords

INTERESTING PROGRAM
PERVASIVE DATA STRUCTURE
PARALLEL IMPLEMENTATION
DATA TYPE
FUNCTIONAL PROGRAM
HINDLEY-MILNER TYPE INFERENCE
TIME CONSUMPTION
OPTIMISED REPRESENTATION
LIST REPRESENTATION
CONSIDERABLE IMPROVEMENT
PARTIAL EVALUATION
DATA STRUCTURE
TYPE INFERENCE
FUNCTIONAL PROGRAMMING

This publication has 0 references indexed in Scilit: