OCaml: установить модули - PullRequest
       7

OCaml: установить модули

18 голосов
/ 21 сентября 2009

Я хочу использовать OCaml для генерации наборов данных и сравнения между ними. Я видел документацию для таких типов модулей, как Set.OrderType, Set.Make и т. Д., Но не могу понять, как инициализировать набор или как-то иначе его использовать.

Ответы [ 2 ]

30 голосов
/ 21 сентября 2009

Наборы определяются с помощью функционального интерфейса. Для любого данного типа вы должны создать модуль Set для этого типа, используя функтор Set.Make. К сожалению, упущение стандартных библиотек заключается в том, что они не определяют Set экземпляров для встроенных типов. В большинстве простых случаев достаточно использовать Pervasives.compare. Вот определение, которое работает для int:

module IntSet = Set.Make( 
  struct
    let compare = Pervasives.compare
    type t = int
  end )

Модуль IntSet будет реализовывать интерфейс Set.S. Теперь вы можете работать с сетами, используя модуль IntSet:

let s = IntSet.empty ;;
let t = IntSet.add 1 s ;;
let u = IntSet.add 2 s ;;
let tu = IntSet.union t u ;;

Обратите внимание, что вам не нужно явно определять структуру ввода для Set.Make как OrderedType; вывод типа сделает всю работу за вас. В качестве альтернативы вы можете использовать следующее определение:

module IntOrder : Set.OrderedType = struct
  type t = int
  let compare = Pervasives.compare
end

module IntSet = Set.Make( IntOrder )

Это имеет то преимущество, что вы можете повторно использовать один и тот же модуль для создания экземпляра Map:

module IntMap = Map.Make( IntOrder )

Вы теряете некоторую универсальность при использовании функторов, потому что тип элементов фиксирован. Например, вы не сможете определить функцию, которая принимает Set некоторого произвольного типа и выполняет какую-то операцию с ней. (К счастью, сам модуль Set объявляет много полезных операций над Set с.)

12 голосов
/ 21 сентября 2009

В дополнение к ответу Криса, может быть полезно сказать, что некоторые стандартные библиотечные модули уже придерживаются подписи OrderedType. Например, вы можете просто сделать:

module StringSet = Set.Make(String) ;;       (* sets of strings *)
module Int64Set = Set.Make(Int64) ;;         (* sets of int64s *)
module StringSetSet = Set.Make(StringSet) ;; (* sets of sets of strings *)

и т. Д.

Вот простой пример использования StringSet; помните, что наборы являются функциональными структурами данных, поэтому добавление нового элемента в набор возвращает новый набор:

let set = List.fold_right StringSet.add ["foo";"bar";"baz"] StringSet.empty ;;
StringSet.mem "bar" set ;; (* returns true *)
StringSet.mem "zzz" set ;; (* returns false *)
...