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


40 map

%--------------------------------------------------%
% vim: ft=mercury ts=4 sw=4 et
%--------------------------------------------------%
% Copyright (C) 1993-2012 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%
%
% File: map.m.
% Main author: fjh, conway.
% Stability: high.
%
% This file provides the 'map' ADT.
% A map (also known as a dictionary or an associative array) is a collection
% of (Key, Data) pairs which allows you to look up any Data item given the
% Key.
%
% The implementation is using balanced binary trees, as provided by tree234.m.
% Virtually all the predicates in this file just forward the work
% to the corresponding predicate in tree234.m.
%
% Note: 2-3-4 trees do not have a canonical representation for any given map.
% Therefore, two maps with the same set of key-value pairs may have
% different internal representations. This means that two maps with the
% same set of key-value pairs that may fail to unify and may compare as
% unequal, for example if items were inserted into one of the maps in a
% different order. See equal/2 below which can be used to test if two
% maps have the same set of key-value pairs.
%
%--------------------------------------------------%
%--------------------------------------------------%

:- module map.
:- interface.

:- import_module assoc_list.
:- import_module list.
:- import_module maybe.
:- import_module set.

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

:- type map(_K, _V).

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

    % Initialize an empty map.
    %
:- func init = (map(K, V)::uo) is det.
:- pred init(map(_, _)::uo) is det.

    % Initialize a map containing the given key-value pair.
    %
:- func singleton(K, V) = map(K, V).

    % Check whether a map is empty.
    %
:- pred is_empty(map(_, _)::in) is semidet.

    % True if both maps have the same set of key-value pairs, regardless of
    % how the maps were constructed.
    %
    % Unifying maps does not work as one might expect because the internal
    % structures of two maps that contain the same set of key-value pairs
    % may be different.
    %
:- pred equal(map(K, V)::in, map(K, V)::in) is semidet.

    % Succeed iff the map contains the given key.
    %
:- pred contains(map(K, _V)::in, K::in) is semidet.

:- pred member(map(K, V)::in, K::out, V::out) is nondet.

    % Search map for key.
    %
:- func search(map(K, V), K) = V is semidet.
:- pred search(map(K, V)::in, K::in, V::out) is semidet.

    % Search map for key, but abort if search fails.
    %
:- func lookup(map(K, V), K) = V.
:- pred lookup(map(K, V)::in, K::in, V::out) is det.

    % Search map for data.
    %
:- pred inverse_search(map(K, V)::in, V::in, K::out) is nondet.

    % Search for a key-value pair using the key. If there is no entry
    % for the given key, returns the pair for the next lower key instead.
    % Fails if there is no key with the given or lower value.
    %
:- pred lower_bound_search(map(K, V)::in, K::in, K::out, V::out)
    is semidet.

    % Search for a key-value pair using the key. If there is no entry
    % for the given key, returns the pair for the next lower key instead.
    % Aborts if there is no key with the given or lower value.
    %
:- pred lower_bound_lookup(map(K, V)::in, K::in, K::out, V::out) is det.

    % Search for a key-value pair using the key. If there is no entry
    % for the given key, returns the pair for the next higher key instead.
    % Fails if there is no key with the given or higher value.
    %
:- pred upper_bound_search(map(K, V)::in, K::in, K::out, V::out)
    is semidet.

    % Search for a key-value pair using the key. If there is no entry
    % for the given key, returns the pair for the next higher key instead.
    % Aborts if there is no key with the given or higher value.
    %
:- pred upper_bound_lookup(map(K, V)::in, K::in, K::out, V::out) is det.

    % Return the largest key in the map, if there is one.
    %
:- func max_key(map(K, V)) = K is semidet.

    % As above, but abort if there is no largest key.
    %
:- func det_max_key(map(K, V)) = K.

    % Return the smallest key in the map, if there is one.
    %
:- func min_key(map(K,V)) = K is semidet.

    % As above, but abort if there is no smallest key.
    %
:- func det_min_key(map(K, V)) = K.

    % Insert a new key and corresponding value into a map.
    % Fail if the key already exists.
    %
:- func insert(map(K, V), K, V) = map(K, V) is semidet.
:- pred insert(K::in, V::in, map(K, V)::in, map(K, V)::out) is semidet.

    % Insert a new key and corresponding value into a map.
    % Abort if the key already exists.
    %
:- func det_insert(map(K, V), K, V) = map(K, V).
:- pred det_insert(K::in, V::in, map(K, V)::in, map(K, V)::out) is det.

    % Apply det_insert to key - value pairs from corresponding lists.
    %
