为什么在皇后那里定义类型？

Question

代码格式《程序员的ML》第7.1章：

structure Queue1 =
struct
  type 'a t = 'a list
  exception E 

  val empty = []

  fun enq(q, x) = q @ [x]

  fun null(x::q) = false
    | null _ = true

  fun hd(x::q) = x
    | hd [] = raise E 

  fun deq(x::q) = q 
    | deq [] = raise E
end

上面的代码完全是书上的（省略;）。我和要测试的代码：

val a = Queue1.enq(Queue1.empty, 1)
val b = Queue1.enq(a, 2)
val c = Queue1.enq(b, 3)

fun main() = map PolyML.print c

而且效果很好。

如果我省略类型定义行：

(* type 'a t = 'a list *)

它也很好用！

那为什么要写类型定义呢？似乎只需要一个空列表 [] 作为初始列表。谢谢！

Answer 1

继续阅读您的书。第 7 章的标题是“抽象类型和函子”，这应该是您所看到的 type t 符号的原因的线索。

非常简短的入门指南：函数将一个值映射到另一个值。仿函数对模块做同样的事情。

假设我们想要“构建”一个 BinaryTree 可以存储特定类型值的模块。我们需要知道类型，还需要知道如何比较该类型的两个值。我们可以创建一个反映该数据的签名。

datatype cmp = Eq | Lt | Gt

signature TREE_VAL_TYPE =
sig
  type t
  val compare : (t * t) -> cmp
end

然后我们的BinaryTree仿函数：

functor BinaryTree (S : TREE_VAL_TYPE) =
struct
  datatype tree = Empty | Node of S.t * tree * tree

  fun insert(existingTree, value) =
    (* Use S.compare to insert the value into a tree *)
end

现在当我想创建一个包含整数的树时：

structure IntModule =
struct
  type t = int

  fun compare(a, b) =
    if a = b then Eq
    else if a < b then Lt
    else Gt
end

structure IntTree = BinaryTree(IntModule)

现在向这样的树中添加一个值可能如下所示：

IntTree.insert(IntTree.Empty, 42)

为什么在皇后那里定义类型？

Why there define the type in the queen?

sml