在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")。注意，我们使用逗号分隔元组的参数。

在您的示例中，type ('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)具有特殊的语义，因为以下定义了具有四个参数（键，值，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 |
  +--------+

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