package logtk

  1. Overview
  2. Docs
Core types and algorithms for logic

Install

Dune Dependency

Authors

Maintainers

Sources

1.5.1.tar.gz
md5=cc320f66f10555c54822da624419e003
sha512=f8d5f7a5ae790bf0388d74261673803cf375f91f92f7b413b70db1ce5841ef55343a208f98727c8551d66f1840ab892f1c0c943a34861d14d79ce469b235a2f2

doc/src/logtk/Multiset_intf.ml.html

Source file Multiset_intf.ml

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155

(* This file is free software, part of Logtk. See file "license" for more details. *)

module type S = sig
  type elt
  (** Elements of the multiset *)

  type t
  (** A multiset of elements of type 'a *)

  val size : t -> int
  (** Number of distinct elements. *)

  val cardinal : t -> Z.t
  (** Number of unique occurrences of elements (the multiplicity of each
      element is considered) *)

  val empty : t
  (** Empty multiset *)

  val is_empty : t -> bool
  (** Is the multiset empty? *)

  val mem : t -> elt -> bool
  (** Is the element part of the multiset? *)

  val find : t -> elt -> Z.t
  (** Return the multiplicity of the element within the multiset.
      Will return [Z.zero] if the element is not part of the multiset *)

  val singleton : elt -> t

  val doubleton : elt -> elt -> t

  val add : t -> elt -> t
  (** Add one occurrence of the element *)

  val add_coeff : t -> elt -> Z.t -> t
  (** Add several occurrences of the element *)

  val union : t -> t -> t
  (** Union of multisets (max of multiplicies) *)

  val intersection : t -> t -> t
  (** Intersection of multisets (min of multiplicies) *)

  val sum : t -> t -> t
  (** Sum of multiplicies *)

  val difference : t -> t -> t
  (** Difference of multisets. If [x] has a bigger multiplicity in the
      second argument it won't appear in the result *)

  val product : Z.t -> t -> t
  (** Multiply all multiplicities with the given coefficient *)

  val filter : (elt -> Z.t -> bool) -> t -> t
  (** Filter out elements that don't satisfy the predicate *)

  val map : (elt -> elt) -> t -> t
  (** Apply a function to all elements *)

  val map_coeff : (elt -> Z.t -> Z.t) -> t -> t
  (** Apply a function to all coefficients. *)

  val filter_map : (elt -> Z.t -> (elt * Z.t) option) -> t -> t
  (** More powerful mapping *)

  val flat_map : (elt -> t) -> t -> t
  (** replace each element by a multiset in its own *)

  module Seq : sig
    val of_seq : t -> elt Iter.t -> t
    val to_seq : t -> elt Iter.t

    val of_coeffs : t -> (elt * Z.t) Iter.t -> t
    val to_coeffs : t -> (elt * Z.t) Iter.t
  end

  val iter : (elt -> unit) -> t -> unit
  (** Iterate on distinct occurrences of elements *)

  val fold : ('a -> elt -> 'a) -> 'a -> t -> 'a
  (** fold on occurrences of elements *)

  val iter_coeffs : (elt -> Z.t -> unit) -> t -> unit
  (** Iterate on elements with their multiplicity *)

  val fold_coeffs : ('a -> elt -> Z.t -> 'a) -> 'a -> t -> 'a
  (** Fold on elements with their multiplicity *)

  val for_all : (elt -> bool) -> t -> bool

  val exists : (elt -> bool) -> t -> bool

  val choose : t -> elt
  (** Chose one element, or
      @raise Not_found if the multiset is empty *)

  val of_list : elt list -> t
  (** Multiset from list *)

  val of_coeffs : (elt * Z.t) list -> t
  (** From list of elements with multiplicities. Multiplicities lower
      than 0 will not count. *)

  val of_iarray : elt IArray.t -> t
  (** From immutable array *)

  val of_array : elt array -> t

  val to_list : t -> (elt * Z.t) list
  (** List of elements with their coefficients *)

  val equal : t -> t -> bool
  (** Check equality of two multisets *)

  val cancel : t -> t -> t * t
  (** Remove common elements from the multisets. For instance,
      on [{1,1,2}] and [{1,2,2,3}], [cancel] will return [({1}, {2,3})] *)

  (** {6 Comparisons}

      In the following, the comparison function must be equality-compatible
      with [E.compare]. In other words, if [E.compare x y = 0] then
      [f x y = Comparison.Eq] must hold. *)

  val compare : t -> t -> int
  (** Compare two multisets with the multiset extension of {!E.compare} *)

  val compare_partial : (elt -> elt -> Comparison.t) -> t -> t -> Comparison.t
  (** Compare two multisets with the multiset extension of the
      given ordering. This ordering is total iff the element
      ordering is. *)

  val is_max : (elt -> elt -> Comparison.t) -> elt -> t -> bool
  (** Is the given element maximal (ie not dominated by any
      other element) within the multiset? *)

  val max : (elt -> elt -> Comparison.t) -> t -> t
  (** Maximal elements of the multiset, w.r.t the given ordering. *)

  val max_seq : (elt -> elt -> Comparison.t) -> t -> (elt * Z.t) Iter.t
  (** Fold on maximal elements *)

  val max_l : (elt -> elt -> Comparison.t) -> elt list -> elt list
  (** Maximal elements of a list *)

  val compare_partial_l :
    (elt -> elt -> Comparison.t) ->
    elt list -> elt list -> Comparison.t
  (** Compare two multisets represented as list of elements *)

  val pp : elt CCFormat.printer -> t CCFormat.printer
end
OCaml

Innovation. Community. Security.