Next: , Previous: array2d, Up: Top   [Contents]


3 assoc_list

%--------------------------------------------------%
% 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-2020 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)).

%--------------------------------------------------%
%
% 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.

%--------------------------------------------------%
%
% 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.

    % 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 assoc_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, 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), 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.

%--------------------------------------------------%
%
% Filtering elements in assoc_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),
    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) 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),
    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) 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),
    assoc_list(K, V)::in, assoc_list(K, V)::out, assoc_list(K, V)::out) is det.

%--------------------------------------------------%
%
% Merging assoc_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(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.

%--------------------------------------------------%
%
% Folding over assoc_lists.
%

    % 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), assoc_list(K, V), A, A).
:- mode foldl(pred(in, in, in, out) is det, in, in, out) is det.
:- mode foldl(pred(in, in, mdi, muo) is det, in, mdi, muo) is det.
:- mode foldl(pred(in, in, di, uo) is det, in, di, uo) is det.
:- mode foldl(pred(in, in, in, out) is semidet, in, in, out) is semidet.
:- mode foldl(pred(in, in, mdi, muo) is semidet, in, mdi, muo) is semidet.
:- mode foldl(pred(in, in, di, uo) is semidet, in, di, uo) is semidet.
:- mode foldl(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, assoc_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), 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(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, assoc_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), 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 foldl, but with two accumulators.
    %
:- pred foldl2(pred(K, V, A, A, B, B), assoc_list(K, V), A, A, B, B).
:- mode foldl2(pred(in, in, in, out, in, out) is det, in, in, out,
    in, out) is det.
:- mode foldl2(pred(in, in, in, out, mdi, muo) is det, in, in, out,
    mdi, muo) is det.
:- mode foldl2(pred(in, in, in, out, di, uo) is det, in, in, out,
    di, uo) is det.
:- mode foldl2(pred(in, in, in, out, in, out) is semidet, in, in, out,
    in, out) is semidet.
:- mode foldl2(pred(in, in, in, out, mdi, muo) is semidet, in,in, out,
    mdi, muo) is semidet.
:- mode foldl2(pred(in, in, in, out, di, uo) is semidet, in, in, out,
    di, uo) is semidet.
:- mode foldl2(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), 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 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(pred(in, in, in, out, in, out, in, out) is det, in,
    in, out, in, out, in, out) is det.
:- mode foldl3(pred(in, in, in, out, in, out, mdi, muo) is det, in,
    in, out, in, out, mdi, muo) is det.
:- mode foldl3(pred(in, in, in, out, in, out, di, uo) is det, in,
    in, out, in, out, di, uo) is det.
:- mode foldl3(pred(in, in, in, out, in, out, in, out) is semidet, in,
    in, out, in, out, in, out) is semidet.
:- mode foldl3(pred(in, in, in, out, in, out, mdi, muo) is semidet, in,
        in, out, in, out, mdi, muo) is semidet.
:- mode foldl3(pred(in, in, in, out, in, out, di, uo) is semidet, in,
    in, out, in, out, di, uo) is semidet.
:- mode foldl3(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), 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.

%--------------------------------------------------%
%--------------------------------------------------%


Next: , Previous: array2d, Up: Top   [Contents]