Module Lists.Assoc

empty is the empty alist.

(random ?size ~key ~value ()) is a random alist of size (size ()) (default: < 100), and each binding is given by (key (), value ()).

assoc is assoc.

find is assoc.

(bindings k alist) is the list of all bindings of key k in alist; tail recursive.

The bindings are returned in the order in which they occur.

Example:

• (bindings 2 [1,1;2,2;3,3;2,4]) = [2,2; 2,4]

Invariants:

• (bindings k [] = [])
• (assocs k alist |> map (cons k)) = (bindings k alist)
• (len (assocs k) = len (bindings k))

(assocs k alist) is the list of all the values in alist associated with key k; tail-recursive.

The values are in the order in which they occur in alist.

Example:

• (assocs 2 [1,1;2,2;3,3;2,4]) = [2; 4]

See also coalesce for an efficient way to do assocs for each key in an alist.

(keys alist) is the list of all the keys in alist, order preserved; tail-recursive.

(values alist) is the list of all the values in alist, order preserved; tail-recursive.

(project keys alist) is the subset of alist that contains only pairs with keys in keys.

mem is mem_assoc.

(has ?kf vf xs) is true if (kf k && vf v) for any (k,v) pair in alist xs and false otherwise.

The default value for kf is (k true).

(add k v alist) is ((k,v) :: alist).

remove_assoc is List.remove_assoc.

(remove k alist) is like remove_assoc except: 1. it removes ALL matching pairs (not just the first) and 2. remove is tail-recursive.

remove_keys igns alist is alist minus all associations whose keys are in igns.

(replace ?all (k,v) alist) replaces some or all of the bindings for k in alist with (k,v); tail recursive.

If (all = false) (the default) then only the first binding is replaced.

The order of the bindings in alist is always preserved.

Invariants:

• (replace (k,v) [] = [])
• (replace (k,v) >> replace (k,v) = replace (k,v))
• (replace (k,v) alist |> keys = keys alist)

(coalesce alist) converts an alist with repeating keys into one with unique keys bound to lists of values.

The order of elements in the result is sorted as by Stdlib.compare.

Invariants:

• (coalesce xs |> flatmap (fun (k,vs) -> map (Pair.up k) vs) |> sort compare) = (sort compare xs)
• (keys xs |> List.sort_uniq compare |> map (id *** flip assocs xs) |> sort compare) = (coalesce xs |> sort compare)

• author Matt Teichman

(adjoin vadd empty) returns a function (f alist k v) that adjoins v to a collection of values associated with key k in association list alist; O(n).

See Map.Make.adjoin (which is more efficient) for a discussion and example.

(classify f add z x alist) returns a classifying adjoiner.

add could be cons and z, [], or add could be S.add and z, S.empty for some Set S.

f is a function that classifies an 'a by mapping it to some equivalence class; f could be even, or String.lowercase_ascii.

For example, foldr (classify even cons []) [] applied to an int list returns an alist of length 2 (the size of the codomain of even) mapping true to a list of even integers and false to a list of odd integers.

(incr ?z ?i k alist) is (adjoin (+) z k i alist), i.e. incr generates a function for counting instances of items (k) in an alist.

~z is the "zero" for the counters (default: 0); ~i is the increment (default: 1).

(merge xs ys) merges the two alists; bindings in xs trump bindings in ys.

The order of the results is undefined.

(mergelong xs ys) is exactly the same as merge, but is significantly faster (up to 27 times) for long alists (100+).

(to_string ?left ?sep ?right f g xs) returns a string representation of xs.

to_string is (List.to_string ?left ?sep ?right (Pair.to_string f g)).

(print ?left ?sep ?right f g xs) is (to_string ?left ?sep ?right f g xs >> print_endline).