Saya mengalami masalah seputar definisi modul rekursif/saling referensi yang mencoba menggunakan hal-hal Peta/Set Caml. Saya benar-benar menginginkan yang hanya berfungsi pada tipe, bukan modul. Saya merasa mungkin untuk melakukan ini dengan modul kelas satu, tetapi saya gagal membuat sintaksnya berfungsi.

Tanda tangan yang saya inginkan adalah:

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

Mungkin dengan fungsi Caml.Set lainnya disertakan. Ide saya tentang bagaimana ini akan bekerja adalah seperti:

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

Tapi itu tidak berhasil karena beberapa alasan; 'a tidak diekspos di tempat yang tepat, saya tidak dapat merujuk m.t dalam catatan yang sama di mana m didefinisikan, dll.

Apakah ada versi ini yang berfungsi?

Menambahkan lebih banyak konteks tentang kasus penggunaan saya:

Saya memiliki dua modul, Region dan Tribe. Tribe membutuhkan akses ke banyak antarmuka Region, jadi saat ini saya membuat Tribe sebagai functor, MakeTribe(Region : RegionT). Region sebagian besar tidak perlu tahu tentang Tribe, tetapi harus dapat menyimpan koleksi Tribe.t yang dapat berubah yang mewakili suku yang tinggal di wilayah tersebut.

Jadi, entah bagaimana, saya membutuhkan RegionT like

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

Saya tidak terlalu peduli dengan sintaks spesifik <tribe>, <tribes> dan <region> dalam hal ini, selama modul Tribe yang dibangun sepenuhnya dapat mengetahui bahwa Region.get_local_tribes, dll, akan menghasilkan Tribe.t yang sebenarnya Masalah ketergantungan melingkar adalah bahwa tipe <tribe> tidak ada sampai modul Tribe dibuat. Ide saya sejauh ini adalah agar RegionT.t benar-benar menjadi 'a RegionT.t, dan kemudian Tribe dapat dengan mudah merujuk ke Tribe.t Region.t. Ini semua baik-baik saja jika saya puas dengan menyimpan <tribe> list di dalam Region, tetapi saya ingin itu menjadi satu set.

Saya merasa ini harus dimungkinkan berdasarkan kode contoh berikut:

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)

Semua yang diperlihatkan Example di antarmukanya adalah tipe dan fungsi dari dua instance tipe itu ke int; mengapa itu lebih dari memiliki 'a -> 'a -> int, yang memiliki hal yang sama?

2
Edward Peters 12 Mei 2021, 19:50

1 menjawab

Jawaban Terbaik

Menggunakan Set Polimoprik dan Peta dari Perpustakaan Dasar

Di pustaka Base dan Core, dari Jane Street, struktur data yang dipesan, seperti peta, set, tabel hash, dan set hash, semuanya diimplementasikan sebagai struktur data polimorfik, alih-alih versi yang difungsikan seperti di pustaka standar vanilla OCaml.

Anda dapat membaca lebih lanjut tentang mereka di bab Maps dan Hashtbales Dunia Nyata. Tapi di sini ada resep cepat. Saat Anda melihat komparator di antarmuka fungsi, misalnya, di Map.empty yang sebenarnya diinginkan adalah memberi Anda modul yang mengimplementasikan antarmuka komparator. Kabar baiknya adalah sebagian besar modul di Base/Core mengimplementasikannya, jadi Anda tidak perlu khawatir atau tahu apa pun tentang ini untuk menggunakannya, mis.,

# 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>

Jadi aturan sederhananya, jika Anda menginginkan set,map,hashtable,hashset di mana elemen kuncinya bertipe foo, cukup berikan (module Foo) sebagai pembanding.

Sekarang, bagaimana jika Anda ingin membuat pemetaan dari jenis kustom Anda? Misalnya, sepasang int yang ingin Anda bandingkan dalam urutan leksikografis.

