Skip to content

Latest commit

 

History

History
81 lines (61 loc) · 2.68 KB

AssocList.md

File metadata and controls

81 lines (61 loc) · 2.68 KB
Raw

AssocList

Lists of key-value entries ("associations").

Implements the same operations as library Trie, but uses a linked-list of entries and no hashing.

Type AssocList

type AssocList<K, V> = List.List<(K, V)>

polymorphic association linked lists between keys and values

Function find

func find<K, V>(al : AssocList<K, V>, k : K, k_eq : (K, K) -> Bool) : ?V

Find the value associated with a given key, or null if absent.

Function replace

func replace<K, V>(al : AssocList<K, V>, k : K, k_eq : (K, K) -> Bool, ov : ?V) : (AssocList<K, V>, ?V)

replace the value associated with a given key, or add it, if missing. returns old value, or null, if no prior value existed.

Function diff

func diff<K, V, W>(al1 : AssocList<K, V>, al2 : AssocList<K, W>, keq : (K, K) -> Bool) : AssocList<K, V>

The entries of the final list consist of those pairs of the left list whose keys are not present in the right list; the "extra" values of the right list are irrelevant.

Function mapAppend

func mapAppend<K, V, W, X>(al1 : AssocList<K, V>, al2 : AssocList<K, W>, vbin : (?V, ?W) -> X) : AssocList<K, X>

Transform and combine the entries of two association lists.

Function disjDisjoint

func disjDisjoint<K, V, W, X>(al1 : AssocList<K, V>, al2 : AssocList<K, W>, vbin : (?V, ?W) -> X) : AssocList<K, X>

Specialized version of disj, optimized for disjoint sub-spaces of keyspace (no matching keys).

Function disj

func disj<K, V, W, X>(al1 : AssocList<K, V>, al2 : AssocList<K, W>, keq : (K, K) -> Bool, vbin : (?V, ?W) -> X) : AssocList<K, X>

This operation generalizes the notion of "set union" to finite maps. Produces a "disjunctive image" of the two lists, where the values of matching keys are combined with the given binary operator.

For unmatched entries, the operator is still applied to create the value in the image. To accomodate these various situations, the operator accepts optional values, but is never applied to (null, null).

Function join

func join<K, V, W, X>(al1 : AssocList<K, V>, al2 : AssocList<K, W>, keq : (K, K) -> Bool, vbin : (V, W) -> X) : AssocList<K, X>

This operation generalizes the notion of "set intersection" to finite maps. Produces a "conjuctive image" of the two lists, where the values of matching keys are combined with the given binary operator, and unmatched entries are not present in the output.

Function fold

func fold<K, V, X>(al : AssocList<K, V>, nil : X, cons : (K, V, X) -> X) : X

Fold the entries based on the recursive list structure.