Calculemus

Partition Module

Namespace: Calculemus.Lib
Assembly: Calculemus.dll

Equivalence relations (or partitions, equivalence classes) on finite sets.

See also Disjoint set/Union Find data structure on Wikipedia.

Types

Type Description

partition<'a>

Union-Find datatype to represent equivalence relations (partitions) on finite sets.

pnode<'a>

Type of polymorphic partition node.

Functions and values

Function or value Description

canonize ptn a

Full Usage: canonize ptn a

Parameters:
    ptn : partition<'a> - The input partition.
    a : 'a - The element of the partition to search.

Returns: 'a The canonical element of a's equivalence class, if a is an element in the domain of the partition; otherwise a itself.

Returns the canonical representative of the ptn-equivalence class containing a, if a is in the domain of the partition. Otherwise it returns just a itself.

Corresponds to the find method in the union-find algorithm.

ptn : partition<'a>

The input partition.

a : 'a

The element of the partition to search.

Returns: 'a

The canonical element of a's equivalence class, if a is an element in the domain of the partition; otherwise a itself.

Example 

 let (Partition f as ptn) = 
   unequal
   |> equate (2,1) 
   |> equate (3,1)
   |> equate (4,1) 
   |> equate (6,5) 
   |> equate (7,5) 
 
 canonize ptn 3
val f: obj
val ptn: obj
Evaluates to 1.

Example 

 let (Partition f as ptn) = 
   unequal
   |> equate (2,1) 
   |> equate (3,1)
   |> equate (4,1) 
   |> equate (6,5) 
   |> equate (7,5) 
 
 canonize ptn 8
val f: obj
val ptn: obj
Evaluates to 8.

equate (a, b) ptn

Full Usage: equate (a, b) ptn

Parameters:
    a : 'a - The first element to equate.
    b : 'a - The second element to equate.
    ptn : partition<'a> - The input partition.

Returns: partition<'a> The new partition with the updated equivalence classes.

Creates a new partition that results from merging the a and b classes in ptn, i.e. the smallest equivalence relation containing ptn such that a and b are equivalent.

Corresponds to the union method in the union-find algorithm.

a : 'a

The first element to equate.

b : 'a

The second element to equate.

ptn : partition<'a>

The input partition.

Returns: partition<'a>

The new partition with the updated equivalence classes.

Example 

 unequal
 |> equate (2,1)
 |> fun (Partition f) -> graph f
val f: obj
Evaluates to [(1, Terminal (1, 2)); (2, Nonterminal 1)].

equated ptn

Full Usage: equated ptn

Parameters:
Returns: 'a list The domain of the partition.

Returns the domain of the partition ptn.

ptn : partition<'a>

The input partition.

Returns: 'a list

The domain of the partition.

Example 

 let (Partition f as ptn) = 
   unequal
   |> equate (2,1) 
   |> equate (3,1)
   |> equate (4,1) 
   |> equate (6,5) 
   |> equate (7,5) 
 
 equated ptn
val f: obj
val ptn: obj
Evaluates to [1; 2; 3; 4; 5; 6; 7].

equivalent ptn a b

Full Usage: equivalent ptn a b

Parameters:
    ptn : partition<'a> - The input partition.
    a : 'a - The first element to compare.
    b : 'a - The second element to compare.

Returns: bool true if a and b belong to the same equivalence class in ptn; otherwise false.

Tests if a and b are equivalent w.r.t. ptn.

ptn : partition<'a>

The input partition.

a : 'a

The first element to compare.

b : 'a

The second element to compare.

Returns: bool

true if a and b belong to the same equivalence class in ptn; otherwise false.

Example 

 let (Partition f as ptn) = 
   unequal
   |> equate (2,1) 
   |> equate (3,1)
   |> equate (4,1) 
   |> equate (6,5) 
   |> equate (7,5) 
 
 equivalent ptn 3 2
val f: obj
val ptn: obj
Evaluates to true.

Example 

 let (Partition f as ptn) = 
   unequal
   |> equate (2,1) 
   |> equate (3,1)
   |> equate (4,1) 
   |> equate (6,5) 
   |> equate (7,5) 
 
 equivalent ptn 6 1
val f: obj
val ptn: obj
Evaluates to false.

terminus ptn a

Full Usage: terminus ptn a

Parameters:
    ptn : partition<'a> - The input partition.
    a : 'a - The element of the partition to search.

Returns: 'a * int The pair of the canonical element of a's equivalence class plus its size, if a is an element in the domain of the partition.

Searches for the canonical representative of the ptn-equivalence class containing a, failing if a does not belong to the domain of the partition.

ptn : partition<'a>

The input partition.

a : 'a

The element of the partition to search.

Returns: 'a * int

The pair of the canonical element of a's equivalence class plus its size, if a is an element in the domain of the partition.

Exception Thrown with message apply, when a is not an element in the domain of the partition.
Example 

 let (Partition f as ptn) = 
   unequal
   |> equate (2,1) 
   |> equate (3,1)
   |> equate (4,1) 
   |> equate (6,5) 
   |> equate (7,5) 
 
 terminus ptn 3
val f: obj
val ptn: obj
Evaluates to (1, 4).

Example 

 let (Partition f as ptn) = 
   unequal
   |> equate (2,1) 
   |> equate (3,1)
   |> equate (4,1) 
   |> equate (6,5) 
   |> equate (7,5) 
 
 terminus ptn 8
val f: obj
val ptn: obj
Throws System.Exception: apply.

tryterminus ptn a

Full Usage: tryterminus ptn a

Parameters:
    ptn : partition<'a> - The input partition.
    a : 'a - The element of the partition to search.

Returns: 'a * int The pair of the canonical element of a's equivalence class plus its size, if a is an element in the domain of the partition; otherwise (a, 1).

Searches for the canonical representative of the ptn-equivalence class containing a, returning the input element a itself if it does not belong to the domain of the partition.

ptn : partition<'a>

The input partition.

a : 'a

The element of the partition to search.

Returns: 'a * int

The pair of the canonical element of a's equivalence class plus its size, if a is an element in the domain of the partition; otherwise (a, 1).

Example 

 let (Partition f as ptn) = 
   unequal
   |> equate (2,1) 
   |> equate (3,1)
   |> equate (4,1) 
   |> equate (6,5) 
   |> equate (7,5) 
 
 tryterminus ptn 3
val f: obj
val ptn: obj
Evaluates to (1, 4).

Example 

 let (Partition f as ptn) = 
   unequal
   |> equate (2,1) 
   |> equate (3,1)
   |> equate (4,1) 
   |> equate (6,5) 
   |> equate (7,5) 
 
 tryterminus ptn 8
val f: obj
val ptn: obj
Evaluates to (8, 1).

unequal

Full Usage: unequal

Returns: partition<'a> The empty partition.

The empty partition: used to define new partitions.

Returns: partition<'a>

The empty partition.