В OCaml как вы отличаете * от,? - PullRequest
Новая
       16

В OCaml как вы отличаете * от,?

2 голосов
/ 05 июля 2019

Я пытаюсь реализовать дерево с кортежами ключ-значение. Я пробовал следующее вместе со многими вариантами замены * на , и наоборот. 

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;;

При этом он говорит, что конструктор дерева принимает два аргумента, но если я изменяю * на , в конструкторе, я получаю неописанную ошибку. Я не очень ясно, когда использовать какой, и я предполагаю, что это источник ошибки. Я знаю, что вы делаете конкретные экземпляры кортежей с запятой и определения типов, которые построены с кортежами со звездой. Но здесь не всегда понятно, что есть что, или если на самом деле какое-то другое правило действует.

1 Ответ

7 голосов
/ 05 июля 2019

Символ * используется для разделения элементов кортежа в определениях типов данных. Символ , используется для разделения переменных типа в параметрическом типе, который имеет более одной переменной.

Например, в Student of name * age * class мы определяем конструктор с тремя аргументами. Чтобы создать значение с помощью этого конструктора, мы передаем аргументы в виде кортежа Student ("Jon",21,"CS"). Обратите внимание, что мы использовали запятую для разделения аргументов кортежа.

В вашем примере тип ('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) будет храниться в коробочном представлении, вне дерева. Или графически 1 , 

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

...