Контейнеры внутри записей в Ocaml - PullRequest
Новая
       20

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

2 голосов
/ 03 февраля 2012

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

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

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

Ответы [ 2 ]

5 голосов
/ 03 февраля 2012

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

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

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

type record = {
    name: string;
    neighbors: string BatSet.t
};
2 голосов
/ 14 февраля 2012

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

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

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

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

module StringSet = Set.Make (String)

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

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

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

...