syntax - 在 OCaml 中，你如何区分 * 和 ,？

Question

我正在尝试用键值元组实现一棵树。我尝试了以下方法以及将 * 替换为 , 的许多变体，反之亦然。

type ('k,'v) tree =
  | Leaf
  | Node of ('k*'v) * ('k*'v) tree * ('k*'v) tree;;

module type Dictionary = sig 
  type ('k,'v) t
  val empty : ('k,'v) t
end;;
module TreeDict : Dictionary = struct 
  type ('k,'v) t = ('k*'v) tree
  let empty = Leaf
end;;

它说树构造函数有两个参数，但是如果我在构造函数中将 * 更改为 , 我会得到一个非描述性错误。我不太清楚什么时候使用哪个，我猜这就是错误的根源。我知道您使用逗号创建元组的特定实例，并使用带星号的元组构造类型定义。但是这里并不总是很清楚哪个是哪个，或者实际上是否有其他规则在起作用。

Answer 1

* 符号用于分隔数据类型定义中的元组元素。 , 符号用于分隔具有多个变量的参数类型中的类型变量。

例如，在 Student of name * age * class 中，我们定义了一个具有三个参数的构造函数。要使用此构造函数创建值，我们将参数作为元组 Student ("Jon",21,"CS") 传递。请注意，我们使用逗号分隔元组的参数。

在您的示例中，类型 ('k,'v) tree 是参数化的，具有两个类型变量。因此，我们需要始终引用它，就像这样(不是 ('k * 'v) tree，而是 ('k,'v) tree)。

正确的定义应该是这样的

type ('k,'v) tree =
  | Leaf
  | Node of 'k * 'v * ('k,'v) tree * ('k,'v) tree

请注意，('k * 'v) 两边的括号具有特殊的语义，因为下面定义了一个具有四个参数 (key,value,lhs,rhs) 的构造函数，

  | Node of 'k * 'v * ('k,'v) tree * ('k,'v) tree

而下面

  | Node of ('k * 'v) * ('k,'v) tree * ('k,'v) tree

定义一个具有三个参数的构造函数，例如，Node (data,lhs,rhs)，其中data表示为(key,value) 对。具有 3 个参数的表示将使用更多内存，因为每个 (key,value) 对将存储在树外部的盒装表示中。或者图形化¹,

  4 arguments              3 arguments
  representation           representation 
  (5 words/node)           (7 words/node)

  +--------+               +--------+
  | header |               | header |
  +--------+               +--------+     +--------+
  |  key   |               | data   |---->| header | 
  +--------+               +--------+     +--------+
  |  value |      vs.      | left   |     |   key  |
  +--------+               +--------+     +--------+
  |  left  |               | right  |     | value  |
  +--------+               +--------+     +--------+
  |  right |
  +--------+

---

¹⁾ 在实际实现中，data 指针实际上将指向 key，即指向装箱值的第一个字段，但我认为从概念上讲，最好忽略此实现细节。