A Framework for the Recursive Definition of Data Structures

Jean-Louis Giavitto

To appear at the 2nd International Conference on Principles and Practice of Declarative Programming (PPDP 2000), Montreal, Canada, September 20-22, 2000


Functional languages allow the definition of a function by means of recursive equations. This paper describes a general framework to extend this approach to data structures.

Our main objective is to avoid partial definitions and the lazy evaluation strategy (as it is the case in {Haskell}). Our first task is to develop the concept of data structure and sub-structure in a general setting. Then we characterize an evaluation strategy which preserves the structure of the data set and we present a sufficient condition for a definition to be total (each element of the data structure has a definite value) and computable by this strategy.

Using the framework, we fully develop the special case of vectors. In addition, we provide an explicit syntactic condition to check if a recursive vector definition is total and computable by a simple iterative loop.