functional-programming - 如何为树创建联合类型，在 OCaml 中它需要 'a 类型的键和 'b 类型的值？

Question

我希望创建一个bst（二叉搜索树）联合类型。

它是leaf或node。对于节点，它需要'a键和'b值。

我这样做了：

type 'a*'b bst = 
  | Node of 'a * 'b * ('a*'b) bst * ('a*'b) bst
  | Leaf;;

但它不起作用

我该怎么做？

Answer 1

您正在寻找的语法是：

# type ('a, 'b) bst =                              
      | Node of 'a * 'b * ('a,'b) bst * ('a,'b) bst
      | Leaf;;                                     
type ('a, 'b) bst = Node of 'a * 'b * ('a, 'b) bst * ('a, 'b) bst | Leaf

Answer 2

多参数多态类型的语法如下：

type ('a, 'b) bst = 
  | Node of 'a * 'b * ('a, 'b) bst * ('a, 'b) bst
  | Leaf;;

Answer 3

此外，由于'a需要比较运算符，您可能会遇到麻烦。这就是为什么在标准库中，Map和Set模块被实现为函子，以便可以指定比较顺序。

如果您决定采用'a多态方式，则必须使用“神奇”的默认比较运算符compare。

这个问题在 F# 中有所不同，因为有多种方法可以将比较运算符附加到类型。