Abstract Types

StackSig signature

module type StackSig = sig
  type 'a stack
  
  exception Empty
  val empty : 'a stack
  val is_empty : 'a stack -> bool
  val push : 'a -> 'a stack -> 'a stack
  val peek : 'a stack -> 'a
  val pop : 'a stack -> 'a stack
  val size : 'a stack -> int
end

ListStack Impl

module ListStack : StackSig = struct
  type 'a stack = 'a list
  exception Empty
  let empty = []
  let is_empty = function [] -> true | _ -> false
  let push x s = x :: s
  let peek = function [] -> raise Empty | x :: _ -> x
  let pop = function [] -> raise Empty | _ :: s -> s
  let size = List.length
end

Since the StackSig signature only exposes type 'a stack, even though in ListStack internally uses 'a list as underlying data structure, external users can only see 'a stack and 'a list is hidden from users. Thus we can accept the first and reject the second, which provides safety from explicit construction.

(* Accept *)
let s1 : int ListStack.stack = ListStack.(empty |> push 42)

(* Reject *)
let s2 : int ListStack.stack = [42]

So here, type 'a stack is abstract. There’s only declaration but no definition.