2 - Data Structures

Summary

Programs have to handle highly varied objects organized into categories, such as numbers, text, images, formulas, as well as other programs. These objects are for the most part foreign to the world of programming and involve quite diverse formal systems.

For each such category of objects, the programmer must define a representation in the objects of the programming language that he or she is using. This representation must satisfy criteria such as efficiency (by exploiting what the programmer has learned about algorithms) and clarity; that is, the way the data is structured should reflect the structure of the objects being represented. Representation of objects from the exterior world should not be some obscure encoding; rather, the conceptual, external structure should remain apparent.

In a typed language like Caml, the nature of an object lies in its type. It is thus natural to ask that the external structure of the objects being handled should be reflected in the types of their internal representation. For that purpose, the programmer must have the means to define a great variety of types.

In this chapter, we present the two principal type constructions that Caml offers: records and sums with constructors. You might think of a record as the product of named components, and a sum as the union of named components.

Record or Named Cartesian Products

Let's assume that we want to write programs working on complex numbers. We can imagine representing complex numbers by pairs (r,i) of type (float * float) giving the real and imaginary parts of such numbers.