package grenier

  1. Overview
  2. Docs
type 'a t

A set of abstract elements annotated with values of type 'a that can be efficiently diffed.

val empty : 'a t

The empty set

val element : 'a -> 'a t

element x creates a new set element tagged with metadata x (O(1)). It is the physical identity of the element that is considered when computing set difference, not the tag. Therefore diff (element x) (element x) = { added = [x]; removed = [x]; } But (let e = element x in diff e e) = { added = []; removed = []; }

val union : 'a t -> 'a t -> 'a t

The union of two set of resources (O(1))

type 'a diff = {
  1. left_only : 'a list;
  2. right_only : 'a list;
}

Compute the difference between two sets.

diff old_set new_set = { added; removed } where removed lists the tag of elements only present in old_set and added lists the tag of elements only present in new_set

_Conjecture_: the algorithm is linear in the number of changes between old_set and new_set.

When used in a linear fashion (you have a sequence of sets s_i and only compare s_i and s_i+1, at most once for each i), it should not affect the complexity of the program.

val diff : left:'a t -> right:'a t -> 'a diff
type 'a marking
val mark : left:'a t -> right:'a t -> 'a marking
val unmark : 'a marking -> unit
val unmark_and_diff : 'a marking -> 'a diff
type mark =
  1. | Left
  2. | Right
  3. | Both
val get_mark : 'a marking -> 'a t -> mark
type 'a view =
  1. | Empty
  2. | Union of 'a t * 'a t
  3. | Element of 'a
val view : 'a t -> 'a view
OCaml

Innovation. Community. Security.

GitHub Discord Twitter Peertube RSS
About
Changelog Releases Industrial Users Academic Users Why OCaml
Ecosystem
Packages Community Events OCaml Planet Jobs
Resources
Install OCaml Get Started Platform Tools Language Manual Standard Library API Books Exercises Papers OCaml Playground Logo
Policies
Carbon Footprint Governance Privacy Code of Conduct