Контейнеры внутри записей в Ocaml

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

struct A {
name: string;
neighbors: Set of String;
};

Но я не могу создать контейнер Set внутри записи в Ocaml. Учитывая, что Set — это функтор, а не традиционный тип, я не уверен, как это можно сделать.


containers ocaml records
person mahesh prabhu    schedule 03.02.2012    source источник

Ответы (2)


arrow_upward
5
arrow_downward

Set — это функтор, который создает экземпляр нового типа для каждого типа набора, который вы хотите; поскольку ему нужно знать функцию сравнения, вы не можете сделать string set так, как вы можете string list (если только вы не используете PSet, полиморфный набор из Batteries Included или extlib). Так:

module StringSet = Set.Make(String);; (* or use BatSet.StringSet *)
type record = {
    name: string;
    neighbors: StringSet.t;
};

С полиморфными наборами Batteries (будьте осторожны с этим, так как он не проверяет, что вы используете одну и ту же функцию сравнения):

type record = {
    name: string;
    neighbors: string BatSet.t
};
person Michael Ekstrand    schedule 03.02.2012

arrow_upward
2
arrow_downward

Вам нужно понимать разницу между, например, «списком строк» ​​и «набором строк», который вы хотите построить.

Для списков типом является «список», потому что вам не нужно ничего знать о содержании списка, чтобы построить список. Для набора вам нужен доступ по времени log(N), и для этого вы хотите организовать набор в зависимости от порядка элементов. Значит, надо уметь их сравнивать. OCaml предоставляет функцию сравнения по умолчанию (Pervasives.compare), но эта функция не всегда лучшая: она дорога в использовании (например, для целых чисел) и не всегда работает (использует лексикографический порядок в структура значения, это не всегда тот порядок, который вам нужен).

В OCaml, когда тип зависит от значения, что имеет место в случае «набора», но также может быть в случае «отсортированного списка», вам нужно использовать функтор для определения типа и применить функтор чтобы получить новый тип.

Вот что этот код делает для вас:

модуль StringSet = Set.Make(String)

эквивалентно :

module StringSet = Set.Make(struct
  type t = string
  let compare = compare
end)

где «давайте сравнить = сравнить» означает, что функция сравнения является функцией по умолчанию (второе сравнение относится к Pervasives.compare). Вместо этого вы можете использовать непосредственно «String», так как модули String уже содержат «type t = string» и «let compare = compare».

person Fabrice Le Fessant    schedule 14.02.2012