%--------------------------------------------------% % vim: ft=mercury ts=4 sw=4 et %--------------------------------------------------% % Copyright (C) 1995-1997, 1999-2001, 2004-2006, 2010-2011 The University of Melbourne. % Copyright (C) 2013-2018 The Mercury team. % This file is distributed under the terms specified in COPYING.LIB. %--------------------------------------------------% % % File: assoc_list.m. % Main authors: fjh, zs. % Stability: medium to high. % % This file contains the definition of the type assoc_list(K, V) % and some predicates which operate on those types. % %--------------------------------------------------% %--------------------------------------------------% :- module assoc_list. :- interface. :- import_module list. :- import_module pair. %--------------------------------------------------% :- type assoc_list(K, V) == list(pair(K, V)). :- type assoc_list(T) == list(pair(T, T)). % Swap the two sides of the pairs in each member of the list. % :- func reverse_members(assoc_list(K, V)) = assoc_list(V, K). :- pred reverse_members(assoc_list(K, V)::in, assoc_list(V, K)::out) is det. % Zip together two lists. % Throw an exception if they are of different lengths. % :- func from_corresponding_lists(list(K), list(V)) = assoc_list(K, V). :- pred from_corresponding_lists(list(K)::in, list(V)::in, assoc_list(K, V)::out) is det. % Return the first member of each pair. % :- func keys(assoc_list(K, V)) = list(K). :- pred keys(assoc_list(K, V)::in, list(K)::out) is det. % Return the second member of each pair. % :- func values(assoc_list(K, V)) = list(V). :- pred values(assoc_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 assoc_list. % :- pred keys_and_values(assoc_list(K, V)::in, list(K)::out, list(V)::out) is det. % Find the first element of the association list that matches % the given key, and return the associated value. % :- pred search(assoc_list(K, V)::in, K::in, V::out) is semidet. % An alternative version of search. % :- func assoc_list(K, V) ^ elem(K) = V is semidet. % An alternative version of search that throws an exception if the key in % question does not appear in the assoc_list. % :- func assoc_list(K, V) ^ det_elem(K) = V is det. % 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(assoc_list(K, V)::in, K::in, V::out, assoc_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, assoc_list(K, V)::in, assoc_list(K, V)::out) is semidet. :- func map_keys_only(func(K) = L, assoc_list(K, V)) = assoc_list(L, V). :- pred map_keys_only(pred(K, L), assoc_list(K, V), assoc_list(L, V)). :- mode map_keys_only(pred(in, out) is det, in, out) is det. :- func map_values_only(func(V) = W, assoc_list(K, V)) = assoc_list(K, W). :- pred map_values_only(pred(V, W), assoc_list(K, V), assoc_list(K, W)). :- mode map_values_only(pred(in, out) is det, in, out) is det. :- func map_values(func(K, V) = W, assoc_list(K, V)) = assoc_list(K, W). :- pred map_values(pred(K, V, W), assoc_list(K, V), assoc_list(K, W)). :- mode map_values(pred(in, in, out) is det, in, out) is det. % filter(Pred, List, TrueList) takes a closure with one % input argument and for each member K - V of List X, calls the closure % on the key. K - V is included in TrueList iff Pred(K) is true. % :- pred filter(pred(K)::in(pred(in) is semidet), assoc_list(K, V)::in, assoc_list(K, V)::out) is det. :- func filter(pred(K)::in(pred(in) is semidet), assoc_list(K, V)::in) = (assoc_list(K, V)::out) is det. % negated_filter(Pred, List, FalseList) takes a closure with one % input argument and for each member K - V of List X, calls the closure % on the key. K - V is included in FalseList iff Pred(K) is false. % :- pred negated_filter(pred(K)::in(pred(in) is semidet), assoc_list(K, V)::in, assoc_list(K, V)::out) is det. :- func negated_filter(pred(K)::in(pred(in) is semidet), assoc_list(K, V)::in) = (assoc_list(K, V)::out) is det. % filter(Pred, List, TrueList, FalseList) takes a closure with % one input argument and for each member K - V of List X, calls the closure % on the key. K - V is included in TrueList iff Pred(K) is true. % K - V is included in FalseList iff Pred(K) is false. % :- pred filter(pred(K)::in(pred(in) is semidet), assoc_list(K, V)::in, assoc_list(K, V)::out, assoc_list(K, V)::out) is det. % 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(assoc_list(K, V), assoc_list(K, V)) = assoc_list(K, V). :- pred merge(assoc_list(K, V)::in, assoc_list(K, V)::in, assoc_list(K, V)::out) is det. % foldl_keys(Pred, List, Start End) calls Pred % with each key in List (working left-to-right) and an accumulator % (with initial value of Start), and returns the final value in End. % :- pred foldl_keys(pred(K, A, A), assoc_list(K, V), A, A). :- mode foldl_keys(pred(in, in, out) is det, in, in, out) is det. :- mode foldl_keys(pred(in, mdi, muo) is det, in, mdi, muo) is det. :- mode foldl_keys(pred(in, di, uo) is det, in, di, uo) is det. :- mode foldl_keys(pred(in, in, out) is semidet, in, in, out) is semidet. :- mode foldl_keys(pred(in, mdi, muo) is semidet, in, mdi, muo) is semidet. :- mode foldl_keys(pred(in, di, uo) is semidet, in, di, uo) is semidet. :- mode foldl_keys(pred(in, in, out) is multi, in, in, out) is multi. :- mode foldl_keys(pred(in, in, out) is nondet, in, in, out) is nondet. % foldl_values(Pred, List, Start End) calls Pred % with each value in List (working left-to-right) and an accumulator % (with initial value of Start), and returns the final value in End. % :- pred foldl_values(pred(V, A, A), assoc_list(K, V), A, A). :- mode foldl_values(pred(in, in, out) is det, in, in, out) is det. :- mode foldl_values(pred(in, mdi, muo) is det, in, mdi, muo) is det. :- mode foldl_values(pred(in, di, uo) is det, in, di, uo) is det. :- mode foldl_values(pred(in, in, out) is semidet, in, in, out) is semidet. :- mode foldl_values(pred(in, mdi, muo) is semidet, in, mdi, muo) is semidet. :- mode foldl_values(pred(in, di, uo) is semidet, in, di, uo) is semidet. :- mode foldl_values(pred(in, in, out) is multi, in, in, out) is multi. :- mode foldl_values(pred(in, in, out) is nondet, in, in, out) is nondet. % As above, but with two accumulators. % :- pred foldl2_values(pred(V, A, A, B, B), assoc_list(K, V), A, A, B, B). :- mode foldl2_values(pred(in, in, out, in, out) is det, in, in, out, in, out) is det. :- mode foldl2_values(pred(in, in, out, mdi, muo) is det, in, in, out, mdi, muo) is det. :- mode foldl2_values(pred(in, in, out, di, uo) is det, in, in, out, di, uo) is det. :- mode foldl2_values(pred(in, in, out, in, out) is semidet, in, in, out, in, out) is semidet. :- mode foldl2_values(pred(in, in, out, mdi, muo) is semidet, in, in, out, mdi, muo) is semidet. :- mode foldl2_values(pred(in, in, out, di, uo) is semidet, in, in, out, di, uo) is semidet. :- mode foldl2_values(pred(in, in, out, in, out) is multi, in, in, out, in, out) is multi. :- mode foldl2_values(pred(in, in, out, in, out) is nondet, in, in, out, in, out) is nondet. % As above, but with three accumulators. % :- pred foldl3_values(pred(V, A, A, B, B, C, C), assoc_list(K, V), A, A, B, B, C, C). :- mode foldl3_values(pred(in, in, out, in, out, in, out) is det, in, in, out, in, out, in, out) is det. :- mode foldl3_values(pred(in, in, out, in, out, mdi, muo) is det, in, in, out, in, out, mdi, muo) is det. :- mode foldl3_values(pred(in, in, out, in, out, di, uo) is det, in, in, out, in, out, di, uo) is det. :- mode foldl3_values(pred(in, in, out, in, out, in, out) is semidet, in, in, out, in, out, in, out) is semidet. :- mode foldl3_values(pred(in, in, out, in, out, mdi, muo) is semidet, in, in, out, in, out, mdi, muo) is semidet. :- mode foldl3_values(pred(in, in, out, in, out, di, uo) is semidet, in, in, out, in, out, di, uo) is semidet. :- mode foldl3_values(pred(in, in, out, in, out, in, out) is multi, in, in, out, in, out, in, out) is multi. :- mode foldl3_values(pred(in, in, out, in, out, in, out) is nondet, in, in, out, in, out, in, out) is nondet. %--------------------------------------------------% %--------------------------------------------------%