1/* Part of SWI-Prolog 2 3 Author: Jan Wielemaker 4 E-mail: J.Wielemaker@vu.nl 5 WWW: http://www.swi-prolog.org 6 Copyright (c) 2006-2024, University of Amsterdam 7 VU University Amsterdam 8 SWI-Prolog Solutions b.v. 9 All rights reserved. 10 11 Redistribution and use in source and binary forms, with or without 12 modification, are permitted provided that the following conditions 13 are met: 14 15 1. Redistributions of source code must retain the above copyright 16 notice, this list of conditions and the following disclaimer. 17 18 2. Redistributions in binary form must reproduce the above copyright 19 notice, this list of conditions and the following disclaimer in 20 the documentation and/or other materials provided with the 21 distribution. 22 23 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 24 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 25 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 26 FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 27 COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 28 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 29 BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 30 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 31 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 32 LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 33 ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 34 POSSIBILITY OF SUCH DAMAGE. 35*/ 36 37:- module(pairs, 38 [ pairs_keys_values/3, 39 pairs_values/2, 40 pairs_keys/2, 41 group_pairs_by_key/2, 42 transpose_pairs/2, 43 map_list_to_pairs/3 44 ]). 45 46:- meta_predicate 47 map_list_to_pairs(, , ). 48 49/** <module> Operations on key-value lists 50 51This module implements common operations on Key-Value lists, also known 52as _Pairs_. Pairs have great practical value, especially due to 53keysort/2 and the library(assoc). 54 55This library is based on discussion in the SWI-Prolog mailinglist, 56including specifications from Quintus and a library proposal by Richard 57O'Keefe. 58 59@see keysort/2, library(assoc) 60*/ 61 62%! pairs_keys_values(?Pairs, ?Keys, ?Values) is det. 63% 64% True if Keys holds the keys of Pairs and Values the values. 65% 66% Deterministic if any argument is instantiated to a finite list 67% and the others are either free or finite lists. All three lists 68% are in the same order. 69% 70% @see pairs_values/2 and pairs_keys/2. 71 72pairs_keys_values(Pairs, Keys, Values) :- 73 ( nonvar(Pairs) 74 -> pairs_keys_values_(Pairs, Keys, Values) 75 ; nonvar(Keys) 76 -> keys_values_pairs(Keys, Values, Pairs) 77 ; values_keys_pairs(Values, Keys, Pairs) 78 ). 79 80pairs_keys_values_([], [], []). 81pairs_keys_values_([K-V|Pairs], [K|Keys], [V|Values]) :- 82 pairs_keys_values_(Pairs, Keys, Values). 83 84keys_values_pairs([], [], []). 85keys_values_pairs([K|Ks], [V|Vs], [K-V|Pairs]) :- 86 keys_values_pairs(Ks, Vs, Pairs). 87 88values_keys_pairs([], [], []). 89values_keys_pairs([V|Vs], [K|Ks], [K-V|Pairs]) :- 90 values_keys_pairs(Vs, Ks, Pairs). 91 92%! pairs_values(+Pairs, -Values) is det. 93% 94% Remove the keys from a list of Key-Value pairs. Same as 95% pairs_keys_values(Pairs, _, Values) 96 97pairs_values([], []). 98pairs_values([_-V|T0], [V|T]) :- 99 pairs_values(T0, T). 100 101 102%! pairs_keys(+Pairs, -Keys) is det. 103% 104% Remove the values from a list of Key-Value pairs. Same as 105% pairs_keys_values(Pairs, Keys, _) 106 107pairs_keys([], []). 108pairs_keys([K-_|T0], [K|T]) :- 109 pairs_keys(T0, T). 110 111 112%! group_pairs_by_key(+Pairs, -Joined:list(Key-Values)) is det. 113% 114% Group values with equivalent (==/2) consecutive keys. For 115% example: 116% 117% ``` 118% ?- group_pairs_by_key([a-2, a-1, b-4, a-3], X). 119% 120% X = [a-[2,1], b-[4], a-[3]] 121% ``` 122% 123% Sorting the list of pairs before grouping can be used to group 124% _all_ values associated with a key. For example, finding all 125% values associated with the largest key: 126% 127% ``` 128% ?- sort(1, @>=, [a-1, b-2, c-3, a-4, a-5, c-6], Ps), 129% group_pairs_by_key(Ps, [K-Vs|_]). 130% K = c, 131% Vs = [3, 6]. 132% ``` 133% 134% In this example, sorting by key only (first argument of sort/4 135% is 1) ensures that the order of the values in the original list 136% of pairs is maintained. 137% 138% @arg Pairs Key-Value list 139% @arg Joined List of Key-Group, where Group is the 140% list of Values associated with equivalent 141% consecutive Keys in the same order as they 142% appear in Pairs. 143 144group_pairs_by_key([], []). 145group_pairs_by_key([M-N|T0], [M-[N|TN]|T]) :- 146 same_key(M, T0, TN, T1), 147 group_pairs_by_key(T1, T). 148 149same_key(M0, [M-N|T0], [N|TN], T) :- 150 M0 == M, 151 !, 152 same_key(M, T0, TN, T). 153same_key(_, L, [], L). 154 155 156%! transpose_pairs(+Pairs, -Transposed) is det. 157% 158% Swap Key-Value to Value-Key. The resulting list is sorted using 159% keysort/2 on the new key. 160 161transpose_pairs(Pairs, Transposed) :- 162 flip_pairs(Pairs, Flipped), 163 keysort(Flipped, Transposed). 164 165flip_pairs([], []). 166flip_pairs([Key-Val|Pairs], [Val-Key|Flipped]) :- 167 flip_pairs(Pairs, Flipped). 168 169 170%! map_list_to_pairs(:Function, +List, -Keyed) is det. 171% 172% Create a Key-Value list by mapping each element of List. 173% For example, if we have a list of lists we can create a 174% list of Length-List using 175% 176% ``` 177% map_list_to_pairs(length, ListOfLists, Pairs), 178% ``` 179 180map_list_to_pairs(Function, List, Pairs) :- 181 map_list_to_pairs2(List, Function, Pairs). 182 183map_list_to_pairs2([], _, []). 184map_list_to_pairs2([H|T0], Pred, [K-H|T]) :- 185 call(Pred, H, K), 186 map_list_to_pairs2(T0, Pred, T)