mirror of
https://github.com/Mercury-Language/mercury.git
synced 2026-04-15 09:23:44 +00:00
778e75f696
library/array.m:
library/builtin.m:
library/construct.m:
Fix copy-and-paste errors.
library/arrayd2d.m:
Use the mode array2d_di instead of array_di in a spot.
Delete an extra space from an exception message.
library/bimap.m:
Fix formatting.
library/bit_buffer.m:
Fix inverted argument types.
library/dir.m:
Say that make_single_directory/4 returns an error rather
than saying that it fails.
library/io.m:
Fix errors in obsolete pragmas.
library/assoc_list.m:
library/bag.m:
library/cord.m:
library/deconstruct.m:
library/enum.m:
library/fat_sparse_bitset.m:
library/getopt*.m:
library/int*.m:
library/io*.m:
library/type_desc.m:
Fix documentation errors.
tests/hard_coded/array2d_from_array.exp:
Conform to the changed exception message in array2d.m.
677 lines
23 KiB
Mathematica
677 lines
23 KiB
Mathematica
%---------------------------------------------------------------------------%
|
|
% 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-2023, 2025-2026 The Mercury team.
|
|
% This file is distributed under the terms specified in COPYING.LIB.
|
|
%---------------------------------------------------------------------------%
|
|
%
|
|
% File: assoc_list.m.
|
|
% Main authors: fjh, zs.
|
|
% Stability: high.
|
|
%
|
|
% This file defines the type assoc_list(K, V), which holds a list of
|
|
% key-value pairs, and some predicates which operate on assoc_lists.
|
|
%
|
|
% Another module of the Mercury standard library, kv_list.m, defines
|
|
% another data type that does the same job, but makes different tradeoffs.
|
|
%
|
|
%---------------------------------------------------------------------------%
|
|
%---------------------------------------------------------------------------%
|
|
|
|
:- 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)).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
% These instantiation states can be used for instantiation
|
|
% state subtyping.
|
|
%
|
|
:- inst assoc_list(I1, I2) == list(pair(I1, I2)).
|
|
|
|
:- inst assoc_list(I) == list(pair(I, I)).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
%
|
|
% Creating assoc_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)) = assoc_list(K, V).
|
|
:- pred from_corresponding_lists(list(K)::in, list(V)::in,
|
|
assoc_list(K, V)::out) is det.
|
|
|
|
% Zip together a list of keys and a list of values.
|
|
% Fail if they are of different lengths.
|
|
%
|
|
:- pred maybe_from_corresponding_lists(list(K)::in, list(V)::in,
|
|
assoc_list(K, V)::out) is semidet.
|
|
|
|
%---------------------------------------------------------------------------%
|
|
%
|
|
% Operations on lists of keys and/or values.
|
|
%
|
|
|
|
% 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.
|
|
|
|
% 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.
|
|
|
|
%---------------------------------------------------------------------------%
|
|
%
|
|
% Searching assoc_lists.
|
|
%
|
|
|
|
% Find the first element of the association list that matches
|
|
% the given key, and return the associated value.
|
|
% Fail if there is no matching key.
|
|
%
|
|
:- pred search(assoc_list(K, V)::in, K::in, V::out) is semidet.
|
|
|
|
% Find the first element of the association list that matches
|
|
% the given key, and return the associated value.
|
|
% Throw an exception if there is no matching key.
|
|
%
|
|
:- pred lookup(assoc_list(K, V)::in, K::in, V::out) is det.
|
|
|
|
% A field access version of search.
|
|
%
|
|
:- func assoc_list(K, V) ^ elem(K) = V is semidet.
|
|
% NOTE_TO_IMPLEMENTORS CFF :- pragma obsolete(func(elem/2), [search/3]).
|
|
|
|
% A field access version of lookup.
|
|
%
|
|
:- func assoc_list(K, V) ^ det_elem(K) = V is det.
|
|
|
|
%---------------------------------------------------------------------------%
|
|
%
|
|
% Updating elements in assoc_lists.
|
|
%
|
|
|
|
% Find the first element of the association list that matches
|
|
% the given key, and update the associated value.
|
|
% Fail if there is no matching key.
|
|
%
|
|
:- pred update(K::in, V::in, assoc_list(K, V)::in, assoc_list(K, V)::out)
|
|
is semidet.
|
|
|
|
%---------------------------------------------------------------------------%
|
|
%
|
|
% Removing elements from assoc_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(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.
|
|
|
|
%---------------------------------------------------------------------------%
|
|
%
|
|
% Mapping keys or values.
|
|
%
|
|
|
|
:- func map_keys_only(func(K) = L, assoc_list(K, V)) = assoc_list(L, V).
|
|
:- pred map_keys_only(pred(K, L)::in(pred(in, out) is det),
|
|
assoc_list(K, V)::in, assoc_list(L, V)::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)::in(pred(in, out) is det),
|
|
assoc_list(K, V)::in, assoc_list(K, W)::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)::in(pred(in, in, out) is det),
|
|
assoc_list(K, V)::in, assoc_list(K, W)::out) is det.
|
|
|
|
%---------------------------------------------------------------------------%
|
|
%
|
|
% Filtering elements in assoc_lists.
|
|
%
|
|
|
|
% filter(Pred, List, TrueList):
|
|
%
|
|
% Given a closure containing a predicate with one input argument,
|
|
% and a list of key-value pairs, call the closure on each key K.
|
|
% Include the key-value pair in TrueList if-and-only-if Pred(K) is true.
|
|
%
|
|
:- func filter(pred(K)::in(pred(in) is semidet),
|
|
assoc_list(K, V)::in) = (assoc_list(K, V)::out) is det.
|
|
:- pred 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):
|
|
%
|
|
% Given a closure containing a predicate with one input argument,
|
|
% and a list of key-value pairs, call the closure on each key K.
|
|
% Include the key-value pair in FalseList if-and-only-if Pred(K) is false.
|
|
%
|
|
:- func negated_filter(pred(K)::in(pred(in) is semidet),
|
|
assoc_list(K, V)::in) = (assoc_list(K, V)::out) is det.
|
|
:- pred 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):
|
|
%
|
|
% Given a closure containing a predicate with one input argument,
|
|
% and a list of key-value pairs, call the closure on each key K.
|
|
% Include the key-value pair in TrueList if-and-only-if Pred(K) is true.
|
|
% Include the key-value pair in FalseList if-and-only-if 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.
|
|
|
|
%---------------------------------------------------------------------------%
|
|
%
|
|
% Operations on two assoc_lists.
|
|
%
|
|
|
|
% merge(ListA, ListB, ListAB):
|
|
%
|
|
% Given two lists ListA and ListB, which must both be sorted
|
|
% in ascending order on the keys, return ListAB, which is the result
|
|
% of merging the elements of ListA and ListB. It will also be sorted
|
|
% in ascending order.
|
|
%
|
|
:- 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.
|
|
|
|
% common_subset(ListA, ListB, CommonList):
|
|
%
|
|
% Given two lists ListA and ListB, which must both be sorted
|
|
% in ascending order on the keys, neither of which contains any key
|
|
% more than once, return CommonList, which will consist of only the
|
|
% key-value pairs that occur in *both* ListA and ListB.
|
|
% It will also be sorted in ascending order on the keys.
|
|
%
|
|
:- func common_subset(assoc_list(K, V), assoc_list(K, V)) = assoc_list(K, V).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
%
|
|
% Folding over assoc_lists.
|
|
%
|
|
|
|
% foldl(Pred, List, Start, End):
|
|
%
|
|
% Call Pred with each key-value pair in List, working left-to-right.
|
|
% Each call updates the value of an accumulator. The initial value
|
|
% of this accumulator is passed by the caller as Start; this predicate
|
|
% returns its final value as End.
|
|
%
|
|
:- pred foldl(pred(K, V, A, A), assoc_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:
|
|
% foldl_keys(Pred, List, Start, End):
|
|
%
|
|
% Call Func or Pred with the keys in List, working left-to-right.
|
|
% Each call updates the value of an accumulator. The initial value
|
|
% of this accumulator is passed by the caller as Start; this predicate
|
|
% returns its final value as End.
|
|
%
|
|
:- func foldl_keys(func(K, A) = A, assoc_list(K, V), A) = A.
|
|
:- pred foldl_keys(pred(K, A, A), assoc_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:
|
|
% foldl_values(Pred, List, Start, End):
|
|
%
|
|
% Call Func or Pred with the values in List, working left-to-right.
|
|
% Each call updates the value of an accumulator. The initial value
|
|
% of this accumulator is passed by the caller as Start; this predicate
|
|
% returns its final value as End.
|
|
%
|
|
:- func foldl_values(func(V, A) = A, assoc_list(K, V), A) = A.
|
|
:- pred foldl_values(pred(V, A, A), assoc_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.
|
|
|
|
% Does the same job as foldl, but with two accumulators.
|
|
%
|
|
:- pred foldl2(pred(K, V, A, A, B, B), assoc_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.
|
|
|
|
% Does the same job as foldl_values, but with two accumulators.
|
|
%
|
|
:- pred foldl2_values(pred(V, A, A, B, B), assoc_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.
|
|
|
|
% Does the same job as foldl, but with three accumulators.
|
|
%
|
|
:- pred foldl3(pred(K, V, A, A, B, B, C, C), assoc_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.
|
|
|
|
% Does the same job as foldl_values, 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(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.
|
|
|
|
%---------------------------------------------------------------------------%
|
|
%---------------------------------------------------------------------------%
|
|
|
|
:- implementation.
|
|
|
|
:- import_module require.
|
|
:- import_module string.
|
|
:- import_module type_desc.
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
from_corresponding_lists(Ks, Vs) = AL :-
|
|
assoc_list.from_corresponding_lists(Ks, Vs, AL).
|
|
|
|
from_corresponding_lists(Ks, Vs, KVs) :-
|
|
( if assoc_list.from_corresponding_loop(Ks, Vs, KVsPrime) then
|
|
KVs = KVsPrime
|
|
else
|
|
KeyType = type_name(type_of(Ks)),
|
|
list.length(Ks, KeyLength),
|
|
string.int_to_string(KeyLength, KeyLengthString),
|
|
ValueType = type_name(type_of(Vs)),
|
|
list.length(Vs, ValueLength),
|
|
string.int_to_string(ValueLength, ValueLengthString),
|
|
ErrorString =
|
|
"Lists have different lengths.\n"
|
|
++ "\tKey list type: " ++ KeyType
|
|
++ "\n\tKey list length: " ++ KeyLengthString
|
|
++ "\n\tValue list type: " ++ ValueType
|
|
++ "\n\tValue list length: " ++ ValueLengthString,
|
|
unexpected($pred, ErrorString)
|
|
).
|
|
|
|
maybe_from_corresponding_lists(Ks, Vs, KVs) :-
|
|
assoc_list.from_corresponding_loop(Ks, Vs, KVs).
|
|
|
|
:- pred from_corresponding_loop(list(K)::in, list(V)::in,
|
|
assoc_list(K,V)::out) is semidet.
|
|
|
|
from_corresponding_loop([], [], []).
|
|
from_corresponding_loop([A | As], [B | Bs], [A - B | ABs]) :-
|
|
assoc_list.from_corresponding_loop(As, Bs, ABs).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
reverse_members(AL1) = AL2 :-
|
|
assoc_list.reverse_members(AL1, AL2).
|
|
|
|
reverse_members([], []).
|
|
reverse_members([K - V | KVs], [V - K | VKs]) :-
|
|
assoc_list.reverse_members(KVs, VKs).
|
|
|
|
keys(AL) = Ks :-
|
|
assoc_list.keys(AL, Ks).
|
|
|
|
keys([], []).
|
|
keys([K - _ | KVs], [K | Ks]) :-
|
|
assoc_list.keys(KVs, Ks).
|
|
|
|
values(AL) = Vs :-
|
|
assoc_list.values(AL, Vs).
|
|
|
|
values([], []).
|
|
values([_ - V | KVs], [V | Vs]) :-
|
|
assoc_list.values(KVs, Vs).
|
|
|
|
keys_and_values([], [], []).
|
|
keys_and_values([K - V | KVs], [K | Ks], [V | Vs]) :-
|
|
assoc_list.keys_and_values(KVs, Ks, Vs).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
search([K - V | KVs], Key, Value) :-
|
|
( if K = Key then
|
|
Value = V
|
|
else
|
|
assoc_list.search(KVs, Key, Value)
|
|
).
|
|
|
|
lookup(KVs, K, V) :-
|
|
( if assoc_list.search(KVs, K, VPrime) then
|
|
V = VPrime
|
|
else
|
|
report_lookup_error("assoc_list.lookup: key not found", K)
|
|
).
|
|
|
|
AL ^ elem(K) = V :-
|
|
assoc_list.search(AL, K, V).
|
|
|
|
AL ^ det_elem(K) = V :-
|
|
assoc_list.lookup(AL, K, V).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
update(Key, Value, KVs0, KVs) :-
|
|
require_complete_switch [KVs0]
|
|
(
|
|
KVs0 = [],
|
|
fail
|
|
;
|
|
KVs0 = [K - V | TailKVs0],
|
|
( if Key = K then
|
|
KVs = [K - Value | TailKVs0]
|
|
else
|
|
update(Key, Value, TailKVs0, TailKVs),
|
|
KVs = [K - V | TailKVs]
|
|
)
|
|
).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
remove([K - V | KVs], Key, Value, Filtered) :-
|
|
( if K = Key then
|
|
Value = V,
|
|
Filtered = KVs
|
|
else
|
|
assoc_list.remove(KVs, Key, Value, FilteredTail),
|
|
Filtered = [K - V | FilteredTail]
|
|
).
|
|
|
|
svremove(Key, Value, !AL) :-
|
|
assoc_list.remove(!.AL, Key, Value, !:AL).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
map_keys_only(_F, []) = [].
|
|
map_keys_only(F, [K0 - V | KVs0]) = [K - V | KVs] :-
|
|
K = F(K0),
|
|
KVs = assoc_list.map_keys_only(F, KVs0).
|
|
|
|
map_keys_only(_P, [], []).
|
|
map_keys_only(P, [K0 - V | KVs0], [K - V | KVs]) :-
|
|
P(K0, K),
|
|
assoc_list.map_keys_only(P, KVs0, KVs).
|
|
|
|
map_values_only(_F, []) = [].
|
|
map_values_only(F, [K - V0 | KVs0]) = [K - V | KVs] :-
|
|
V = F(V0),
|
|
KVs = assoc_list.map_values_only(F, KVs0).
|
|
|
|
map_values_only(_P, [], []).
|
|
map_values_only(P, [K - V0 | KVs0], [K - V | KVs]) :-
|
|
P(V0, V),
|
|
assoc_list.map_values_only(P, KVs0, KVs).
|
|
|
|
map_values(_F, []) = [].
|
|
map_values(F, [K - V0 | KVs0]) = [K - V | KVs] :-
|
|
V = F(K, V0),
|
|
KVs = assoc_list.map_values(F, KVs0).
|
|
|
|
map_values(_P, [], []).
|
|
map_values(P, [K - V0 | KVs0], [K - V | KVs]) :-
|
|
P(K, V0, V),
|
|
assoc_list.map_values(P, KVs0, KVs).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
filter(P, List) = Trues :-
|
|
assoc_list.filter(P, List, Trues).
|
|
|
|
filter(_, [], []).
|
|
filter(P, [HK - HV | T], True) :-
|
|
( if P(HK) then
|
|
assoc_list.filter(P, T, TrueTail),
|
|
True = [HK - HV | TrueTail]
|
|
else
|
|
assoc_list.filter(P, T, True)
|
|
).
|
|
|
|
negated_filter(P, List) = Falses :-
|
|
assoc_list.negated_filter(P, List, Falses).
|
|
|
|
negated_filter(_, [], []).
|
|
negated_filter(P, [HK - HV | T], False) :-
|
|
( if P(HK) then
|
|
assoc_list.negated_filter(P, T, False)
|
|
else
|
|
assoc_list.negated_filter(P, T, FalseTail),
|
|
False = [HK - HV | FalseTail]
|
|
).
|
|
|
|
filter(_, [], [], []).
|
|
filter(P, [HK - HV | T], True, False) :-
|
|
( if P(HK) then
|
|
assoc_list.filter(P, T, TrueTail, False),
|
|
True = [HK - HV | TrueTail]
|
|
else
|
|
assoc_list.filter(P, T, True, FalseTail),
|
|
False = [HK - HV | FalseTail]
|
|
).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
merge(As, Bs) = ABs :-
|
|
assoc_list.merge(As, Bs, ABs).
|
|
|
|
merge([], Bs, Bs).
|
|
merge([A | As], [], [A | As]).
|
|
merge([A | As], [B | Bs], Cs) :-
|
|
( if
|
|
A = AK - _AV,
|
|
B = BK - _BV,
|
|
compare(>, AK, BK)
|
|
then
|
|
assoc_list.merge([A | As], Bs, Cs0),
|
|
Cs = [B | Cs0]
|
|
else
|
|
% If compare((=), AK, BK), take A first.
|
|
assoc_list.merge(As, [B | Bs], Cs0),
|
|
Cs = [A | Cs0]
|
|
).
|
|
|
|
common_subset(ListA, ListB) = CommonList :-
|
|
assoc_list.common_subset_loop(ListA, ListB, [], RevCommonList),
|
|
list.reverse(RevCommonList, CommonList).
|
|
|
|
:- pred common_subset_loop(assoc_list(K, V)::in, assoc_list(K, V)::in,
|
|
assoc_list(K, V)::in, assoc_list(K, V)::out) is det.
|
|
|
|
common_subset_loop(ListA, ListB, !RevCommonList) :-
|
|
(
|
|
ListA = [],
|
|
ListB = []
|
|
;
|
|
ListA = [_ | _],
|
|
ListB = []
|
|
;
|
|
ListA = [],
|
|
ListB = [_ | _]
|
|
;
|
|
ListA = [KeyA - ValueA | TailA],
|
|
ListB = [KeyB - ValueB | TailB],
|
|
compare(R, KeyA, KeyB),
|
|
(
|
|
R = (=),
|
|
( if ValueA = ValueB then
|
|
!:RevCommonList = [KeyA - ValueA | !.RevCommonList]
|
|
else
|
|
true
|
|
),
|
|
assoc_list.common_subset_loop(TailA, TailB, !RevCommonList)
|
|
;
|
|
R = (<),
|
|
% KeyA has no match in ListB.
|
|
assoc_list.common_subset_loop(TailA, ListB, !RevCommonList)
|
|
;
|
|
R = (>),
|
|
% KeyB has no match in ListA.
|
|
assoc_list.common_subset_loop(ListA, TailB, !RevCommonList)
|
|
)
|
|
).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
|
|
foldl(_P, [], !A).
|
|
foldl(P, [K - V | KVs], !A) :-
|
|
P(K, V, !A),
|
|
foldl(P, KVs, !A).
|
|
|
|
foldl_keys(_F, [], A) = A.
|
|
foldl_keys(F, [KV | KVs], !.A) = !:A :-
|
|
KV = K - _V,
|
|
!:A = F(K, !.A),
|
|
!:A = assoc_list.foldl_keys(F, KVs, !.A).
|
|
|
|
foldl_keys(_P, [], !A).
|
|
foldl_keys(P, [KV | KVs], !A) :-
|
|
KV = K - _V,
|
|
P(K, !A),
|
|
assoc_list.foldl_keys(P, KVs, !A).
|
|
|
|
foldl_values(_F, [], A) = A.
|
|
foldl_values(F, [KV | KVs], !.A) = !:A :-
|
|
KV = _K - V,
|
|
!:A = F(V, !.A),
|
|
!:A = assoc_list.foldl_values(F, KVs, !.A).
|
|
|
|
foldl_values(_P, [], !A).
|
|
foldl_values(P, [KV | KVs], !A) :-
|
|
KV = _K - V,
|
|
P(V, !A),
|
|
assoc_list.foldl_values(P, KVs, !A).
|
|
|
|
foldl2(_P, [], !A, !B).
|
|
foldl2(P, [K - V | KVs], !A, !B) :-
|
|
P(K, V, !A, !B),
|
|
foldl2(P, KVs, !A, !B).
|
|
|
|
foldl2_values(_P, [], !A, !B).
|
|
foldl2_values(P, [KV | KVs], !A, !B) :-
|
|
KV = _K - V,
|
|
P(V, !A, !B),
|
|
assoc_list.foldl2_values(P, KVs, !A, !B).
|
|
|
|
foldl3(_P, [], !A, !B, !C).
|
|
foldl3(P, [K - V | KVs], !A, !B, !C) :-
|
|
P(K, V, !A, !B, !C),
|
|
foldl3(P, KVs, !A, !B, !C).
|
|
|
|
foldl3_values(_P, [], !A, !B, !C).
|
|
foldl3_values(P, [KV | KVs], !A, !B, !C) :-
|
|
KV = _K - V,
|
|
P(V, !A, !B, !C),
|
|
assoc_list.foldl3_values(P, KVs, !A, !B, !C).
|
|
|
|
%---------------------------------------------------------------------------%
|
|
:- end_module assoc_list.
|
|
%---------------------------------------------------------------------------%
|