Pertama-tama, kita perlu mendefinisikan sexp_of dan membandingkan fungsi. Untuk tipe kami. Kami akan menggunakan turunan ppx untuk itu, tetapi mudah untuk membuatnya secara manual jika Anda membutuhkannya.

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

Sekarang, untuk membuat komparator, kita hanya perlu menggunakan fungsi Base.Comparator.Make, mis.,

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

Jadi sekarang kita bisa melakukannya,


# 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>

Meskipun struktur data Base bersifat polimorfik, mereka sangat membutuhkan modul yang menyediakan komparator untuk dipakai dan diketahui. Anda bisa menggunakan fungsi bandingkan untuk membuat struktur data polimorfik karena Base akan membuat instance tipe saksi untuk setiap fungsi perbandingan yang ditentukan dan menangkapnya dalam tipe struktur data untuk mengaktifkan metode biner. Bagaimanapun, ini adalah masalah yang kompleks, baca terus untuk solusi yang lebih mudah (dan lebih sulit).

Membuat Instansiasi Set pada modul yang saling bergantung

Faktanya, OCaml mendukung funtor yang saling rekursif dan meskipun saya menyarankan Anda untuk mematahkan rekursi dengan memperkenalkan abstraksi umum yang menjadi sandaran Wilayah dan Suku, Anda masih dapat menyandikan masalah Anda di OCaml, mis.,

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

Mematahkan Lingkaran Ketergantungan

Solusi yang jauh lebih baik adalah mendesain ulang modul Anda dan memutus loop ketergantungan. Pendekatan paling sederhana adalah dengan memilih beberapa pengenal yang akan digunakan untuk membandingkan suku, misalnya, dengan nama unik mereka,

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

Ada juga banyak pilihan lain dan secara umum, ketika Anda memiliki ketergantungan timbal balik, itu sebenarnya merupakan indikator masalah dalam desain Anda. Jadi, saya masih akan mengunjungi kembali tahap desain dan menghindari ketergantungan melingkar.

Membuat Kumpulan Polimorfik menggunakan Pustaka Standar Vanilla OCaml

Ini bukan tugas yang mudah, terutama jika Anda perlu menangani operasi yang melibatkan beberapa set, misalnya Set.union. Masalahnya adalah Set.Make menghasilkan tipe baru untuk set per setiap fungsi compare jadi ketika kita perlu menyatukan dua set, sulit bagi kita untuk membuktikan kepada kompiler OCaml bahwa mereka dibuat dari Tipe yang sama. Itu mungkin tetapi sangat menyakitkan, saya menunjukkan bagaimana melakukan ini hanya untuk mencegah Anda melakukan ini (dan untuk menunjukkan kemampuan mengetik dinamis OCaml).

Pertama-tama kita membutuhkan tipe saksi yang akan mengubah tipe OCaml untuk himpunan menjadi nilai konkret.

type _ witness = ..


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

Sekarang kita dapat mendefinisikan himpunan polimorfik kita sebagai eksistensial yang menampung himpunan itu sendiri dan modul dengan operasi. Itu juga menyimpan tid (untuk pengidentifikasi tipe) yang nantinya akan kita gunakan untuk memulihkan tipe 's dari himpunan.

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

Sekarang kita dapat menulis fungsi create yang akan mengambil fungsi perbandingan dan mengubahnya menjadi himpunan,

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);
  }

Peringatan di sini adalah bahwa setiap panggilan ke create akan menghasilkan instance baru dari tipe set 's sehingga kita dapat membandingkan/union/etc dua set yang dibuat dengan fungsi create yang sama. Dengan kata lain, semua set dalam implementasi kami akan memiliki nenek moyang yang sama. Tapi sebelum itu mari kita coba dan terapkan setidaknya dua operasi, add dan 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"

Sekarang, kita bisa bermain dengannya sedikit,


# 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".
#
2
ivg 12 Mei 2021, 21:42