Ocaml-如何将类型优先级队列定义为带有|的二叉树

Question

我试图将优先级队列定义为二叉树，但不断得到语法错误

    type 'a priority_queue = PriorityQueue of (Leaf | Node of 'a priority_queue * ('a*int) * 'a priority_queue)

当我这样做的时候，我得到一个错误

type 'a priority_queue = (PriorityQueue of Leaf) | (PriorityQueue of Node of 'a priority_queue * ('a*int) * 'a priority_queue) 

我如何定义这个?

Answer 1

我认为应该是

type 'a priority_queue =
| Leaf
| Node of 'a priority_queue * ('a * int) * 'a priority_queue

通过在定义Node时使用priority_queue，我们说左子和右子可以是Leaf或另一个Node。在构造函数的定义中不需要任何|浮动。

编辑

如果你想让不同类型的构造函数的名字彼此分开，你可以使用模块。在Google上快速搜索一下就会得到这个页面(讽刺的是)，它打开的是优先队列示例。特别是，这里有一个简单的模块，包括您的priority_queue类型(基于该链接的第一部分):

module PriorityQueue =
  struct
    type 'a priority_queue =
    | Leaf
    | Node of 'a priority_queue * ('a * int) * 'a priority_queue
  end

模块PriorityQueue作为其中声明的命名空间。因此，当您希望使用优先级队列时，可以这样写:

let leaf = PriorityQueue.Leaf
let pq = PriorityQueue.Node (PriorityQueue.Leaf, ("Hello from PriorityQueue", 1), PriorityQueue.Leaf)

当然，这太啰嗦了，所以为了方便，你可以先打开模块:

open PriorityQueue
let leaf = Leaf
let pq = Node (Leaf, ("Hello from PriorityQueue", 1), Leaf)

Answer 2

如果您感兴趣，OCaml手册中的一个示例是优先级队列的实现，其数据类型与您的类似——优先级堆。

关于sum类型的介绍，它们的语法和一些示例，请参见优秀的在线书籍《使用Objective - Caml开发应用程序》中的类型声明和模式匹配。