:- func det_insert_from_corresponding_lists(map(K, V), list(K), list(V))
    = map(K, V).
:- pred det_insert_from_corresponding_lists(list(K)::in,
    list(V)::in, map(K, V)::in, map(K, V)::out) is det.

    % Apply det_insert to key - value pairs from the assoc_lists.
    %
:- func det_insert_from_assoc_list(map(K, V), assoc_list(K, V))
    = map(K, V).
:- pred det_insert_from_assoc_list(assoc_list(K, V)::in,
    map(K, V)::in, map(K, V)::out) is det.

    % Apply set to key - value pairs from corresponding lists.
    %
:- func set_from_corresponding_lists(map(K, V), list(K), list(V))
    = map(K, V).
:- pred set_from_corresponding_lists(list(K)::in, list(V)::in,
    map(K, V)::in, map(K, V)::out) is det.

:- func set_from_assoc_list(map(K, V), assoc_list(K, V)) = map(K, V).
:- pred set_from_assoc_list(assoc_list(K, V)::in,
    map(K, V)::in, map(K, V)::out) is det.

    % Update the value corresponding to a given key
    % Fail if the key doesn't already exist.
    %
:- func update(map(K, V), K, V) = map(K, V) is semidet.
:- pred update(K::in, V::in, map(K, V)::in, map(K, V)::out) is semidet.

    % Update the value corresponding to a given key
    % Abort if the key doesn't already exist.
    %
:- func det_update(map(K, V), K, V) = map(K, V).
:- pred det_update(K::in, V::in, map(K, V)::in, map(K, V)::out) is det.

    % search_insert(K, V, MaybeOldV, !Map):
    %
    % Search for the key K in the map. If the key is already in the map,
    % with corresponding value OldV, set MaybeOldV to yes(OldV). If it
    % is not in the map, then insert it into the map with value V.
    %
:- pred search_insert(K::in, V::in, maybe(V)::out,
    map(K, V)::in, map(K, V)::out) is det.

    % Update the value at the given key by applying the supplied
    % transformation to it. Fails if the key is not found. This is faster
    % than first searching for the value and then updating it.
    %
:- pred transform_value(pred(V, V)::in(pred(in, out) is det), K::in,
    map(K, V)::in, map(K, V)::out) is semidet.

    % Same as transform_value/4, but aborts instead of failing if the
    % key is not found.
    %
:- func det_transform_value(func(V) = V, K, map(K, V)) = map(K, V).
:- pred det_transform_value(pred(V, V)::in(pred(in, out) is det), K::in,
    map(K, V)::in, map(K, V)::out) is det.

    % Update value if the key is already present, otherwise
    % insert new key and value.
    %
:- func set(map(K, V), K, V) = map(K, V).
:- pred set(K::in, V::in, map(K, V)::in, map(K, V)::out) is det.

    % Given a map, return a list of all the keys in the map.
    %
:- func keys(map(K, _V)) = list(K).
:- pred keys(map(K, _V)::in, list(K)::out) is det.

    % Given a map, return a list of all the keys in the map,
    % in sorted order.
    %
:- func sorted_keys(map(K, _V)) = list(K).
:- pred sorted_keys(map(K, _V)::in, list(K)::out) is det.

    % Given a map, return a list of all the data values in the map.
    %
:- func values(map(_K, V)) = list(V).
:- pred values(map(_K, V)::in, list(V)::out) is det.

:- pred keys_and_values(map(K, V)::in, list(K)::out, list(V)::out) is det.

    % Convert a map to an association list.
    %
:- func to_assoc_list(map(K, V)) = assoc_list(K, V).
:- pred to_assoc_list(map(K, V)::in, assoc_list(K, V)::out) is det.

    % Convert a map to an association list which is sorted on the keys.
    %
:- func to_sorted_assoc_list(map(K, V)) = assoc_list(K, V).
:- pred to_sorted_assoc_list(map(K, V)::in, assoc_list(K, V)::out) is det.

    % Convert an association list to a map.
    %
:- func from_assoc_list(assoc_list(K, V)) = map(K, V).
:- pred from_assoc_list(assoc_list(K, V)::in, map(K, V)::out) is det.

    % Convert a sorted association list with no duplicated keys to a map.
    %
:- func from_sorted_assoc_list(assoc_list(K, V)) = map(K, V).
:- pred from_sorted_assoc_list(assoc_list(K, V)::in, map(K, V)::out)
    is det.

    % Convert a reverse sorted association list with no duplicated keys
    % to a map.
    %
