Как создать набор элементов, не зная типа элемента?

Question

У меня возникают проблемы с определениями рекурсивных / взаимно ссылочных модулей, пытающихся использовать материал Caml Map / Set. Мне действительно нужны те, которые работают только с типами, а не с модулями. Я чувствую, что это должно быть возможно сделать с помощью первоклассных модулей, но мне не удается заставить синтаксис работать.

Подпись, которую я хочу:

      module type NonFunctorSet = sig
  type 'a t
  val create : ('a -> 'a -> int) -> 'a t
  val add : 'a t -> 'a -> 'a t
  val remove : 'a t -> 'a -> 'a t
  val elements : 'a t -> 'a list
end

Возможно с другими Caml.Setфункции включены. Моя идея о том, как это будет работать, выглядит примерно так:

      type 'a t = {
 m : (module Caml.Set.S with type elt = 'a);
 set : m.t
}

let create (compare : 'a -> 'a -> t) =
    module m = Caml.Set.Make(struct type t = 'a let compare = compare end) in
    let set = m.empty in
    {m = m; set = set;}
end

Но это не работает по ряду причин; 'a не отображается в нужных местах, я не могу ссылаться на mt в той же записи, где m был определен, и т. д.

Есть версия, которая работает?

Добавляем больше контекста о моем варианте использования:

У меня есть два модуля, и. требуется доступ ко многим интерфейсам, поэтому в настоящее время я создаю как функтор, MakeTribe(Region : RegionT). в основном не нужно знать об этом, но он должен иметь возможность хранить изменяемую коллекцию, которая представляет племена, живущие в этом регионе.

Так или иначе, мне нужен RegionT нравиться

      module type RegionT = sig
  type <region>
  val get_local_tribes : <region> -> <tribes>
  val add_tribe : <region> -> <tribe> -> unit
  ...
end

Меня не особо интересует конкретный синтаксис, <tribes> а также <region> в этом случае, если полностью собранный модуль может знать, что Region.get_local_tribesи т. д., дадут фактический Tribe.t Проблема круговой зависимости заключается в том, что тип <tribe>не существует, пока модуль не будет создан. Моя идея до сих пор заключалась в том, чтобы RegionT.t на самом деле быть 'a RegionT.t, а потом Tribe можно просто сослаться на Tribe.t Region.t. Все в порядке, если я доволен тем, что <tribe> list внутри Region, но я хочу, чтобы это был набор.

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

      module Example : sig
  type t
  val compare : t -> t -> int
end = struct
  type t = int
  let compare = Int.compare
end

module ExampleSet = Caml.Set.Make(struct type t = Example.t let compare = Example.compare end)

Все это Exampleпредоставляет в своем интерфейсе тип и функцию из двух экземпляров этого типа в int; почему это больше, чем просто 'a -> 'a -> int, где есть то же самое?

Answer 1

Использование полиморфных наборов и карт из базовой библиотеки

В базовых и основных библиотеках от Jane Street упорядоченные структуры данных, такие как карты, наборы, хеш-таблицы и хеш-наборы, все реализованы как полиморфные структуры данных, а не функционализированные версии, как в стандартной библиотеке OCaml.

Вы можете прочитать о них больше в главе « OCaml Картыи хэшбалы в реальном мире» . Но вот быстрые рецепты. Когда вы видите компаратор в интерфейсе функции, например, в Map.emptyна самом деле он хочет, чтобы вы дали вам модуль , реализующий интерфейс компаратора. Хорошей новостью является то, что большинство модулей в Base / Core реализуют его, поэтому вам не нужно беспокоиться или знать что-либо об этом, чтобы использовать его, например,

      # open Base;;
# let empty = Map.empty (module Int);;
val empty : (Base.Int.t, 'a, Base.Int.comparator_witness) Base.Map.t =
  <abstr>
# Map.add empty 1 "one";;
- : (Base.Int.t, string, Base.Int.comparator_witness) Base.Map.t
    Base.Map.Or_duplicate.t
= `Ok <abstr>

Итак, простое правило, если вам нужен набор, карта, хеш-таблица, хеш-набор, где ключевой элемент имеет тип fooпросто пройди (module Foo) как компаратор.

А что, если вы хотите создать сопоставление из своего настраиваемого типа? Например, пара int, которые вы хотели бы сравнить в лексикографическом порядке.

Прежде всего, нам нужно определить sexp_of и сравнить функции. Для нашего типа. Мы будем использовать для этого производные ppx, но при необходимости это легко сделать вручную.

       module Pair = struct
   type t = int * int [@@deriving compare, sexp_of]
 end

Теперь, чтобы создать компаратор, нам просто нужно использовать Base.Comparator.Make функтор, например,

       module Lexicographical_order = struct 
    include Pair
    include Base.Comparator.Make(Pair)
 end

Итак, теперь мы можем сделать,

      
# let empty = Set.empty (module Lexicographical_order);;
val empty :
  (Lexicographical_order.t, Lexicographical_order.comparator_witness)
  Base.Set.t = <abstr>
# Set.add empty (1,2);;
- : (Lexicographical_order.t, Lexicographical_order.comparator_witness)
    Base.Set.t
= <abstr>

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

Создание экземпляров наборов на взаимозависимых модулях

Фактически, OCaml поддерживает взаимно рекурсивные фунторы, и хотя я бы посоветовал вам прервать рекурсию, введя общую абстракцию, от которой зависят как Region, так и Tribe, вы все равно можете кодировать свою проблему в OCaml, например,

      module rec Tribe : sig
  type t
  val create : string -> t
  val compare : t -> t -> int
  val regions : t -> Region.t list
end = struct
  type t = string * Region.t list
  let create name = name,[]
  let compare (x,_) (y,_) = String.compare x y
  let regions (_,r) = r
end
and Region : sig
  type t
  val empty : t
  val add_tribe : Tribe.t -> t -> t
  val tribes : t -> Tribe.t list
end = struct
  module Tribes = Set.Make(Tribe)
  type t = Tribes.t
  let empty = Tribes.empty
  let add_tribe = Tribes.add
  let tribes = Tribes.elements
end

Разрыв петли зависимости

Гораздо лучшим решением было бы изменить дизайн ваших модулей и разорвать цикл зависимостей. Самый простой подход - просто выбрать какой-то идентификатор, который будет использоваться для сравнения племен, например, по их уникальным именам,

      module Region : sig
  type 'a t
  val empty : 'a t
  val add_tribe : string -> 'a -> 'a t -> 'a t
  val tribes : 'a t -> 'a list
end = struct
  module Tribes = Map.Make(String)
  type 'a t = 'a Tribes.t
  let empty = Tribes.empty
  let add_tribe = Tribes.add
  let tribes r = Tribes.bindings r |> List.map snd

end

module Tribe : sig
  type t
  val create : string -> t
  val name : t -> string
  val regions : t -> t Region.t list
  val conquer : t Region.t -> t -> t Region.t
end = struct
  type t = Tribe of string * t Region.t list
  let create name = Tribe (name,[])
  let name (Tribe (name,_)) = name
  let regions (Tribe (_,r)) = r
  let conquer region tribe =
    Region.add_tribe (name tribe) tribe region
end

Есть также множество других вариантов, и в целом, когда у вас есть взаимозависимости, это фактически индикатор проблемы в вашем дизайне. Так что я бы все равно вернулся к стадии проектирования и отказался от циклических зависимостей.

Создание полиморфных наборов с использованием стандартной библиотеки Vanilla OCaml

Это непростая задача, особенно если вам нужно обрабатывать операции, включающие несколько наборов, например, Set.union. Проблема в том, что Set.Make генерирует новый тип для набора для каждого compareфункция, поэтому, когда нам нужно объединить два набора, нам трудно доказать компилятору OCaml, что они были созданы из одного и того же типа. Это возможно, но очень болезненно. Я показываю, как это сделать, только для того, чтобы отговорить вас от этого (и продемонстрировать возможности динамической типизации OCaml).

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

      type _ witness = ..


module type Witness = sig
  type t
  type _ witness += Id : t witness
end

Теперь мы можем определить наш полиморфный набор как экзистенциальный, содержащий сам набор и модуль с операциями. Он также содержит tid (для идентификатора типа), который мы позже будем использовать для восстановления типа набора.

      type 'a set = Set : {
    set : 's;
    ops : (module Set.S with type elt = 'a and type t = 's);
    tid : (module Witness with type t = 's);
  } -> 'a set

Теперь мы можем написать функцию, которая возьмет функцию сравнения и превратит ее в набор,

      let create : type a s. (a -> a -> int) -> a set =
  fun compare ->
  let module S = Set.Make(struct
      type t = a
      let compare = compare
    end) in
  let module W = struct
    type t = S.t
    type _ witness += Id : t witness
  end in
  Set {
    set = S.empty;
    ops = (module S);
    tid = (module W);
  }

Предостережение здесь в том, что каждый вызов будет генерировать новый экземпляр заданного типа. 's поэтому мы можем сравнить / объединить / и т. д. два набора, которые были созданы с одним и тем же createфункция. Другими словами, все наборы в нашей реализации должны иметь одного и того же предка. Но перед этим позвольте себе немного поработать и выполнить как минимум две операции, add а также union,

      let add : type a. a -> a set -> a set =
  fun elt (Set {set; tid; ops=(module Set)}) -> Set {
      set = Set.add elt set;
      ops = (module Set);
      tid;
    }

let union : type a. a set -> a set -> a set =
  fun (Set {set=s1; tid=(module W1); ops=(module Set)})
    (Set {set=s2; tid=(module W2)}) ->
    match W1.Id with
    | W2.Id -> Set {
        set = Set.union s1 s2;
        tid = (module W1);
        ops = (module Set);
      }
    | _ -> failwith "sets are potentially using different types"

Теперь мы можем немного поиграть с этим,

      
# let empty = create compare;;
val empty : '_weak1 set = Set {set = <poly>; ops = <module>; tid = <module>}
# let x1 = add 1 empty;;
val x1 : int set = Set {set = <poly>; ops = <module>; tid = <module>}
# let x2 = add 2 empty;;
val x2 : int set = Set {set = <poly>; ops = <module>; tid = <module>}
# let x3 = union x1 x2;;
val x3 : int set = Set {set = <poly>; ops = <module>; tid = <module>}
# let x4 = create compare;;
val x4 : '_weak2 set = Set {set = <poly>; ops = <module>; tid = <module>}
# union x3 x4;;
Exception: Failure "sets are potentially using different types".
#