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

通过priority_queue在定义时使用Node,我们说左右儿童可能是一个Leaf或另一个Node.|在构造函数的定义中不需要任何浮动.

编辑

如果您希望将不同类型的构造函数的名称彼此分开,则可以使用模块.一个快速的谷歌搜索产生了这个页面(具有讽刺意味)打开了优先队列示例.特别是,这是一个简单的模块,包括你的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)