OCaml: установка модулей

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


module set ocaml
person Nick Heiner    schedule 20.09.2009    source источник

Ответы (2)


arrow_upward
31
arrow_downward

Наборы определяются с помощью функториального интерфейса. Для любого данного типа вы должны создать модуль 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 объявляет множество полезных операций над Sets.)

person Chris Conway    schedule 20.09.2009
comment
вы не сможете определить функцию, которая принимает Set некоторого произвольного типа, однако вы могли бы выполнить то же самое, определив функцию внутри функтора, который принимает ваш конкретный модуль Set в качестве параметра. но для его использования программисту, конечно, пришлось бы делать еще один модуль с этим функтором, так что он менее удобен - person newacct; 21.09.2009
comment
Правильно. Это функторы на всем пути вниз. - person Chris Conway; 21.09.2009

arrow_upward
12
arrow_downward

В дополнение к ответу Криса может быть полезно сказать, что некоторые стандартные библиотечные модули уже придерживаются подписи 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 *)
person Bruno De Fraine    schedule 21.09.2009