Abstract data structure type

Learning
4

If you wanted to implement a non-imperative stack, is there any way of keeping the underlying data structure abstract just using records? Or would you need to use modules for this one way or another?

Two nice features of specifying and implementing ADTs in modules, which I don’t think you can get out of records:

  • Structural sub-typing that lets implementations of richer specifications satisfy simpler ones
  • The related ability to quickly construct and extend structures and signatures by inclusion

Here’s an example:

(* Given a minimal (imperative) stack interface, which is a substructure of the interface exposed by Stdlib *)
module type Stack = sig
  type 'a t
  val create : unit -> 'a t
  val is_empty : 'a t -> bool
  val push : 'a -> 'a t -> unit
  val pop : 'a t -> 'a
end

(* We can specify a Deque interface the basis of the specification for the Stack  *)
module type Deque = sig
  include Stack
  val pop_back : 'a t -> 'a
  val push_back : 'a -> unit
end

(* Now, let's assume we have some code that needs a stack *)
module NeedsStack (S : Stack) = struct
  (* Does some stuff with the stack *)
end

(* And then suppose we are in an environment where we are given something implementing Dequeu *)
module Example (D: Deque) = struct
  (* We can use our Deque where a Stack is needed *)
  module M = NeedsStack (D)

  (* Also, Stdlib's Stack satisifies our interface *)
  module M' = NeedsStack (Stdlib.Stack)

  (* We can define a new stack on top of the Deque *)
  module AltStack : Stack = struct
    include D
    (* But we can change what pop means *)
    let pop = failwith "Unimplemented"
  end

  module M'' = NeedsStack (AltStack)
end

I find the connections between records and modules is neat, and kind of profound. I think Rossberg’s 1-ML paper paper is a very fun exploration of the connections. More knowledge folks around these parts can likely recommend other resources.

2 Likes