:- func from_rev_sorted_assoc_list(assoc_list(K, V)) = map(K, V).
:- pred from_rev_sorted_assoc_list(assoc_list(K, V)::in, map(K, V)::out)
    is det.

    % Delete a key-value pair from a map.
    % If the key is not present, leave the map unchanged.
    %
:- func delete(map(K, V), K) = map(K, V).
:- pred delete(K::in, map(K, V)::in, map(K, V)::out) is det.

    % Apply delete/3 to a list of keys.
    %
:- func delete_list(map(K, V), list(K)) = map(K, V).
:- pred delete_list(list(K)::in, map(K, V)::in, map(K, V)::out) is det.

    % Apply delete/3 to a sorted list of keys. The fact that the list
    % is sorted may make this more efficient. (If the list is not sorted,
    % the result will be either an abort or incorrect output.)
    %
:- func delete_sorted_list(map(K, V), list(K)) = map(K, V).
:- pred delete_sorted_list(list(K)::in, map(K, V)::in, map(K, V)::out)
    is det.

    % Delete a key-value pair from a map and return the value.
    % Fail if the key is not present.
    %
:- pred remove(K::in, V::out, map(K, V)::in, map(K, V)::out) is semidet.

    % Delete a key-value pair from a map and return the value.
    % Abort if the key is not present.
    %
:- pred det_remove(K::in, V::out, map(K, V)::in, map(K, V)::out) is det.

    % Remove the smallest item from the map, fail if the map is empty.
    %
:- pred remove_smallest(K::out, V::out, map(K, V)::in, map(K, V)::out)
    is semidet.

    % Count the number of elements in the map.
    %
:- func count(map(K, V)) = int.
:- pred count(map(K, V)::in, int::out) is det.

    % Convert a pair of lists (which must be of the same length) to a map.
    %
:- func from_corresponding_lists(list(K), list(V)) = map(K, V).
:- pred from_corresponding_lists(list(K)::in, list(V)::in, map(K, V)::out)
    is det.

    % Merge the contents of the two maps.
    % Throws an exception if both sets of keys are not disjoint.
    %
    % The cost of this predicate is proportional to the number of elements
    % in the second map, so for efficiency, you want to put the bigger map
    % first and the smaller map second.
    %
:- func merge(map(K, V), map(K, V)) = map(K, V).
:- pred merge(map(K, V)::in, map(K, V)::in, map(K, V)::out) is det.

    % For overlay(MapA, MapB, Map), if MapA and MapB both contain the
    % same key, then Map will map that key to the value from MapB.
    % In other words, MapB takes precedence over MapA.
    %
:- func overlay(map(K, V), map(K, V)) = map(K, V).
:- pred overlay(map(K, V)::in, map(K, V)::in, map(K, V)::out) is det.

    % overlay_large_map(MapA, MapB, Map) performs the same task as
    % overlay(MapA, MapB, Map). However, while overlay takes time
    % proportional to the size of MapB, overlay_large_map takes time
    % proportional to the size of MapA. In other words, it preferable when
    % MapB is a large
    %
:- func overlay_large_map(map(K, V), map(K, V)) = map(K, V).
:- pred overlay_large_map(map(K, V)::in, map(K, V)::in, map(K, V)::out)
    is det.

    % select takes a map and a set of keys, and returns a map
    % containing the keys in the set and their corresponding values.
    %
:- func select(map(K, V), set(K)) = map(K, V).
:- pred select(map(K, V)::in, set(K)::in, map(K, V)::out) is det.

    % select_sorted_list takes a map and a sorted list of keys, and returns
    % a map containing the keys in the list and their corresponding values.
    %
:- func select_sorted_list(map(K, V), list(K)) = map(K, V).
:- pred select_sorted_list(map(K, V)::in, list(K)::in, map(K, V)::out)
    is det.

    % Given a list of keys, produce a list of their corresponding
    % values in a specified map.
    %
:- func apply_to_list(list(K), map(K, V)) = list(V).
:- pred apply_to_list(list(K)::in, map(K, V)::in, list(V)::out) is det.

    % Declaratively, a NOP.
    % Operationally, a suggestion that the implementation
    % optimize the representation of the map in the expectation
    % of a number of lookups but few or no modifications.
    %
:- func optimize(map(K, V)) = map(K, V).
:- pred optimize(map(K, V)::in, map(K, V)::out) is det.

    % Perform an inorder traversal of the map, applying
    % an accumulator predicate for each key-value pair.
    %
