Define own data structures in OCaml using Make syntax

Question

In attempting to implement the exercises from Purely Functional Data Structures in OCaml I'm not sure how I can create instances of my solutions.

Say I have the following code:

    module type Stack =
      sig
        type 'a t
        val empty   : 'a t
        val isEmpty : 'a t -> bool
        val cons    : 'a -> 'a t -> 'a t
        val head    : 'a t -> 'a
        val tail    : 'a t -> 'a t
    end

    (* Implementation using OCaml lists *)
    module MyStack : Stack = struct
      type 'a t = 'a list

      exception Empty

      let empty = []
      let isEmpty l =
        match l with
        | [] -> true
        | _  -> false

      let cons x l = x :: l

      let head l =
        match l with
        | h :: _ -> h
        | [] -> raise Empty

      let tail l =
        match l with
        | _ :: r -> r
        | [] -> raise Empty
    end

I want to provide a Make function similar to Set.Make(String) for creating a specialised instance. But I'm not sure how to do that.

Answer 1

Seems to me it's natural to parameterize a set by a notion of order (or you could get away with just equality). But a stack doesn't need to be parameterized in that way; i.e., it doesn't depend on a notion of order or equality. It just depends on algebraic properties of its structure.

You already have a parametrically polymorphic module that can be used to make a stack of any type of object.

I'm looking at the code for the Set module. If you want to make a functor like Set.Make, you need a module type for the elements. Since you can use any type at all (unlike Set, which needs an ordered type), you could use something like this:

module type AnyType = struct type t end

Then your functor might look like this (again, I'm just copying code from the Set module):

module Make(Any: AnyType) =
    struct
    type elt = Any.t
    type t = elt list
    ...
    end

Update

If you just want to try out your stack code as is, you can just start using it:

$ ocaml
        OCaml version 4.01.0

# #use "mystack.ml";;
module type Stack =
  sig
    type 'a t
    val empty : 'a t
    val isEmpty : 'a t -> bool
    val cons : 'a -> 'a t -> 'a t
    val head : 'a t -> 'a
    val tail : 'a t -> 'a t
  end
module MyStack : Stack
# let x = MyStack.cons 3 MyStack.empty;;
val x : int MyStack.t = <abstr>
# MyStack.head x;;
- : int = 3
#