1/* Part of SWI-Prolog 2 3 WWW: http://www.swi-prolog.org 4 Copyright (c) 2020-2021, SWI-Prolog Solutions b.v. 5 All rights reserved. 6 7 Redistribution and use in source and binary forms, with or without 8 modification, are permitted provided that the following conditions 9 are met: 10 11 1. Redistributions of source code must retain the above copyright 12 notice, this list of conditions and the following disclaimer. 13 14 2. Redistributions in binary form must reproduce the above copyright 15 notice, this list of conditions and the following disclaimer in 16 the documentation and/or other materials provided with the 17 distribution. 18 19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 20 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 21 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 22 FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 23 COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 24 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 25 BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 26 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 27 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 28 LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 29 ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 30 POSSIBILITY OF SUCH DAMAGE. 31*/ 32 33:- module(sicstus4_lists, 34 [ keys_and_values/3, % ?Pairs, ?Keys, ?Values 35 rev/2, % +List, ?Reversed 36 shorter_list/2, % ?Short, ?Long 37 append_length/4, % ?Prefix, ?Suffix, ?List, ?Length 38 append_length/3, % ?Suffix, ?List, ?Length 39 prefix_length/3, % ?List, ?Prefix, ?Length 40 proper_prefix_length/3, % ?List, ?Prefix, ?Length 41 suffix_length/3, % ?List, ?Suffix, ?Length 42 proper_suffix_length/3, % ?List, ?Suffix, ?Length 43 sublist/5, % +Whole, ?Part, ?Before, ?Length, ?After 44 sublist/4, % +Whole, ?Part, ?Before, ?Length 45 sublist/3, % +Whole, ?Part, ?Before 46 cons/3, % ?Head, ?Tail, ?List 47 last/3, % ?Fore, ?Last, ?List 48 head/2, % ?List, ?Head 49 tail/2, % ?List, ?Tail 50 prefix/2, % ?List, ?Prefix 51 proper_prefix/2, % ?List, ?Prefix 52 suffix/2, % ?List, ?Suffix 53 proper_suffix/2, % ?List, ?Suffix 54 subseq/3, % ?Sequence, ?SubSequence, ?Complement 55 subseq0/2, % +Sequence, ?SubSequence 56 subseq1/2, % +Sequence, ?SubSequence 57 scanlist/4, % :Pred, ?Xs, ?V1, ?V 58 scanlist/5, % :Pred, ?Xs, ?Ys, ?V1, ?V 59 scanlist/6, % :Pred, ?Xs, ?Ys, ?Zs, ?V1, ?V 60 61 % is_list/1 is built-in on SWI. 62 % We re-export it here to avoid warnings 63 % when SICStus code explicitly imports it from library(lists). 64 is_list/1 % +Term 65 ]). 66:- reexport('../../lists', 67 [ select/3, 68 selectchk/3, 69 append/2, 70 delete/3, 71 last/2, 72 % SWI lists:list_to_set/2 actually behaves 73 % like SICStus lists:remove_dups/2 74 % and not like SICStus sets:list_to_set/2. 75 list_to_set/2 as remove_dups, 76 nextto/3, 77 nth1/3, 78 nth1/4, 79 nth0/3, 80 nth0/4, 81 permutation/2, 82 proper_length/2, 83 reverse/2, 84 same_length/2, 85 select/4, 86 selectchk/4, 87 sum_list/2 as sumlist, 88 max_member/2, 89 min_member/2, 90 max_member/3, 91 min_member/3, 92 clumped/2 93 ]). 94:- reexport('../../apply', 95 [ maplist/2, 96 maplist/3, 97 maplist/4, 98 convlist/3, 99 exclude/3, 100 include/3, 101 partition/5 102 ]). 103:- reexport('../../clp/clpfd', [transpose/2]). 104:- reexport('../sicstus/lists', [same_length/3]). 105:- use_module(library(pairs), [pairs_keys_values/3]). 106 107:- multifile sicstus4:rename_module/2. 108 109sicstus4rename_module(lists, sicstus4_lists). 110 111/** <module> SICStus 4-compatible library(lists). 112 113@tbd This library is incomplete. 114 As of SICStus 4.6.0, the following predicates are missing: 115 116 * append/5 117 * correspond/4 118 * delete/4 119 * one_longer/2 120 * perm/2 121 * perm2/4 122 * rotate_list/[2,3] 123 * segment/2 124 * proper_segment/2 125 * cumlist/[4,5,6] 126 * map_product/4 127 * some/[2,3,4] 128 * somechk/[2,3,4] 129 * exclude/[4,5] 130 * include/[4,5] 131 * group/[3,4,5] 132 * ordered/[1,2] 133 * select_min/[3,4] 134 * select_max/[3,4] 135 * increasing_prefix/[3,4] 136 * decreasing_prefix/[3,4] 137 * clumps/2 138 * keyclumps/2 139 * keyclumped/2 140 141@see https://sicstus.sics.se/sicstus/docs/4.6.0/html/sicstus.html/lib_002dlists.html 142*/ 143 144keys_and_values(Pairs, Keys, Values) :- 145 pairs_keys_values(Pairs, Keys, Values). 146 147 148%% rev(+List, ?Reversed) is semidet. 149% 150% Same as reverse/2, but List must be a proper list. 151 152rev(List, Reversed) :- rev_(List, [], Reversed). 153rev_([], Reversed, Reversed). 154rev_([Head|Tail], RevTail, Reversed) :- 155 rev_(Tail, [Head|RevTail], Reversed). 156 157 158%% shorter_list(?Short, ?Long) is nondet. 159% 160% True if Short is a shorter list than Long. The lists' contents 161% are insignificant, only the lengths matter. Mode -Short, +Long 162% can be used to enumerate list skeletons shorter than Long. 163 164shorter_list([], [_|_]). 165shorter_list([_|ShortTail], [_|LongTail]) :- 166 shorter_list(ShortTail, LongTail). 167 168 169% TODO The *_length predicates can probably be implemented more efficiently. 170 171append_length(Prefix, Suffix, List, Length) :- 172 append(Prefix, Suffix, List), 173 length(Prefix, Length). 174 175append_length(Suffix, List, Length) :- 176 append_length(_, Suffix, List, Length). 177 178prefix_length(List, Prefix, Length) :- 179 prefix(List, Prefix), 180 length(Prefix, Length). 181 182proper_prefix_length(List, Prefix, Length) :- 183 proper_prefix(List, Prefix), 184 length(Prefix, Length). 185 186suffix_length(List, Suffix, Length) :- 187 suffix(List, Suffix), 188 length(Suffix, Length). 189 190proper_suffix_length(List, Suffix, Length) :- 191 proper_suffix(List, Suffix), 192 length(Suffix, Length). 193 194 195sublist(Whole, Part, Before, Length, After) :- 196 append(Prefix, Tail, Whole), 197 append(Part, Suffix, Tail), 198 length(Prefix, Before), 199 length(Part, Length), 200 length(Suffix, After). 201 202sublist(Whole, Part, Before, Length) :- 203 sublist(Whole, Part, Before, Length, _). 204 205sublist(Whole, Part, Before) :- 206 sublist(Whole, Part, Before, _, _). 207 208 209cons(Head, Tail, [Head|Tail]). 210last(Fore, Last, List) :- append(Fore, [Last], List). 211head([Head|_], Head). 212tail([_|Tail], Tail). 213 214 215%% prefix(?List, ?Prefix) is nondet. 216% 217% True if Prefix is a prefix of List. Not the same as prefix/2 218% in SICStus 3 or SWI - the arguments are reversed! 219 220prefix(List, Prefix) :- 221 append(Prefix, _, List). 222 223%% proper_prefix(?List, ?Prefix) is nondet. 224% 225% True if Prefix is a prefix of List, but is not List itself. 226 227proper_prefix(List, Prefix) :- 228 prefix(List, Prefix), 229 Prefix \== List. 230 231%% suffix(?List, ?Prefix) is nondet. 232% 233% True if Suffix is a suffix of List. Not the same as suffix/2 234% in SICStus 3 - the arguments are reversed! 235 236suffix(List, List). 237suffix([_|Tail], Suffix) :- 238 suffix(Tail, Suffix). 239 240%% proper_suffix(?List, ?Prefix) is nondet. 241% 242% True if Suffix is a suffix of List, but is not List itself. 243 244proper_suffix([_|Tail], Suffix) :- 245 suffix(Tail, Suffix). 246 247 248%% scanlist(:Pred, ?Xs, ?V1, ?V) is nondet. 249%% scanlist(:Pred, ?Xs, ?Ys, ?V1, ?V) is nondet. 250%% scanlist(:Pred, ?Xs, ?Ys, ?Zs, ?V1, ?V) is nondet. 251% 252% Same as foldl/[4,5,6]. 253% 254% @compat SICStus 4 255 256:- meta_predicate scanlist(, , , ). 257scanlist(Pred, Xs, V1, V) :- foldl(Pred, Xs, V1, V). 258:- meta_predicate scanlist(, , , , ). 259scanlist(Pred, Xs, Ys, V1, V) :- foldl(Pred, Xs, Ys, V1, V). 260:- meta_predicate scanlist(, , , , , ). 261scanlist(Pred, Xs, Ys, Zs, V1, V) :- foldl(Pred, Xs, Ys, Zs, V1, V). 262 263 264subseq(Sequence, [], Sequence). 265subseq([Head|Tail], [Head|SubTail], Complement) :- 266 subseq(Tail, SubTail, Complement). 267subseq([Head|Tail], SubSequence, [Head|Complement]) :- 268 subseq(Tail, SubSequence, Complement). 269 270 271subseq0(Sequence, SubSequence) :- subseq(Sequence, SubSequence, _). 272subseq1(Sequence, SubSequence) :- 273 subseq(Sequence, SubSequence, Complement), 274 Complement \== []