##
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

### Abstract

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.