package grenier

  1. Overview
  2. Docs
A collection of various algorithms in OCaml

Install

Dune Dependency

Authors

Maintainers

Sources

grenier-v0.10.tbz
sha256=271ae9461d012c99449e5233386b13ab99ae2e474ed570e05bf0c9947e5eff1e
sha512=73c89aa6281f612c499eb734c6fc4d33b961ed82d6cc7380b03acb196233c27107e103b11f55e50f543f0f1dedb4924e6691a5c3c353ef4d8177bc661fc2bfd4

doc/grenier.dset/Dset/index.html

Module Dset

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.