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.Нет необходимости в |, плавающем внутри определения конструктора.

Редактировать

Если вы хотите, чтобы имена конструкторов для разных типов были отделены друг от друга, вы можете использоватьмодулей.Быстрый поиск в 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 - это реализация очередей с приоритетами, тип данных которых похож на ваш, - куча приоритетов.

Для введения втипы сумм, их синтаксис и некоторые примеры, см. объявления типов и сопоставление с образцом в превосходной онлайн-книге Разработка приложений с Objective Caml .