From concrete data types to abstract data types, revisited

With its modules, OCaml provides language support to specify abstract data types.

Example: lists of integers as an abstract data type

For example, we could specify lists of integers as an abstract data type with a special value – the empty list (call it nil) – and with operators:

• is_nil: a predicate deciding whether its argument is the empty list of integers;
• equal: a predicate that, given two lists of integers, determines whether these two lists are equal;
• cons: a function that, given an integer and a list of integers, returns the list whose head is this given integer and whose tail is this given list of integers; and
• car and cdr that, when applied to a non-empty list of integers, respectively return its head and its tail.

Here is the signature of a module that implements these lists of integers:

module type INT_LIST =
  sig
    type int_list
    val nil : int_list
    val is_nil : int_list -> bool
    val equal : int_list -> int_list -> bool
    val cons : int -> int_list -> int_list
    val car : int_list -> int option
    val cdr : int_list -> int_list option
  end;;

Here are the properties we expect these lists to satisfy:

• is_nil should recognize the empty list as such;
• is_nil should recognize a non-empty list as such;
• the empty list should be equal to itself;
• any list should be equal to itself;
• any two distinct lists should be recognized to not be equal;
• applying car and cdr to the empty list should yield an undefined result;
• applying car and cdr to a non-empty list should respectively yield their head and tail.

Let us write a unit-test function that captures these properties:

let test_int_list nil is_empty equal cons car cdr =
  let b0 = (is_empty nil = true)
  and b1 = (is_empty (cons 2 nil) = false)
  and b2 = (equal nil nil = true)
  and b3 = (equal (cons 1 nil) nil = false)
  and b4 = (equal nil (cons 2 nil) = false)
  and b5 = (equal (cons 1 nil) (cons 2 nil) = false)
  and b6 = (equal (cons 1 nil) (cons 1 nil) = true)
  and b7 = (equal (cons 2 (cons 1 nil)) (cons 2 (cons 1 nil)) = true)
  and b8 = (car nil = None)
  and b9 = (car (cons 1 nil) = Some 1)
  and b10 = (match car (cons 1 nil) with
             | None ->
                false
             | Some n ->
                n = 1)
  and b11 = (match cdr (cons 2 (cons 1 nil)) with
             | None ->
                false
             | Some ns ->
                equal ns (cons 1 nil))
  (* etc. *)
  in b0 && b1 && b2 && b3 && b4 && b5 && b6 && b7 && b8 && b9 && b10 && b11;;

A first implementation: native lists

Let us first implement lists of integers as native OCaml lists of integers:

module Int_List_native : INT_LIST =
  struct
    type int_list = int list

    let nil = []

    let is_nil is =
      is = []

    let equal is js =
      is = js

    let cons i is =
      i :: is

    let car is =
      match is with
      | [] ->
         None
      | i :: _ ->
         Some i

    let cdr is =
      match is with
      | [] ->
         None
      | _ :: is' ->
         Some is'
  end;;

This implementation passes the unit test:

# test_int_list Int_List_native.nil
                Int_List_native.is_nil
                Int_List_native.equal
                Int_List_native.cons
                Int_List_native.car
                Int_List_native.cdr;;
- : bool = true
#

A second implementation: a left-to-right representation

Let us implement lists of integers with a list-like OCaml data type that links from left to right:

module Int_List_l2r : INT_LIST =
  struct
    type int_list =
      | Nil
      | Cons of int * int_list

    let nil = Nil

    let is_nil is =
      is = Nil

    let equal is js =
      is = js

    let cons i is =
      Cons (i, is)

    let car is =
      match is with
      | Nil ->
         None
      | Cons (i, _) ->
         Some i

    let cdr is =
      match is with
      | Nil ->
         None
      | Cons (_, is') ->
         Some is'
  end;;

This second implementation also passes the unit test:

# test_int_list Int_List_l2r.nil
                Int_List_l2r.is_nil
                Int_List_l2r.equal
                Int_List_l2r.cons
                Int_List_l2r.car
                Int_List_l2r.cdr;;
- : bool = true
#

A third implementation: a right-to-left representation

Let us finally implement lists of integers with a list-like OCaml data type that links from right to left:

module Int_List_r2l : INT_LIST =
  struct
    type int_list =
      | Nil
      | Cons of int_list * int

    let nil = Nil

    let is_nil is =
      is = Nil

    let equal is js =
      is = js

    let cons i is =
      Cons (is, i)

    let car is =
      match is with
      | Nil ->
         None
      | Cons (_, i) ->
         Some i

    let cdr is =
      match is with
      | Nil ->
         None
      | Cons (is', _) ->
         Some is'
  end;;

This third implementation also passes the unit test:

# test_int_list Int_List_r2l.nil
                Int_List_r2l.is_nil
                Int_List_r2l.equal
                Int_List_r2l.cons
                Int_List_r2l.car
                Int_List_r2l.cdr;;
- : bool = true
#

Summary and conclusion

Modules and signatures provide language support to specify abstract data types. What each module does is consistent with the signature and can be measured with the unit tests. How each module implements the abstract data type is private to its implementer.

Resources

• The complete OCaml code for the present lecture note (latest version: 24 Mar 2020).

Version

Created [02 Apr 2019]