%--------------------------------------------------%
% vim: ft=mercury ts=4 sw=4 et
%--------------------------------------------------%
% Copyright (C) 2020, 2023 The Mercury team.
% This file is distributed under the terms specified in COPYING.LIB.
%--------------------------------------------------%
%
% File: kv_list.m.
% Main author: zs.
% Stability: medium to high.
%
% This file defines the type kv_list(K, V), which represents lists of
% key-value pairs, and provides a range of operations on such lists.
%
% The kv_list module resembles the assoc_list module quite closely.
% The data type it defines stores the same information, and the set
% of operations they provide is the same, modulo the fact that the
% operations that convert between the two representations are here.
% The difference is that kv_list uses one memory cell, not two,
% to represent one key-value pair, which should mean that it requires
% fewer memory allocations. On the other hand, values of type assoc_list
% may be operated on as plain lists, while this cannot be done on values
% of type kv_list.
%
%--------------------------------------------------%
%--------------------------------------------------%
:- module kv_list.
:- interface.
:- import_module assoc_list.
:- import_module list.
%--------------------------------------------------%
:- type kv_list(K, V)
---> kv_nil
; kv_cons(K, V, kv_list(K, V)).
%--------------------------------------------------%
%
% Creating kv_lists from lists of keys and values.
%
% Zip together a list of keys and a list of values.
% Throw an exception if they are of different lengths.
%
:- func from_corresponding_lists(list(K), list(V)) = kv_list(K, V).
:- pred from_corresponding_lists(list(K)::in, list(V)::in,
kv_list(K, V)::out) is det.
%--------------------------------------------------%
%
% Conversion to and from assoc_lists.
%
:- func assoc_list_to_kv_list(assoc_list(K, V)) = kv_list(K, V).
:- func kv_list_to_assoc_list(kv_list(K, V)) = assoc_list(K, V).
%--------------------------------------------------%
%
% Operations on lists of keys and/or values.
%
% Swap the two sides of the pairs in each member of the list.
%
:- func reverse_members(kv_list(K, V)) = kv_list(V, K).
:- pred reverse_members(kv_list(K, V)::in, kv_list(V, K)::out) is det.
% Return the first member of each pair.
%
:- func keys(kv_list(K, V)) = list(K).
:- pred keys(kv_list(K, V)::in, list(K)::out) is det.
% Return the second member of each pair.
%
:- func values(kv_list(K, V)) = list(V).
:- pred values(kv_list(K, V)::in, list(V)::out) is det.
% Return two lists containing respectively the first and the second member
% of each pair in the kv_list.
%
:- pred keys_and_values(kv_list(K, V)::in, list(K)::out, list(V)::out) is det.
%--------------------------------------------------%
%
% Searching kv_lists.
%
% Find the first element of the kv_list list that matches
% the given key, and return the associated value.
% Fail if there is no matching key.
%
:- pred search(kv_list(K, V)::in, K::in, V::out) is semidet.
% Find the first element of the kv_list list that matches
% the given key, and return the associated value.
% Throw an exception if there is no matching key.
%
:- pred lookup(kv_list(K, V)::in, K::in, V::out) is det.
% A field access version of search.
%
:- func kv_list(K, V) ^ elem(K) = V is semidet.
% A field access version of lookup.
%
:- func kv_list(K, V) ^ det_elem(K) = V is det.
%--------------------------------------------------%
%
% Updating elements in kv_lists.
%
% Find the first element of the kv_list list that matches
% the given key, and update the associated value.
% Fail if there is no matching key.
%
:- pred update(K::in, V::in, kv_list(K, V)::in, kv_list(K, V)::out)
is semidet.
%--------------------------------------------------%
%
% Removing elements from kv_lists.
%
% Find the first element of the association list that matches the given
% key. Return the associated value, and the original list with the selected
% element removed.
%
:- pred remove(kv_list(K, V)::in, K::in, V::out, kv_list(K, V)::out)
is semidet.
% As above, but with an argument ordering that is more conducive to
% the use of state variable notation.
%
:- pred svremove(K::in, V::out, kv_list(K, V)::in, kv_list(K, V)::out)
is semidet.
%--------------------------------------------------%
%
% Mapping keys or values.
%
:- func map_keys_only(func(K) = L, kv_list(K, V)) = kv_list(L, V).
:- pred map_keys_only(pred(K, L)::in(pred(in, out) is det),
kv_list(K, V)::in, kv_list(L, V)::out) is det.
:- func map_values_only(func(V) = W, kv_list(K, V)) = kv_list(K, W).
:- pred map_values_only(pred(V, W)::in(pred(in, out) is det),
kv_list(K, V)::in, kv_list(K, W)::out) is det.
:- func map_values(func(K, V) = W, kv_list(K, V)) = kv_list(K, W).
:- pred map_values(pred(K, V, W)::in(pred(in, in, out) is det),
kv_list(K, V)::in, kv_list(K, W)::out) is det.
%--------------------------------------------------%
%
% Filtering elements in kv_lists.
%
% filter(Pred, List, TrueList) takes a closure with one input argument,
% and for each key-value pair in List, calls the closure on the key K.
% The key-value pair is included in TrueList iff Pred(K) is true.
%
:- func filter(pred(K)::in(pred(in) is semidet),
kv_list(K, V)::in) = (kv_list(K, V)::out) is det.
:- pred filter(pred(K)::in(pred(in) is semidet),
kv_list(K, V)::in, kv_list(K, V)::out) is det.
% negated_filter(Pred, List, FalseList) takes a closure with one
% input argument, and for each key-value pair in List, calls the closure
% on the key K. The key-value pair is included in TrueList iff Pred(K)
% is false.
%
:- func negated_filter(pred(K)::in(pred(in) is semidet),
kv_list(K, V)::in) = (kv_list(K, V)::out) is det.
:- pred negated_filter(pred(K)::in(pred(in) is semidet),
kv_list(K, V)::in, kv_list(K, V)::out) is det.
% filter(Pred, List, TrueList, FalseList) takes a closure with
% one input argument, and for each key-value pair in List,
% calls the closure on the key K. If Pred(K) is true, the key-value pair
% is included in TrueList; otherwise, it is included in FalseList.
%
:- pred filter(pred(K)::in(pred(in) is semidet),
kv_list(K, V)::in, kv_list(K, V)::out, kv_list(K, V)::out) is det.
%--------------------------------------------------%
%
% Merging kv_lists.
%
% merge(L1, L2, L):
%
% L is the result of merging the elements of L1 and L2, in ascending order.
% L1 and L2 must be sorted on the keys.
%
:- func merge(kv_list(K, V), kv_list(K, V)) = kv_list(K, V).
:- pred merge(kv_list(K, V)::in, kv_list(K, V)::in,
kv_list(K, V)::out) is det.
%--------------------------------------------------%
%
% Folding over kv_lists.
%
% foldl(Func, List, Start) = End calls Func
% with each key-value in List, working left-to-right,
% and an accumulator whose initial value is Start,
% and returns the final value in End.
%
:- func foldl(func(K, V, A) = A, kv_list(K, V), A) = A.
% foldl(Pred, List, Start End) calls Pred
% with each key-value pair in List, working left-to-right,
% and an accumulator whose initial value is Start,
% and returns the final value in End.
%
:- pred foldl(pred(K, V, A, A), kv_list(K, V), A, A).
:- mode foldl(in(pred(in, in, in, out) is det), in, in, out) is det.
:- mode foldl(in(pred(in, in, mdi, muo) is det), in, mdi, muo) is det.
:- mode foldl(in(pred(in, in, di, uo) is det), in, di, uo) is det.
:- mode foldl(in(pred(in, in, in, out) is semidet), in, in, out) is semidet.
:- mode foldl(in(pred(in, in, mdi, muo) is semidet), in, mdi, muo) is semidet.
:- mode foldl(in(pred(in, in, di, uo) is semidet), in, di, uo) is semidet.
:- mode foldl(in(pred(in, in, in, out) is nondet), in, in, out) is nondet.
% foldl_keys(Func List, Start) = End calls Func
% with each key in List, working left-to-right, and an accumulator
% whose initial value is Start, and returns the final value in End.
%
:- func foldl_keys(func(K, A) = A, kv_list(K, V), A) = A.
% foldl_keys(Pred, List, Start End) calls Pred
% with each key in List, working left-to-right, and an accumulator
% whose initial value is Start, and returns the final value in End.
%
:- pred foldl_keys(pred(K, A, A), kv_list(K, V), A, A).
:- mode foldl_keys(in(pred(in, in, out) is det), in, in, out) is det.
:- mode foldl_keys(in(pred(in, mdi, muo) is det), in, mdi, muo) is det.
:- mode foldl_keys(in(pred(in, di, uo) is det), in, di, uo) is det.
:- mode foldl_keys(in(pred(in, in, out) is semidet), in, in, out) is semidet.
:- mode foldl_keys(in(pred(in, mdi, muo) is semidet), in, mdi, muo) is semidet.
:- mode foldl_keys(in(pred(in, di, uo) is semidet), in, di, uo) is semidet.
:- mode foldl_keys(in(pred(in, in, out) is multi), in, in, out) is multi.
:- mode foldl_keys(in(pred(in, in, out) is nondet), in, in, out) is nondet.
% foldl_values(Func List, Start) = End calls Func
% with each value in List, working left-to-right, and an accumulator
% whose initial value is Start, and returns the final value in End.
%
:- func foldl_values(func(V, A) = A, kv_list(K, V), A) = A.
% foldl_values(Pred, List, Start End) calls Pred
% with each value in List, working left-to-right, and an accumulator
% whose initial value is Start, and returns the final value in End.
%
:- pred foldl_values(pred(V, A, A), kv_list(K, V), A, A).
:- mode foldl_values(in(pred(in, in, out) is det), in,
in, out) is det.
:- mode foldl_values(in(pred(in, mdi, muo) is det), in,
mdi, muo) is det.
:- mode foldl_values(in(pred(in, di, uo) is det), in,
di, uo) is det.
:- mode foldl_values(in(pred(in, in, out) is semidet), in,
in, out) is semidet.
:- mode foldl_values(in(pred(in, mdi, muo) is semidet), in,
mdi, muo) is semidet.
:- mode foldl_values(in(pred(in, di, uo) is semidet), in,
di, uo) is semidet.
:- mode foldl_values(in(pred(in, in, out) is multi), in,
in, out) is multi.
:- mode foldl_values(in(pred(in, in, out) is nondet), in,
in, out) is nondet.
% As foldl, but with two accumulators.
%
:- pred foldl2(pred(K, V, A, A, B, B), kv_list(K, V), A, A, B, B).
:- mode foldl2(in(pred(in, in, in, out, in, out) is det), in, in, out,
in, out) is det.
:- mode foldl2(in(pred(in, in, in, out, mdi, muo) is det), in, in, out,
mdi, muo) is det.
:- mode foldl2(in(pred(in, in, in, out, di, uo) is det), in, in, out,
di, uo) is det.
:- mode foldl2(in(pred(in, in, in, out, in, out) is semidet), in, in, out,
in, out) is semidet.
:- mode foldl2(in(pred(in, in, in, out, mdi, muo) is semidet), in,in, out,
mdi, muo) is semidet.
:- mode foldl2(in(pred(in, in, in, out, di, uo) is semidet), in, in, out,
di, uo) is semidet.
:- mode foldl2(in(pred(in, in, in, out, in, out) is nondet), in, in, out,
in, out) is nondet.
% As foldl_values, but with two accumulators.
%
:- pred foldl2_values(pred(V, A, A, B, B), kv_list(K, V),
A, A, B, B).
:- mode foldl2_values(in(pred(in, in, out, in, out) is det), in,
in, out, in, out) is det.
:- mode foldl2_values(in(pred(in, in, out, mdi, muo) is det), in,
in, out, mdi, muo) is det.
:- mode foldl2_values(in(pred(in, in, out, di, uo) is det), in,
in, out, di, uo) is det.
:- mode foldl2_values(in(pred(in, in, out, in, out) is semidet), in,
in, out, in, out) is semidet.
:- mode foldl2_values(in(pred(in, in, out, mdi, muo) is semidet), in,
in, out, mdi, muo) is semidet.
:- mode foldl2_values(in(pred(in, in, out, di, uo) is semidet), in,
in, out, di, uo) is semidet.
:- mode foldl2_values(in(pred(in, in, out, in, out) is multi), in,
in, out, in, out) is multi.
:- mode foldl2_values(in(pred(in, in, out, in, out) is nondet), in,
in, out, in, out) is nondet.
% As foldl, but with three accumulators.
%
:- pred foldl3(pred(K, V, A, A, B, B, C, C), kv_list(K, V),
A, A, B, B, C, C).
:- mode foldl3(in(pred(in, in, in, out, in, out, in, out) is det), in,
in, out, in, out, in, out) is det.
:- mode foldl3(in(pred(in, in, in, out, in, out, mdi, muo) is det), in,
in, out, in, out, mdi, muo) is det.
:- mode foldl3(in(pred(in, in, in, out, in, out, di, uo) is det), in,
in, out, in, out, di, uo) is det.
:- mode foldl3(in(pred(in, in, in, out, in, out, in, out) is semidet), in,
in, out, in, out, in, out) is semidet.
:- mode foldl3(in(pred(in, in, in, out, in, out, mdi, muo) is semidet), in,
in, out, in, out, mdi, muo) is semidet.
:- mode foldl3(in(pred(in, in, in, out, in, out, di, uo) is semidet), in,
in, out, in, out, di, uo) is semidet.
:- mode foldl3(in(pred(in, in, in, out, in, out, in, out) is nondet), in,
in, out, in, out, in, out) is nondet.
% As foldl_values, but with three accumulators.
%
:- pred foldl3_values(pred(V, A, A, B, B, C, C), kv_list(K, V),
A, A, B, B, C, C).
:- mode foldl3_values(in(pred(in, in, out, in, out, in, out) is det),
in, in, out, in, out, in, out) is det.
:- mode foldl3_values(in(pred(in, in, out, in, out, mdi, muo) is det),
in, in, out, in, out, mdi, muo) is det.
:- mode foldl3_values(in(pred(in, in, out, in, out, di, uo) is det),
in, in, out, in, out, di, uo) is det.
:- mode foldl3_values(in(pred(in, in, out, in, out, in, out) is semidet),
in, in, out, in, out, in, out) is semidet.
:- mode foldl3_values(in(pred(in, in, out, in, out, mdi, muo) is semidet),
in, in, out, in, out, mdi, muo) is semidet.
:- mode foldl3_values(in(pred(in, in, out, in, out, di, uo) is semidet),
in, in, out, in, out, di, uo) is semidet.
:- mode foldl3_values(in(pred(in, in, out, in, out, in, out) is multi),
in, in, out, in, out, in, out) is multi.
:- mode foldl3_values(in(pred(in, in, out, in, out, in, out) is nondet),
in, in, out, in, out, in, out) is nondet.
%--------------------------------------------------%
%--------------------------------------------------%