With the type programming construct, OCaml provides language support for specifying data types, i.e., types with constructors. For example, the type of Booleans comes with the two constructors true and false, the type of lists comes with the a constructor for the empty list (traditionally referred to as “nil”), and a constructor for non-empty lists (traditionally referred to as “cons”), the type of binary trees comes with a constructor for leaves and a constructor for nodes, etc. These data types are said to be concrete.
In contrast, an abstract data type is not specified with constructors, but with operators that must satisfy some algebraic laws. The only way to manipulate values of that type is through these operators. This abstractness make it possible for programmers to devise a variety of implementations, with the only constraint that each of the implementations satisfies the algebraic laws. In short, abstract data types make it possible to separate the what and the how of a representation, i.e., what is being represented, and how it is represented.
The following lecture notes describe two such abstract data types: environments and queues.
Created [24 Mar 2020]