Module type `Urn.U`Source

Output signature of the functor Make.

Sourcetype weight

The type of weights.

Sourcetype !+'a t

The type of urns.

Creating Urns

Sourceval singleton : weight -> 'a -> 'a t

singleton w x returns the one-element urn containing x with weight w. Time complexity O(1).

raises Invalid_argument
if w <= 0.

Sourceval of_list : (weight * 'a) list -> 'a t option

of_list was creates an urn from a list of pairs of weights and values. Time complexity O(n).

raises Invalid_argument
if any of the weights are <= 0.

Adding Elements to Urns

Sourceval add : weight -> 'a -> 'a t -> 'a t

add w a ur returns an urn containing the same weights and elements as ur but additionally containing a with weight w. Time complexity O(log n).

raises Invalid_argument
if w <= 0

Sourceval add_seq : (weight * 'a) Seq.t -> 'a t -> 'a t

Add the weight-value pairs in the sequence to the urn. Time complexity O(m log n), where m is the length of the sequence.

raises Invalid_argument
if any of the weights are <= 0.

Sourceval add_list : (weight * 'a) list -> 'a t -> 'a t

Add the weight-value pairs in the list to the urn. Time complexity O(m log n), where m is the length of the list.

raises Invalid_argument
if any of the weights are <= 0.

Sampling Urns

Sourceval sample : 'a t -> 'a

sample ur samples an element of the urn ur and returns it. Time complexity O(log n).

Sourceval remove : 'a t -> (weight * 'a) * 'a t option

remove ur samples an element of the urn ur and returns it along with a new urn with that element removed, or None if the new urn would be empty. Time complexity O(log n).

Sourceval replace : weight -> 'a -> 'a t -> (weight * 'a) * 'a t

replace w a ur samples the urn ur, and returns the sampled element and its weight along with a new urn with the sampled elements removed and a with weight w added. Time complexity O(log n).

raises Invalid_argument
if w <= 0.

Source

val update : 
  (weight -> 'a -> weight * 'a) ->
  'a t ->
  (weight * 'a) * (weight * 'a) * 'a t

update f ur samples an element of the urn ur, then takes the chosen element a and its weight w, and replaces it with f w a, returning a triple of (w, a), f w a, ur' where ur' is the urn containing all the elements and weights of ur but with the chosen w, a replaced by f w a. Time complexity O(log n).

raises Invalid_argument
if the weight produced by f w a is <= 0.

Source

val update_opt : 
  (weight -> 'a -> (weight * 'a) option) ->
  'a t ->
  (weight * 'a) * (weight * 'a) option * 'a t option

update f ur samples an element of the urn ur, then takes the chosen element a and its weight w, and applies f to them. If f w a returns None then the element is removed from the urn. If f w a returns Some (w', a') then the chosen elements weight and value is replaced by w' and a' respectively. The elements of the returned triple are as in update. Time complexity O(log n).

raises Invalid_argument
if w' <= 0.

Misc

Sourceval size : 'a t -> int

size ur returns the total number of elements in the urn ur. Time complexity O(1).

Sourceval weight : 'a t -> weight

weight ur returns the sum of all the weights in the urn ur. Time complexity O(1).

package urn

Module type Urn.USource

Creating Urns

Adding Elements to Urns

Sampling Urns

Misc

Module type `Urn.U`Source