:- func foldl(func(K, V, A) = A, map(K, V), A) = A.
:- pred foldl(pred(K, V, A, A), map(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 cc_multi, in, in, out) is cc_multi.
:- mode foldl(pred(in, in, di, uo) is cc_multi, in, di, uo) is cc_multi.
:- mode foldl(pred(in, in, mdi, muo) is cc_multi, in, mdi, muo)
    is cc_multi.

    % Perform an inorder traversal of the map, applying an accumulator
    % predicate with two accumulators for each key-value pair.
    % (Although no more expressive than foldl, this is often
    % a more convenient format, and a little more efficient).
    %
:- pred foldl2(pred(K, V, A, A, B, B), map(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, di, uo, di, uo) is det,
    in, di, uo, 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 cc_multi,
    in, in, out, in, out) is cc_multi.
:- mode foldl2(pred(in, in, in, out, mdi, muo) is cc_multi,
    in, in, out, mdi, muo) is cc_multi.
:- mode foldl2(pred(in, in, in, out, di, uo) is cc_multi,
    in, in, out, di, uo) is cc_multi.
:- mode foldl2(pred(in, in, di, uo, di, uo) is cc_multi,
    in, di, uo, di, uo) is cc_multi.

    % Perform an inorder traversal of the map, applying an accumulator
    % predicate with three accumulators for each key-value pair.
    % (Although no more expressive than foldl, this is often
    % a more convenient format, and a little more efficient).
    %
:- pred foldl3(pred(K, V, A, A, B, B, C, C), map(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, di, uo, di, uo) is det,
    in, in, out, di, uo, di, uo) is det.
:- mode foldl3(pred(in, in, di, uo, di, uo, di, uo) is det,
    in, di, uo, di, uo, 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.

    % Perform an inorder traversal of the map, applying an accumulator
    % predicate with four accumulators for each key-value pair.
    % (Although no more expressive than foldl, this is often
    % a more convenient format, and a little more efficient).
    %
:- pred foldl4(pred(K, V, A, A, B, B, C, C, D, D), map(K, V),
    A, A, B, B, C, C, D, D).
:- mode foldl4(pred(in, in, in, out, in, out, in, out, in, out) is det,
    in, in, out, in, out, in, out, in, out) is det.
:- mode foldl4(pred(in, in, in, out, in, out, in, out, mdi, muo) is det,
    in, in, out, in, out, in, out, mdi, muo) is det.
:- mode foldl4(pred(in, in, in, out, in, out, in, out, di, uo) is det,
    in, in, out, in, out, in, out, di, uo) is det.
:- mode foldl4(pred(in, in, in, out, in, out, di, uo, di, uo) is det,
    in, in, out, in, out, di, uo, di, uo) is det.
:- mode foldl4(pred(in, in, in, out, di, uo, di, uo, di, uo) is det,
    in, in, out, di, uo, di, uo, di, uo) is det.
:- mode foldl4(pred(in, in, di, uo, di, uo, di, uo, di, uo) is det,
    in, di, uo, di, uo, di, uo, di, uo) is det.
:- mode foldl4(pred(in, in, in, out, in, out, in, out, in, out) is semidet,
    in, in, out, in, out, in, out, in, out) is semidet.
:- mode foldl4(pred(in, in, in, out, in, out, in, out, mdi, muo) is semidet,
    in, in, out, in, out, in, out, mdi, muo) is semidet.
:- mode foldl4(pred(in, in, in, out, in, out, in, out, di, uo) is semidet,
    in, in, out, in, out, in, out, di, uo) is semidet.

    % Perform an inorder traversal of the map, applying an accumulator
    % predicate with five accumulators for each key-value pair.
    % (Although no more expressive than foldl, this is often
    % a more convenient format, and a little more efficient).
    %
:- pred foldl5(pred(K, V, A, A, B, B, C, C, D, D, E, E), map(K, V),
    A, A, B, B, C, C, D, D, E, E).
:- mode foldl5(pred(in, in, in, out, in, out, in, out, in, out, in, out)
    is det,
    in, in, out, in, out, in, out, in, out, in, out) is det.
:- mode foldl5(pred(in, in, in, out, in, out, in, out, in, out, mdi, muo)
    is det,
    in, in, out, in, out, in, out, in, out, mdi, muo) is det.
:- mode foldl5(pred(in, in, in, out, in, out, in, out, in, out, di, uo)
    is det,
    in, in, out, in, out, in, out, in, out, di, uo) is det.
:- mode foldl5(pred(in, in, in, out, in, out, in, out, in, out, in, out)
    is semidet,
    in, in, out, in, out, in, out, in, out, in, out) is semidet.
:- mode foldl5(pred(in, in,in, out,  in, out, in, out, in, out, mdi, muo)
    is semidet,
    in, in, out, in, out, in, out, in, out, mdi, muo) is semidet.
:- mode foldl5(pred(in, in, in, out, in, out, in, out, in, out, di, uo)
    is semidet,
    in, in, out, in, out, in, out, in, out, di, uo) is semidet.

    % Perform an inorder traversal by key of the map, applying an accumulator
    % predicate for value.
    %
:- pred foldl_values(pred(V, A, A), map(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 cc_multi, in, in, out)
    is cc_multi.
:- mode foldl_values(pred(in, di, uo) is cc_multi, in, di, uo) is cc_multi.
:- mode foldl_values(pred(in, mdi, muo) is cc_multi, in, mdi, muo)
    is cc_multi.

    % As above, but with two accumulators.
    %
:- pred foldl2_values(pred(V, A, A, B, B), map(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 cc_multi, in,
    in, out, in, out) is cc_multi.
:- mode foldl2_values(pred(in, in, out, mdi, muo) is cc_multi, in,
    in, out, mdi, muo) is cc_multi.
:- mode foldl2_values(pred(in, in, out, di, uo) is cc_multi, in,
    in, out, di, uo) is cc_multi.

    % As above, but with three accumulators.
    %
:- pred foldl3_values(pred(V, A, A, B, B, C, C), map(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 cc_multi, in,
    in, out, in, out, in, out) is cc_multi.
:- mode foldl3_values(pred(in, in, out, in, out, mdi, muo) is cc_multi, in,
    in, out, in, out, mdi, muo) is cc_multi.
:- mode foldl3_values(pred(in, in, out, in, out, di, uo) is cc_multi, in,
    in, out, in, out, di, uo) is cc_multi.

:- func foldr(func(K, V, A) = A, map(K, V), A) = A.
:- pred foldr(pred(K, V, A, A), map(K, V), A, A).
:- mode foldr(pred(in, in, in, out) is det, in, in, out) is det.
:- mode foldr(pred(in, in, mdi, muo) is det, in, mdi, muo) is det.
:- mode foldr(pred(in, in, di, uo) is det, in, di, uo) is det.
:- mode foldr(pred(in, in, in, out) is semidet, in, in, out) is semidet.
:- mode foldr(pred(in, in, mdi, muo) is semidet, in, mdi, muo) is semidet.
:- mode foldr(pred(in, in, di, uo) is semidet, in, di, uo) is semidet.
:- mode foldr(pred(in, in, in, out) is cc_multi, in, in, out) is cc_multi.
:- mode foldr(pred(in, in, mdi, muo) is cc_multi, in, mdi, muo)
    is cc_multi.
:- mode foldr(pred(in, in, di, uo) is cc_multi, in, di, uo) is cc_multi.

:- pred foldr2(pred(K, V, A, A, B, B), map(K, V), A, A, B, B).
:- mode foldr2(pred(in, in, in, out, in, out) is det,
    in, in, out, in, out) is det.
:- mode foldr2(pred(in, in, in, out, mdi, muo) is det,
    in, in, out, mdi, muo) is det.
:- mode foldr2(pred(in, in, in, out, di, uo) is det,
    in, in, out, di, uo) is det.
:- mode foldr2(pred(in, in, di, uo, di, uo) is det,
    in, di, uo, di, uo) is det.
:- mode foldr2(pred(in, in, in, out, in, out) is semidet,
    in, in, out, in, out) is semidet.
:- mode foldr2(pred(in, in, in, out, mdi, muo) is semidet,
    in, in, out, mdi, muo) is semidet.
:- mode foldr2(pred(in, in, in, out, di, uo) is semidet,
    in, in, out, di, uo) is semidet.

:- pred foldr3(pred(K, V, A, A, B, B, C, C), map(K, V), A, A, B, B, C, C).
:- mode foldr3(pred(in, in, in, out, in, out, in, out) is det,
    in, in, out, in, out, in, out) is det.
:- mode foldr3(pred(in, in, in, out, in, out, mdi, muo) is det,
    in, in, out, in, out, mdi, muo) is det.
:- mode foldr3(pred(in, in, in, out, in, out, di, uo) is det,
    in, in, out, in, out, di, uo) is det.
:- mode foldr3(pred(in, in, in, out, di, uo, di, uo) is det,
    in, in, out, di, uo, di, uo) is det.
:- mode foldr3(pred(in, in, di, uo, di, uo, di, uo) is det,
    in, di, uo, di, uo, di, uo) is det.
:- mode foldr3(pred(in, in, in, out, in, out, in, out) is semidet,
    in, in, out, in, out, in, out) is semidet.
:- mode foldr3(pred(in, in, in, out, in, out, mdi, muo) is semidet,
    in, in, out, in, out, mdi, muo) is semidet.
:- mode foldr3(pred(in, in, in, out, in, out, di, uo) is semidet,
    in, in, out, in, out, di, uo) is semidet.

:- pred foldr4(pred(K, V, A, A, B, B, C, C, D, D), map(K, V),
    A, A, B, B, C, C, D, D).
:- mode foldr4(pred(in, in, in, out, in, out, in, out, in, out) is det,
    in, in, out, in, out, in, out, in, out) is det.
:- mode foldr4(pred(in, in, in, out, in, out, in, out, mdi, muo) is det,
    in, in, out, in, out, in, out, mdi, muo) is det.
:- mode foldr4(pred(in, in, in, out, in, out, in, out, di, uo) is det,
    in, in, out, in, out, in, out, di, uo) is det.
:- mode foldr4(pred(in, in, in, out, in, out, di, uo, di, uo) is det,
    in, in, out, in, out, di, uo, di, uo) is det.
:- mode foldr4(pred(in, in, in, out, di, uo, di, uo, di, uo) is det,
    in, in, out, di, uo, di, uo, di, uo) is det.
:- mode foldr4(pred(in, in, di, uo, di, uo, di, uo, di, uo) is det,
    in, di, uo, di, uo, di, uo, di, uo) is det.
:- mode foldr4(pred(in, in, in, out, in, out, in, out, in, out) is semidet,
    in, in, out, in, out, in, out, in, out) is semidet.
:- mode foldr4(pred(in, in, in, out, in, out, in, out, mdi, muo) is semidet,
    in, in, out, in, out, in, out, mdi, muo) is semidet.
:- mode foldr4(pred(in, in, in, out, in, out, in, out, di, uo) is semidet,
    in, in, out, in, out, in, out, di, uo) is semidet.

:- pred foldr5(pred(K, V, A, A, B, B, C, C, D, D, E, E), map(K, V),
    A, A, B, B, C, C, D, D, E, E).
:- mode foldr5(pred(in, in, in, out, in, out, in, out, in, out, in, out)
    is det,
    in, in, out, in, out, in, out, in, out, in, out) is det.
:- mode foldr5(pred(in, in, in, out, in, out, in, out, in, out, mdi, muo)
    is det,
    in, in, out, in, out, in, out, in, out, mdi, muo) is det.
:- mode foldr5(pred(in, in, in, out, in, out, in, out, in, out, di, uo)
    is det,
    in, in, out, in, out, in, out, in, out, di, uo) is det.
:- mode foldr5(pred(in, in, in, out, in, out, in, out, in, out, in, out)
    is semidet,
    in, in, out, in, out, in, out, in, out, in, out) is semidet.
:- mode foldr5(pred(in, in, in, out, in, out, in, out, in, out, mdi, muo)
    is semidet,
    in, in, out, in, out, in, out, in, out, mdi, muo) is semidet.
:- mode foldr5(pred(in, in, in, out, in, out, in, out, in, out, di, uo)
    is semidet,
    in, in, out, in, out, in, out, in, out, di, uo) is semidet.

    % Apply a transformation predicate to all the values in a map.
    %
:- func map_values(func(K, V) = W, map(K, V)) = map(K, W).
:- pred map_values(pred(K, V, W), map(K, V), map(K, W)).
:- mode map_values(pred(in, in, out) is det, in, out) is det.
:- mode map_values(pred(in, in, out) is semidet, in, out) is semidet.

    % Same as map_values, but do not pass the key to the given predicate.
    %
:- func map_values_only(func(V) = W, map(K, V)) = map(K, W).
:- pred map_values_only(pred(V, W), map(K, V), map(K, W)).
:- mode map_values_only(pred(in, out) is det, in, out) is det.
:- mode map_values_only(pred(in, out) is semidet, in, out) is semidet.

    % Perform an inorder traversal by key of the map, applying a transformation
    % predicate to each value while updating an accumulator.
    %
:- pred map_foldl(pred(K, V, W, A, A), map(K, V), map(K, W), A, A).
:- mode map_foldl(pred(in, in, out, in, out) is det, in, out, in, out)
    is det.
:- mode map_foldl(pred(in, in, out, mdi, muo) is det, in, out, mdi, muo)
    is det.
:- mode map_foldl(pred(in, in, out, di, uo) is det, in, out, di, uo)
    is det.
:- mode map_foldl(pred(in, in, out, in, out) is semidet, in, out,
    in, out) is semidet.
:- mode map_foldl(pred(in, in, out, mdi, muo) is semidet, in, out,
    mdi, muo) is semidet.
:- mode map_foldl(pred(in, in, out, di, uo) is semidet, in, out,
    di, uo) is semidet.

    % As map_foldl, but with two accumulators.
    %
:- pred map_foldl2(pred(K, V, W, A, A, B, B), map(K, V), map(K, W),
    A, A, B, B).
:- mode map_foldl2(pred(in, in, out, in, out, in, out) is det,
    in, out, in, out, in, out) is det.
:- mode map_foldl2(pred(in, in, out, in, out, mdi, muo) is det,
    in, out, in, out, mdi, muo) is det.
:- mode map_foldl2(pred(in, in, out, in, out, di, uo) is det,
    in, out, in, out, di, uo) is det.
:- mode map_foldl2(pred(in, in, out, di, uo, di, uo) is det,
    in, out, di, uo, di, uo) is det.
:- mode map_foldl2(pred(in, in, out, in, out, in, out) is semidet,
    in, out, in, out, in, out) is semidet.
:- mode map_foldl2(pred(in, in, out, in, out, mdi, muo) is semidet,
    in, out, in, out, mdi, muo) is semidet.
:- mode map_foldl2(pred(in, in, out, in, out, di, uo) is semidet,
    in, out, in, out, di, uo) is semidet.

    % As map_foldl, but with three accumulators.
    %
:- pred map_foldl3(pred(K, V, W, A, A, B, B, C, C), map(K, V), map(K, W),
    A, A, B, B, C, C).
:- mode map_foldl3(pred(in, in, out, in, out, in, out, in, out) is det,
    in, out, in, out, in, out, in, out) is det.
:- mode map_foldl3(pred(in, in, out, in, out, in, out, mdi, muo) is det,
    in, out, in, out, in, out, mdi, muo) is det.
:- mode map_foldl3(pred(in, in, out, di, uo, di, uo, di, uo) is det,
    in, out, di, uo, di, uo, di, uo) is det.
:- mode map_foldl3(pred(in, in, out, in, out, in, out, di, uo) is det,
    in, out, in, out, in, out, di, uo) is det.
:- mode map_foldl3(pred(in, in, out, in, out, di, uo, di, uo) is det,
    in, out, in, out, di, uo, di, uo) is det.
:- mode map_foldl3(pred(in, in, out, in, out, in, out, in, out) is semidet,
    in, out, in, out, in, out, in, out) is semidet.
:- mode map_foldl3(pred(in, in, out, in, out, in, out, mdi, muo) is semidet,
    in, out, in, out, in, out, mdi, muo) is semidet.
:- mode map_foldl3(pred(in, in, out, in, out, in, out, di, uo) is semidet,
    in, out, in, out, in, out, di, uo) is semidet.

    % As map_foldl, but without passing the key to the predicate.
    %
:- pred map_values_foldl(pred(V, W, A, A), map(K, V), map(K, W), A, A).
:- mode map_values_foldl(pred(in, out, di, uo) is det,
    in, out, di, uo) is det.
:- mode map_values_foldl(pred(in, out, in, out) is det,
    in, out, in, out) is det.
:- mode map_values_foldl(pred(in, out, in, out) is semidet,
    in, out, in, out) is semidet.

    % As map_values_foldl, but with two accumulators.
    %
:- pred map_values_foldl2(pred(V, W, A, A, B, B), map(K, V), map(K, W),
    A, A, B, B).
:- mode map_values_foldl2(pred(in, out, di, uo, di, uo) is det,
    in, out, di, uo, di, uo) is det.
:- mode map_values_foldl2(pred(in, out, in, out, di, uo) is det,
    in, out, in, out, di, uo) is det.
:- mode map_values_foldl2(pred(in, out, in, out, in, out) is det,
    in, out, in, out, in, out) is det.
:- mode map_values_foldl2(pred(in, out, in, out, in, out) is semidet,
    in, out, in, out, in, out) is semidet.

    % As map_values_foldl, but with three accumulators.
    %
:- pred map_values_foldl3(pred(V, W, A, A, B, B, C, C),
    map(K, V), map(K, W), A, A, B, B, C, C).
:- mode map_values_foldl3(pred(in, out, di, uo, di, uo, di, uo) is det,
    in, out, di, uo, di, uo, di, uo) is det.
:- mode map_values_foldl3(pred(in, out, in, out, di, uo, di, uo) is det,
    in, out, in, out, di, uo, di, uo) is det.
:- mode map_values_foldl3(pred(in, out, in, out, in, out, di, uo) is det,
    in, out, in, out, in, out, di, uo) is det.
:- mode map_values_foldl3(pred(in, out, in, out, in, out, in, out) is det,
    in, out, in, out, in, out, in, out) is det.
:- mode map_values_foldl3(
    pred(in, out, in, out, in, out, in, out) is semidet,
    in, out, in, out, in, out, in, out) is semidet.

    % Given two maps M1 and M2, create a third map M3 that has only the
    % keys that occur in both M1 and M2. For keys that occur in both M1
    % and M2, compute the value in the final map by applying the supplied
    % predicate to the values associated with the key in M1 and M2.
    % Fail if and only if this predicate fails on the values associated
    % with some common key.
    %
:- func intersect(func(V, V) = V, map(K, V), map(K, V)) = map(K, V).

:- pred intersect(pred(V, V, V), map(K, V), map(K, V), map(K, V)).
:- mode intersect(pred(in, in, out) is semidet, in, in, out) is semidet.
:- mode intersect(pred(in, in, out) is det, in, in, out) is det.

    % Calls intersect. Aborts if intersect fails.
    %
:- func det_intersect(func(V, V) = V, map(K, V), map(K, V)) = map(K, V).
:- mode det_intersect(func(in, in) = out is semidet, in, in) = out is det.

:- pred det_intersect(pred(V, V, V), map(K, V), map(K, V), map(K, V)).
:- mode det_intersect(pred(in, in, out) is semidet, in, in, out) is det.

    % Given two maps M1 and M2, create a third map M3 that has only the
    % keys that occur in both M1 and M2. For keys that occur in both M1
    % and M2, compute the corresponding values. If they are the same,
    % include the key/value pair in M3. If they differ, do not include the
    % key in M3.
    %
    % This predicate effectively considers the input maps to be sets of
    % key/value pairs, computes the intersection of those two sets, and
    % returns the map corresponding to the intersection.
    %
    % common_subset is very similar to intersect, but can succeed
    % even with an output map that does not contain an entry for a key
    % value that occurs in both input maps.
    %
:- func common_subset(map(K, V), map(K, V)) = map(K, V).

    % Given two maps M1 and M2, create a third map M3 that contains all
    % the keys that occur in either M1 and M2. For keys that occur in both M1
    % and M2, compute the value in the final map by applying the supplied
    % closure to the values associated with the key in M1 and M2.
    % Fail if and only if this closure fails on the values associated
    % with some common key.
    %
:- func union(func(V, V) = V, map(K, V), map(K, V)) = map(K, V).
:- pred union(pred(V, V, V), map(K, V), map(K, V), map(K, V)).
:- mode union(pred(in, in, out) is semidet, in, in, out) is semidet.
:- mode union(pred(in, in, out) is det, in, in, out) is det.

    % Calls union. Aborts if union fails.
    %
:- func det_union(func(V, V) = V, map(K, V), map(K, V)) = map(K, V).
:- mode det_union(func(in, in) = out is semidet, in, in) = out is det.

:- pred det_union(pred(V, V, V), map(K, V), map(K, V), map(K, V)).
:- mode det_union(pred(in, in, out) is semidet, in, in, out) is det.

    % Consider the original map a set of key-value pairs. This predicate
    % returns a map that maps each value to the set of keys it is paired
    % with in the original map.
    %
:- func reverse_map(map(K, V)) = map(V, set(K)).

    % Field selection for maps.

    % Map ^ elem(Key) = search(Map, Key).
    %
:- func elem(K, map(K, V)) = V is semidet.

    % Map ^ det_elem(Key) = lookup(Map, Key).
    %
:- func det_elem(K, map(K, V)) = V.

    % Field update for maps.

    % (Map ^ elem(Key) := Value) = set(Map, Key, Value).
    %
:- func 'elem :='(K, map(K, V), V) = map(K, V).

    % (Map ^ det_elem(Key) := Value) = det_update(Map, Key, Value).
    %
:- func 'det_elem :='(K, map(K, V), V) = map(K, V).

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


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