ocaml - 使用 Make 语法在 OCaml 中定义自己的数据结构

Question

在尝试从 OCaml 中的纯功能数据结构实现练习时，我不确定如何创建解决方案的实例。

假设我有以下代码:

    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

我想提供一个类似于 Set.Make(String) 的 Make 函数来创建一个专门的实例。但我不确定该怎么做。

Answer 1

在我看来，通过顺序概念对集合进行参数化是很自然的(或者你可以只用相等来逃避)。但是不需要以这种方式对堆栈进行参数化；也就是说，它不依赖于秩序或平等的概念。它仅取决于其结构的代数性质。

您已经有了一个参数多态模块，可用于制作任何类型对象的堆栈。

我正在查看 Set 模块的代码。如果你想制作一个像 Set.Make 这样的仿函数，你需要一个元素的模块类型。因为您可以使用任何类型(不像 Set，它需要一个有序的类型)，您可以使用这样的东西:

module type AnyType = struct type t end

那么你的仿函数可能看起来像这样(同样，我只是从 Set 模块复制代码):

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

更新

如果您只想按原样试用您的堆栈代码，您可以开始使用它:

$ 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
#