1% BEGIN LICENSE BLOCK 2% Version: CMPL 1.1 3% 4% The contents of this file are subject to the Cisco-style Mozilla Public 5% License Version 1.1 (the "License"); you may not use this file except 6% in compliance with the License. You may obtain a copy of the License 7% at www.eclipse-clp.org/license. 8% 9% Software distributed under the License is distributed on an "AS IS" 10% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See 11% the License for the specific language governing rights and limitations 12% under the License. 13% 14% The Original Code is The ECLiPSe Constraint Logic Programming System. 15% The Initial Developer of the Original Code is Cisco Systems, Inc. 16% Portions created by the Initial Developer are 17% Copyright (C) 2006 Cisco Systems, Inc. All Rights Reserved. 18% 19% Contributor(s): 20% 21% END LICENSE BLOCK 22 23:- comment(alias, "Comparing and Sorting"). 24:- comment(summary, "Built-ins for symbolic term comparison and sorting"). 25:- comment(categories, ["Built-In Predicates"]). 26 27:- tool(current_domain / 3). 28:- tool(domain_index / 3). 29 30:- comment((@=<) / 2, [ 31 summary:"Succeeds if term Term1 is before or equal to Term2 in the standard 32ordering. 33 34", 35 template:"?Term1 @=< ?Term2", 36 amode:(@=<(?,?) is semidet), 37 desc:html(" Succeeds if term Term1 is before or equal to term Term2 in the standard 38 order of terms (defined under compare/3). 39<P> 40 See compare/3 for the definition of this standard ordering. 41<P> 42"), 43 args:["Term1" : "An arbitrary term.", "Term2" : "An arbitrary term."], 44 fail_if:"Fails if Term1 comes after Term2.", 45 eg:" 46 Success: 47 X @=< 1.0. (gives X = _g68) 48 1.0 @=< 0. 49 0 @=< \"zero\". 50 same @=< same. 51 diffa @=< diffb. 52 [a|b] @=< [a,b]. 53 [a,b|X] @=< [a,b,c]. (gives X = _g90) 54 f(100) @=< f(0,0). 55 a(100) @=< b(1). 56 Fail: 57 1.0 @=< X. 58 0 @=< 1.0. 59 atom @=< \"atom\". 60 a(1,2,3) @=< a(1,2,X). 61 62 63 64", 65 see_also:[compare/3, (@>) / 2, (@<) / 2, (@>=) / 2]]). 66 67:- comment((@>) / 2, [ 68 summary:"Succeeds if term Term1 is after term Term2 in the standard ordering. 69 70", 71 template:"?Term1 @> ?Term2", 72 amode:(@>(?,?) is semidet), 73 desc:html(" Succeeds if term Term1 is after term Term2 in the standard ordering of 74 terms. 75 76<P> 77 See compare/3 for the definition of this standard ordering. 78<P> 79"), 80 args:["Term1" : "An arbitrary term.", "Term2" : "An arbitrary term."], 81 fail_if:"Fails if Term1 does not come after Term2.", 82 eg:" 83 Success: 84 0.0 @> X. (gives X = _g70) 85 0 @> 0.0. 86 0 @> 1.0. 87 atomb @> atoma. 88 [a,b] @> [a|b]. 89 f(1,1) @> f(1). 90 b(1) @> a(1). 91 a(1,1,1,2) @> a(1,1,1,1). 92 Fail: 93 X @> 1.0. 94 atom @> atom. 95 [a|X] @> [a,b,c,d]. 96 a(1) @> a(2). 97 98 99 100", 101 see_also:[compare/3, (@=<) / 2, (@<) / 2, (@>=) / 2]]). 102 103:- comment((@>=) / 2, [ 104 summary:"Succeeds if term Term1 is after or equal to Term2 in the standard ordering. 105 106", 107 template:"?Term1 @>= ?Term2", 108 amode:(@>=(?,?) is semidet), 109 desc:html(" Succeeds if term Term1 is after or equal to term Term2 in the standard 110 order of terms (defined under compare/3). 111 112<P> 113 See compare/3 for the definition of this standard ordering. 114<P> 115"), 116 args:["Term1" : "An arbitrary term.", "Term2" : "An arbitrary term."], 117 fail_if:"Fails if Term1 comes before Term2.", 118 eg:" 119 Success: 120 1.0 @>= X. (gives X = _g70) 121 0 @>= 1.0. 122 0 @>= 0. 123 \"ab\" @>= \"aa\". 124 atomb @>= atoma. 125 [a,b] @>= [a|b]. 126 f(1,2,3) @>= f(4,5). 127 longe(1) @>= long(1). 128 a(2) @>= a(1). 129 Fail: 130 X @>= 1. 131 atoma @>= atomb. 132 a(1,2,3) @>= a(1,2,4). 133 134 135 136", 137 see_also:[compare/3, (@=<) / 2, (@<) / 2, (@>) / 2]]). 138 139:- comment((@<) / 2, [ 140 summary:"Succeeds if term Term1 is before term Term2 in the standard ordering. 141 142", 143 template:"?Term1 @< ?Term2", 144 amode:(@<(?,?) is semidet), 145 desc:html(" Succeeds if term Term1 precedes term Term2 in the standard ordering of 146 terms. 147 148<P> 149 See compare/3 for the definition of this standard ordering. 150<P> 151"), 152 args:["Term1" : "An arbitrary term.", "Term2" : "An arbitrary term."], 153 fail_if:"Fails if Term1 does not precede Term2.", 154 eg:" 155 Success: 156 X @< 1.0. (gives X = _g68) 157 0.0 @< 1. 158 2.0 @< 1. 159 \"a\" @< a. 160 atoma @< atomb. 161 [a|b] @< [a,b]. 162 b(1) @< a(1,1). 163 a(1,2,3,4.0) @< a(1,2,3,0). 164 Fail: 165 1.0 @< X. 166 atomb @< atoma. 167 f(1,1) @< f(1). 168 169 170 171", 172 see_also:[compare/3, (@>) / 2, (@=<) / 2, (@>=) / 2]]). 173 174:- comment(compare / 3, [ 175 summary:"Succeeds if Ordering is a special atom which describes the ordering between 176Term1 and Term2. 177 178", 179 amode:(compare(-,?,?) is det), 180 desc:html("\ 181 Succeeds if Ordering is one of the special atoms ('<', '>' or '=') 182 describing the standard ordering between the terms Term1 and Term2: 183 184<P> 185 Ordering is the atom '<' iff Term1 comes before Term2 in the standard 186 ordering. 187 188<P> 189 Ordering is the atom '>' iff Term1 comes after Term2 in the standard 190 ordering. 191 192<P> 193 Ordering is the atom '=' iff Term1 is identical to Term2. 194 195<P> 196 The standard ordering of ECLiPSe terms is defined as the following 197 increasing order: 198<DL> 199<DT><STRONG>variables</STRONG><DD> 200 (comparing two free variables yields an implementation-dependent 201 and not necessarily reproducible result). 202 203<DT><STRONG>bounded reals</STRONG><DD> 204 in ascending order (if bounds overlap, the order is by increasing lower 205 bounds, then increasing upper bounds; if both bounds are the same, the 206 two terms are considered equal). 207 208<DT><STRONG>floats</STRONG><DD> 209 in ascending order, with negative zeros (-0.0) being different and 210 before positive zeros (0.0). 211 212<DT><STRONG>rationals</STRONG><DD> 213 in ascending order. 214 215<DT><STRONG>integers</STRONG><DD> 216 in ascending order. 217 218<DT><STRONG>strings</STRONG><DD> 219 lexicographical order, according to character encoding 220 221<DT><STRONG>atoms</STRONG><DD> 222 lexicographical order, according to character encoding 223 224<DT><STRONG>compound terms</STRONG><DD> 225 first by arity, then by functor name, then by the 226 arguments in left to right order. 227 228<DT><STRONG>suspensions</STRONG><DD> 229 in order of creation. 230 231<DT><STRONG>handles</STRONG><DD> 232 according to their class and physical address. 233</DL> 234 235 Note in particular that numbers are first ordered by their type (integer, 236 float, etc) and only then by their magnitude, i.e. when comparing numbers 237 of different types, the result is not necessarily their numerical order. 238"), 239 args:["Ordering" : "Unifiable to a special atom describing the ordering between Term1 and Term2.", "Term1" : "An arbitrary term.", "Term2" : "An arbitrary term."], 240 eg:" 241 Success: 242 compare(X, A, a), X = '<'. 243 compare(X, a, A), X = '>'. 244 compare('<', a(1,2), b(1,2)). 245 compare(X, 1, 1), X = '='. 246 compare(X, f(1), f(1)), X = '='. 247 compare('<', 3.0, 2). % not arithmetic order! 248 compare('>', [a,b], [a|b]). 249 compare('>', [a,b], [a|X]). 250 Fail: 251 compare('<', atomb, atoma). 252 compare('=', 0, 1). 253 compare('>',1.0,1). 254 255 256 257", 258 see_also:[(@>) / 2, (@<) / 2, (@=<) / 2, (@>=) / 2]]). 259 260:- comment(compare_instances / 3, [ 261 summary:"Succeeds if Relationship is an atom describing the instance relationship 262between Term1 and Term2. 263 264", 265 amode:(compare_instances(-,?,?) is det), 266 desc:html(" Succeeds if Relationship is unified with one of the three term 267 relationship symbols indicated by '<', '>', '=' where: 268 269<P> 270 '<': Term1 is an instance of Term2. 271 272<P> 273 '>': Term2 is an instance of Term1. 274 275<P> 276 '=': Term1 is variant of Term2. 277 278<P> 279 For the definition of instance and variant refer to instance/2 and 280 variant/2, respectively. 281 282<P> 283"), 284 args:["Relationship":"Variable or one of the atoms '<', '>', '='", 285 "Term1":"An arbitrary term.", 286 "Term2":"An arbitrary term."], 287 fail_if:"Fails if none of the terms is an instance of the other", 288 eg:" 289 Success: 290 compare_instances(Rel,X,Y), Rel == '='. 291 compare_instances(=, [a,X], [a,Y]). 292 compare_instances(<, [a,b], [X,Y]). 293 compare_instances(<, [X], [X|Y]). 294 compare_instances(>, X, f(1,1)). 295 compare_instances(<, f(1,1), X). 296 Fail: 297 compare_instances(Rel, f(X), 1). 298 compare_instances(Rel, 1, f(X)). 299 compare_instances(<, X, a). 300 301 302 303", 304 see_also:[instance / 2, variant / 2]]). 305 306:- comment((=) / 2, [ 307 summary:"Succeeds if Term1 and Term2 unify. 308 309", 310 template:"?Term1 = ?Term2", 311 amode:(=(?,?) is semidet), 312 desc:html(" Succeeds if the term Term1 unifies with the term Term2, 313 otherwise it fails. 314 315<P> 316 The unification procedure does not contain an occur check. Hence, 317 cyclic structures can be created during unification. These cyclic 318 structures may cause loops in attempting unification. eg. X = f(X,Y), 319 Y = f(X,Y). 320 321<P> 322"), 323 args:["Term1" : "An arbitrary term.", "Term2" : "An arbitrary term."], 324 fail_if:"Fails if Term1 does not unify with Term2.", 325 exceptions:[11 : "Term1 or Term2 contain an attributed variable and it is unified with a nonvariable."], 326 eg:" 327 Success: 328 atom = atom. 329 atom = X. (gives X = atom) 330 X = atom. (gives X = atom) 331 f(1) = X. (gives X = f(1)) 332 Y = X. (gives Y = _g68, X = _g68) 333 [1,X] = [Y,2]. (gives X = 2, Y = 1) 334 [1,X|Y] = [W,2|Z]. (gives X = 2, Y = _g78, 335 W = 1, Z = _g78) 336 [1,A,2,B] = [C|D]. (gives A = _g80, B = _g88, 337 C = 1, D = [_g80, 2, _g88]) 338 Fail: 339 atom = neutron. 340 1.0 = 1. 341 [a|b] = [a,b]. 342 343 344 345", 346 see_also:[(==) / 2, (\=) / 2]]). 347 348:- comment((==) / 2, [ 349 summary:"Succeeds if Term1 and Term2 are identical terms. 350 351", 352 template:"?Term1 == ?Term2", 353 amode:(==(?,?) is semidet), 354 desc:html(" Used to compare Term1 with Term2. Succeeds if Term1 and Term2 are 355 identical terms. It does not attempt unification. Two variables are 356 considered as identical only if one is bound to the other, or if they 357 are both bound to identical terms. Ground terms are identical only if 358 they unify. 359 360<P> 361"), 362 args:["Term1" : "An arbitrary term.", "Term2" : "An arbitrary term."], 363 fail_if:"Fails if Term1 and Term2 are not identical.", 364 eg:" 365 Success: 366 atom == atom. 367 1 == 1. 368 X == X. (gives X = _g70) 369 X = 1, Y = 1, Y == X. (gives X = 1, Y = 1) 370 X = Y, X == Y, Y == X. (gives Y = _g80, X = _g80) 371 [ a,b| [ ] ] == [ a,b ]. 372 f(1,2) == f(1,2). 373 Fail: 374 atom == neutron. 375 atom == X. 376 1 == 1.0. 377 X == Y. 378 [a|b] == [a,b]. 379 [a|X] == [a,X]. 380 381 382 383", 384 see_also:[(\==) / 2, (=) / 2]]). 385 386:- comment(instance / 2, [ 387 summary:"Succeeds if Instance is an instance of Term. 388 389", 390 amode:(instance(?,?) is semidet), 391 desc:html(" Succeeds if it is possible to find an instantiation of free variables in 392 Term such that Term and Instance are equal. The result is undefined if 393 Term and Instance share variables. Note that no unification actually 394 occurs. 395<P> 396 Attributed variables are handled via the attribute's compare_instances 397 handler. In particular, domain variables should be handled correctly. 398<P> 399"), 400 args:["Instance" : "An arbitrary term.", "Term" : "An arbitrary term."], 401 fail_if:"Fails if Instance is not an instance of Term.", 402 eg:" 403 Success: 404 instance(atom,X). 405 instance(f(a,b),X). 406 instance(f(a,b),f(X,Y)). 407 instance(f(a,X),f(Y,X)). 408 instance(f(a,X),f(X,Y)). 409 instance(f(X,Y),f(Y,X)). 410 instance([a,b,c],[A,B,C]). 411 instance([a,f(1,b,X),Y|Z],T). 412 X::1..5, instance(3,X). 413 X::2..4, Y::1..5, instance(X,Y). 414 415 Fail: 416 instance(f(a,b),f(X,X)). 417 instance(X,a). 418 X::2..4, Y::1..5, instance(Y,X). 419", 420 see_also:[compare_instances / 3, prune_instances / 2, variant / 2]]). 421 422:- comment((\=) / 2, [ 423 summary:"Succeeds if Term1 and Term2 are not unifiable. 424 425", 426 template:"?Term1 \\= ?Term2", 427 amode:(\=(?,?) is semidet), 428 desc:html(" Succeeds if Term1 and Term2 are not unifiable. It is implemented like 429 430<P> 431<PRE> 432 X \\= X :- true, !, fail. 433 _ \\= _. 434</PRE> 435 I.e. the arguments are unified, which may cause delayed goals to be 436 woken and constraints to be checked. Only if all this succeeds, \\=/2 437 fails. 438 439<P> 440 This predicate has a negation-as-failure semantics and so if the 441 compared terms are not ground, it may give unexpected results. Note 442 that the original arguments are unchanged after the predicate succeeds. 443 444<P> 445"), 446 args:["Term1" : "An arbitrary term.", "Term2" : "An arbitrary term."], 447 fail_if:"Fails if Term1 and Term2 can be unified.", 448 eg:" 449Success: 450 atom \\= neutron. 451 1.0 \\= 1. 452 f(1,2) \\= f(1,3). 453 [1,2] \\= [1,3]. 454 [a,b,c] \\= [a,b|c]. 455 [a,b,c] \\= [X]. 456 [a,X,c,Y] \\= [X,b,Y,d]. 457 coroutine, X > 1, X \\= 1. 458Fail: 459 X \\= Y. 460 1 \\= X. 461 [a,b|X] \\= X. 462 463 464 465", 466 see_also:[(=) / 2, (\==) / 2, not_unify / 2]]). 467 468:- comment((\==) / 2, [ 469 summary:"Succeeds if Term1 and Term2 are not identical terms. 470 471", 472 template:"?Term1 \\== ?Term2", 473 amode:(\==(?,?) is semidet), 474 desc:html(" Used to compare the terms Term1 with Term2. Succeeds if Term1 475 and Term2 are not identical terms. Two variables are considered as 476 identical only if one is bound to the other one, or if they are bound to 477 identical terms. 478 479<P> 480"), 481 args:["Term1" : "An arbitrary term.", "Term2" : "An arbitrary term."], 482 fail_if:"Fails if Term1 and Term2 are identical.", 483 eg:" 484Success: 485 atom \\== neutron. 486 atom \\== X. 487 X \\== atom. 488 1 \\== 1.0. 489 X \\== Y. 490 [a|b] \\== [a,b]. 491 [a|X] \\== [a,X]. 492 f(a,b) \\== [f,a,b]. 493 f(1,2,3) \\== f(1,2,3.0). 494Fail: 495 a \\== a. 496 X \\== X. 497 X = Y, X \\== Y. 498 [a,b|[]] \\== [a,b]. 499 500 501 502", 503 see_also:[(==) / 2, (\=) / 2]]). 504 505:- comment(occurs / 2, [ 506 summary:"Succeeds if Simple is a variable or an atomic type that occurs in the term 507Term. 508 509", 510 amode:(occurs(?,?) is semidet), 511 desc:html(" Succeeds if Simple is a variable, an atom or a number occurring in the 512 term Term. 513 514<P> 515"), 516 args:["Simple" : "Variable or atomic type.", "Term" : "An arbitrary term."], 517 fail_if:"Fails if Simple does not occur in the term Term.", 518 exceptions:[5 : "If Simple is neither a variable, an atom nor a number."], 519 eg:" 520 Success: 521 occurs(a,a). 522 occurs(X,f(a,b,c,X)). 523 occurs(+,f(+,-)). 524 occurs(a,[b,c,a,g,a]). 525 occurs([ ],[a,b]). 526 occurs(1,[A|1]). 527 occurs(1.0,[1.0|B]). 528 Fail: 529 occurs(a,b). 530 occurs(X,f(Y,Z)). 531 occurs(X,Y). 532 occurs(1,\"2314\"). 533 occurs([], [a,b|c]). 534 Error: 535 occurs(\"str\",f(\"str1\",\"str2\",\"str\")). (Error 5) 536 occurs([a],[a,b]). (Error 5) 537 occurs(f(a,b),f(a,b)). (Error 5) 538 539 540 541", 542 see_also:[instance / 2, variant / 2]]). 543 544:- comment((~=) / 2, [ 545 summary:"The sound difference operator. Succeeds if the two terms cannot be 546unified, fails if they are identical, otherwise it delays. 547 548", 549 template:"?Term1 ~= ?Term2", 550 amode:(~=(?,?) is semidet), 551 desc:html(" If Term1 cannot be unified with Term2 it succeeds. If the two terms are 552 unifiable but not identical, the predicate delays since it cannot yet 553 decide whether the terms are different or not. 554 555<P> 556"), 557 args:["Term1" : "Any term.", "Term2" : "Any term."], 558 fail_if:"Fails if Term1 and Term2 are identical in the sense of ==/2.", 559 eg:" 560Success: 561 3 ~= 4. 562 3 ~= X, (delays ... 563 X = 4. ... then succeeds and gives X = 4) 564 565Note the nonlogical behaviour of negation as failure: 566 3 \\= X, (fails ... 567 X = 4. ... and this is not recognized) 568 569Fail: 570 3 ~= 3. 571 s(X,Y) ~= s(X,Y). 572 s(X,Y) ~= s(X,Z), (delays ... 573 Z = Y. ... then fails) 574 575 576 577", 578 see_also:[(\=) / 2, (\==) / 2, (==) / 2, (~) / 1]]). 579 580:- comment(variant / 2, [ 581 summary:"Succeeds if Term1 is a variant of Term2. 582 583", 584 amode:(variant(?,?) is semidet), 585 desc:html(" Succeeds if the given terms are equal in the sense that all 586 ground instantiations in Term1 are also instantiations in Term2 and vice 587 versa. The result is undefined if Term1 and Term2 share variables. No 588 unification is performed. 589<P> 590 Attributed variables are handled via the attribute's compare_instances 591 handler. In particular, domain variables should be handled correctly. 592<P> 593"), 594 args:["Term1" : "An arbitrary term.", "Term2" : "An arbitrary term."], 595 fail_if:"Fails if Term1 is not a variant of Term2.", 596 eg:" 597 Success: 598 variant(1,1). 599 variant(X,Y). 600 variant(f(a,b),f(a,b)). 601 variant(f(a,X),f(a,Y)). 602 variant(f(X,Y),f(Y,X)). 603 variant([X,2], [Y,2]). 604 [X,Y]::2..4, variant(X,Y). 605 606 Fail: 607 variant(f(a,b),f(a,Y)). 608 variant(f(a,X),f(a,b)). 609 variant(f(X,Y),f(Z,Z)). 610 X::2..4, Y::1..5, variant(X,Y). 611", 612 see_also:[instance / 2, compare_instances / 3, prune_instances / 2]]). 613 614:- comment(not_unify / 2, [ 615 summary:"Succeeds if Term1 and Term2 are not unifiable. 616 617", 618 amode:(not_unify(?,?) is semidet), 619 desc:html(" Succeeds if Term1 and Term2 are not unifiable. This predicate differs 620 from \\=/2 only if attributed variables are involved (e.g. with delayed goals or 621 constraints). While \\=/2 does unification, waking of delayed goals and 622 full constraint propagation to determine unifiability, not_unify/2 uses 623 the test_unify-handler for this purpose. not_unify/2 is therefore 624 likely to be cheaper, but possibly less precise (depending on the 625 test_unify-handler) than \\=/2. 626 627<P> 628"), 629 args:["Term1" : "An arbitrary term.", "Term2" : "An arbitrary term."], 630 fail_if:"Fails if Term1 and Term2 can be unified.", 631 eg:" 632Success: 633 not_unify(atom, neutron). 634 not_unify(1.0, 1). 635Fail: 636 not_unify(X, Y). 637 not_unify(X, 1). 638Note the difference: 639 coroutine, X > 1, X \\= 1. 640 % succeeds because the delayed goal X>1 is 641 % taken into account 642 coroutine, X > 1, not_unify(X, 1). 643 % fails because the delayed goal X>1 is 644 % ignored by the test_unify handler 645 646 647 648", 649 see_also:[(=) / 2, (\=) / 2, (\==) / 2, meta_attribute / 2]]). 650 651:- comment(keysort / 2, [ 652 summary:"Succeeds if List2 is a sorted list version of List1, whose elements are of 653the form Key-Value. The sort is done according to the value of the key 654Key. 655 656", 657 amode:(keysort(+,-) is det), 658 desc:html(" The elements of List1 are of the form Key-Value, where Key and Value are 659 both arbitrary terms. 660 661<P> 662 List1 is sorted according to the value of the key Key and the result is 663 unified with List2. No sorting is carried out on Value. The sort is 664 stable, i.e. the order of elements with the same key is preserved. 665 666<P> 667 The sort is done according to the standard ordering of terms. 668 See compare/3 for this standard ordering. 669 Note in particular that numbers are first ordered by their type (integer, 670 float, etc) and only then by their magnitude, i.e. sorting numbers of 671 different types may not give the expected result. 672 673<P> 674 keysort(R, S) is equivalent to sort(1, =<, R, S). 675<P> 676"), 677 args:["List1" : "List of elements of the form Term-Term.", "List2" : "List or variable."], 678 exceptions:[4 : "List1 is not instantiated.", 5 : "Either List1 or List2 is instantiated, but not to a list of the form Term-Term."], 679 eg:" 680Success: 681 keysort([n-1,4-a],L). (gives L = [4-a,n-1]]). 682 keysort([f(1)-a,[1]-w,7.2-b,\"k\"-e,n-q],L). 683 (gives L = [7.2-b,\"k\"-e,n-q,f(1)-a,[1]-w]). 684 keysort([f(1,2),g(1)],M). (gives M = [f(1,2),g(1)]). 685 keysort([g(1,2)-a, f(1,2)-a],M). 686 (gives M = [f(1,2)-a,g(1,2)-a]). 687 keysort([f(4,3)-a, f(3,4)-b],M). 688 (gives M = [f(3,4)-b,f(4,3)-a]). 689 690Fail: 691 keysort([n-1,M-a],[n-1,M-a]). 692 693Error: 694 keysort(L1,L2). (Error 4). 695 keysort([n-1,m],L). (Error 5). 696 697 698 699", 700 see_also:[compare / 3, merge / 3, merge / 5, msort / 2, sort / 4]]). 701 702:- comment(merge / 3, [ 703 summary:"Succeeds if List3 is a merged list of List1 and List2. If both lists are 704sorted, List3 will be sorted. 705 706", 707 amode:(merge(+,+,-) is det), 708 desc:html(" Used to merge the sorted lists List1 and List2 to give the sorted list 709 List3. merge(L1,L2,L3) is equivalent to merge(0,=<,L1,L2,L3). 710 711<P> 712 For two lists [e1,e2,e3] and [f1,f2,f3], e1 is compared to f1. The 713 lower (dictated by the standard ordering below) is put into List3, and 714 the process continued with the remaining input lists. This process 715 continues until both lists are exhausted. 716 717<P> 718 In particular, this will merge two sorted lists into a sorted list. 719 720<P> 721 The sort is done according to the standard ordering of terms. 722 Duplicates are not removed. See compare/3 for this standard ordering. 723 Note in particular that numbers are first ordered by their type (integer, 724 float, etc) and only then by their magnitude, i.e. sorting numbers of 725 different types may not give the expected result. 726 727<P> 728 merge(A, B, M) is equivalent to merge(0, =<, A, B, M). 729<P> 730"), 731 args:["List1" : "List.", "List2" : "List.", "List3" : "List or variable."], 732 eg:" 733Success: 734 merge([2,4,6],[1,3,5],L). 735 (gives L=[1,2,3,4,5,6]). 736 merge([f(1),f(7)],[f(8),f(10)],L). 737 (gives L=[f(1),f(7),f(8),f(10)]). 738 merge([f(5),f(8)],[f(1),f(2),f(2),f(5),f(8)],L). 739 (gives L=[f(1),f(2),f(2),f(5),f(5),f(8),f(8)]). 740 merge([a,w],[a,b,b,r,w],L). 741 (gives L=[a,a,b,b,r,w,w]). 742 merge([f(2),f(1)],[f(3),f(8)],L). 743 (gives L=[f(2),f(1),f(3),f(8)]). 744 745Fail: 746 merge([2,4,6],[1,3,5],[1,2,3,4,5]). 747 748 749 750", 751 see_also:[compare / 3, merge / 5, msort / 2, number_merge/3]]). 752 753:- comment(merge / 5, [ 754 summary:"Succeeds if List3 is a merged list of List1 and List2. If both lists are 755sorted, List3 will be sorted. The sort is done according to the Key and 756Order specifications. 757 758", 759 amode:(merge(+,+,+,+,-) is det), 760 desc:html("<P>\ 761 Generic list merge primitive: merges two sorted lists according to the Key 762 and Order specifications, and unifies List3 with the result. The sort 763 is stable, i.e. the order of elements with equal keys is preserved. 764</P><P> 765 The Key argument determines which part of the list elements is considered 766 the sorting key. If Key is 0, then the entire term is taken as the 767 sorting key (in this case, the list can contain anything, including 768 numbers, atoms, strings, compound terms, and even variables). If Key 769 is a positive integer (or a list of those), then the list elements will 770 get ordered by their Keyth subterm (in this case, the list must contain 771 compound terms with appropriate subterms). 772</P><P> 773 The Order argument specifies whether to use standard term order (@) or 774 numeric order ($), whether the list is sorted into ascending (<, =<) 775 or descending (>, >=) order, and whether duplicates are to be 776 retained (=<, >=) or removed (<, >). The way to remember the Order 777 argument is that it is the relation which holds between adjacent 778 elements in the result. 779<PRE> 780 Order ordering direction duplicates 781 --------------------------------------------------------------- 782 @< (or <) standard ascending removed 783 @=< (or =<) standard ascending retained 784 @> (or >) standard descending removed 785 @>= (or >=) standard descending retained 786 787 $< numeric ascending removed 788 $=< numeric ascending retained 789 $> numeric descending removed 790 $>= numeric descending retained 791</PRE> 792 The alternative ordering criteria are: 793 <DL> 794 <DT>@ standard term order</DT><DD> 795 The sort is done according to the standard ordering of terms. 796 This can be applied to any term, see compare/3 for the definition. 797 Note in particular that numbers are first ordered by their type 798 (integer, float, etc) and only then by their magnitude, i.e. 799 sorting numbers of different types may not give the expected result. 800 </DD> 801 <DT>$ numeric order</DT><DD> 802 The sort is done according to numeric order. The sorting keys must 803 all be numbers, but can be a mix of numeric types. They are compared 804 in the way they are compared by the arithmetic comparisons (</2, <=/2, etc). 805 Unlike standard order, this will consider numbers such as 3 and 3.0 806 as equal, and -0.0 as equal to 0.0. 807 </DD> 808 </DL> 809 See sort/4 for further details on ordering. 810</P><P> 811 Algorithm: For two lists [e1,e2,e3] and [f1,f2,f3], e1 is compared to f1. 812 The resulting element (dictated by Key, Order and the standard ordering 813 below, with ties being resolved in favour of the element from List1) 814 is put into List3, and the process continued with the remaining input 815 lists. This process continues until both lists are exhausted. 816</P><P> 817 In particular, this will merge two sorted lists into a new sorted list, 818 provided that the given ordering of the input lists is the same as the 819 ordering parameters (Key,Order) of the merge. The merge is stable, i.e. 820 the order of elements with equal keys is preserved. If List1 and List2 821 contain elements with identical keys, List1's elements will occur first 822 in List3. 823</P><P> 824 The other merging primitives may be defined in terms of merge/4 as follows: 825<PRE> 826 merge(L1, L2, L3) :- merge(0, @=<, L1, L2, L3). 827 number_merge(L1, L2, L3) :- merge(0, $=<, L1, L2, L3). 828</PRE> 829</P> 830"), 831 args:["Key" : "A non-negative integer, or a list of positive integers.", 832 "Order" : "One of the atoms =<, >=, < or >, possibly prefixed with @ or $.", 833 "List1" : "List.", "List2" : "List.", "List3" : "List or variable."], 834 exceptions:[5 : "Key is greater than 0, and one of List1 and List2 does not have all elements compound terms.", 5 : "Key is not an integer or a list of integers.", 6 : "One of the compound terms in List1 or List2 has not got as many as Key arguments."], 835 eg:" 836Success: 837 merge(0,<,[2,4,6],[1,3,5],L). 838 (gives L=[1,2,3,4,5,6]). 839 merge(0,<,[f(1),f(7)],[f(8),f(10)],L). 840 (gives L=[f(1),f(7),f(8),f(10)]). 841 merge(0,<,[f(2),f(1)],[f(3),f(8)],L). 842 (gives L=[f(2),f(1),f(3),f(8)]). 843 merge(0,<,[f(2)],[f(6),f(1)],L). 844 (gives L=[f(2),f(6),f(1)]). 845 merge(0,>,[1,e,q],[Q,2,a],L). 846 (gives Q=_g60,L=[_g60,1,2,a,e,q]). 847 merge(0,>,[f(8),f(6)],[f(4),f(1)],L). 848 (gives L=[f(8),f(6),f(4),f(1)]). 849 merge(2,<,[f(2,1),f(6,4)],[f(6,3),f(8,6)],L). 850 (gives L=[f(2,1),f(6,3),f(6,4),f(8,6)]). 851 merge(2,<,[q(2,1),f(6,4)],[a(6,3),i(8,6)],L). 852 (gives L=[q(2,1),a(6,3),f(6,4),i(8,6)]). 853 merge(2,<,[f(a,b),f(c,a)],[f(k,a)],L). 854 (gives L=[f(k,a),f(a,b),f(c,a)). 855 merge(0,=<,[1,2],[3,4,4,5],L). 856 (gives L=[1,2,3,4,4,5]). 857 merge([2,1], =<, [f(1,a(1)), f(0,a(3))], [f(3,a(2)), f(1,a(4))], L). 858 (gives L=[f(1,a(1)), f(3,a(2)), f(0,a(3)), f(1,a(4))]). 859Fail: 860 merge(0,<,[2,4,6],[1,3,5],[1,2,3,4,5]). 861Error: 862 merge(1,<,[f(1,2),f],[f(3,4),h(1,2)],L). (Error 5). 863 merge(0.0,<,[f(1)],[f(2)],L). (Error 5). 864 merge(2,<,[f(1,2)],[f(8)],L). (Error 6). 865 866 867 868", 869 see_also:[merge / 3, number_merge/3, compare / 3, sort/4]]). 870 871:- comment(msort / 2, [ 872 summary:"Succeeds if List2 has the same elements as List1 and is sorted. 873 874", 875 amode:(msort(+,-) is det), 876 desc:html("\ 877 List1 is sorted according to standard term ordering, (without 878 removing duplicates in the sense of ==/2) and unified with List2. 879<P> 880 The sort is done according to the standard ordering of terms. 881 Duplicates are not removed. See compare/3 for this standard ordering. 882 Note in particular that numbers are first ordered by their type (integer, 883 float, etc) and only then by their magnitude, i.e. sorting numbers of 884 different types may not give the expected result. 885<P> 886Note 887 msort(L1,L2) is equivalent to sort(0,=<,L1,L2). 888 msort(L1,L2) differs from sort(L1,L2) in that it keeps duplicates. 889 890<P> 891"), 892 args:["List1" : "List.", "List2" : "List or variable."], 893 exceptions:[4 : "List1 is not instantiated.", 5 : "List1 is not a list."], 894 eg:" 895Success: 896 msort([3,2,1,2,3],[1,2,2,3,3]). 897 msort([2,4,6],L). (gives L=[2,4,6]). 898 msort([2,4,6,1,7,3],L). (gives L=[1,2,3,4,6,7]). 899 900Fail: 901 msort([1,5,3,7],[1,3,7,5]). 902 903Error: 904 msort(List1,List2). (Error 4). 905 msort(\"[1]\",L). (Error 5). 906 907 908 909", 910 see_also:[compare / 3, sort / 2, sort / 4, number_sort/2]]). 911 912:- comment(number_merge / 3, [ 913 summary:"Succeeds if List3 is a merged list of List1 and List2. If both lists are 914sorted, List3 will be sorted. 915 916", 917 amode:(number_merge(+,+,-) is det), 918 desc:html(" Used to merge the sorted lists List1 and List2 to give the sorted list 919 List3. 920 921<P> 922 For two lists [e1,e2,e3] and [f1,f2,f3], e1 is compared to f1. The 923 lower (dictated by numerical ordering) is put into List3, and the 924 process continued with the remaining input lists. This process 925 continues until both lists are exhausted. 926 927 928<P> 929 In particular, this will merge two sorted lists into a sorted list. 930 931<P> 932 The sort is done according to numerical ordering of terms as opposed to 933 merge/3 which uses the standard ordering of terms. Duplicates are 934 not removed. See sort/4 for a discussion of the differences 935 between numerical and standard ordering of numeric types. 936 937<P> 938 number_merge(A, B, M) is equivalent to merge(0, $=<, A, B, M). 939<P> 940"), 941 args:["List1" : "List of numeric terms.", "List2" : "List of numeric terms.", "List3" : "List of numeric terms or variable."], 942 eg:" 943Success: 944 number_merge([2,4,6],[1,3,5],L). 945 (gives L=[1,2,3,4,5,6]). 946 number_merge([f(1),f(7)],[f(8),f(10)],L). 947 (gives L=[f(1),f(7),f(8),f(10)]). 948 number_merge([f(5),f(8)],[f(1),f(2),f(2),f(5),f(8)],L). 949 (gives L=[f(1),f(2),f(2),f(5),f(5),f(8),f(8)]). 950 number_merge([a,w],[a,b,b,r,w],L). 951 (gives L=[a,a,b,b,r,w,w]). 952 number_merge([f(2),f(1)],[f(3),f(8)],L). 953 (gives L=[f(2),f(1),f(3),f(8)]). 954 955Fail: 956 number_merge([2,4,6],[1,3,5],[1,2,3,4,5]). 957 958 959 960", 961 see_also:[merge/3, merge/5]]). 962 963 964:- comment(number_sort / 2, [ 965 summary:"Succeeds if List2 is the numerically ordered version of List1. 966 967", 968 amode:(number_sort(+,-) is det), 969 desc:html("\ 970 List1 is sorted according to numerical ordering, and unified with List2. 971<P> 972 The sort is done according to numerical ordering and duplicates are 973 retained as opposed to sort/2 which uses the standard ordering of 974 terms and removes duplicates. See sort/4 for a discussion of the 975 differences between numerical and standard ordering of numeric types. 976<P> 977Note 978 number_sort(L1,L2) is equivalent to sort(0,$=<,L1,L2). 979"), 980 args:["List1" : "List of numeric terms.", "List2" : "List of numeric terms or variable."], 981 eg:" 982Success: 983 sort([3,1,6,7,2],S). (gives S=[1,2,3,6,7]). 984 sort([1,3,2,3,4,1],S). (gives S=[1,1,2,3,3,4]). 985Fail: 986 sort([2,1,3,4],[2,1,3,4]). 987 988 989 990", 991 see_also:[sort/2, msort/2, sort/4]]). 992 993 994:- comment(prune_instances / 2, [ 995 summary:"Succeeds if PrunedList is the smallest list that subsumes the list List. 996 997", 998 amode:(prune_instances(+,-) is det), 999 desc:html(" Used to get the smallest list PrunedList whose elements subsume elements 1000 of the list List. List must not contain variables. If List contains 1001 elements which are variants of each other, then of these, PrunedList 1002 will only contain the first element found. If List contains element(s) 1003 which are instances of another element, then of these, PrunedList will 1004 only contain the latter. 1005 1006<P> 1007 Note that if List contains only ground terms, it cannot contain proper 1008 instances or variants, but only duplicates. Therefore, it is faster to 1009 use a sorting predicate to prune it. 1010 1011<P> 1012"), 1013 args:["List" : "List of instantiated terms.", "PrunedList" : "List or variable."], 1014 eg:" 1015Success: 1016 prune_instances([5,2,3,5,4,2],L). 1017 (gives L=[5,2,3,4]). 1018 1019 prune_instances([f(1,2),f(1,M),1],L). % instance 1020 (gives L=[f(1,M),1]). 1021 1022 prune_instances([f(1,2,3),f(1,M,3),f(1,2,N)],L). 1023 (gives L=[f(1,M,3),f(1,2,N)]). 1024 1025 prune_instances([f(1,N),f(1,M),1],L). % variants (first one retained) 1026 (gives L=[f(1,N),1]). 1027 1028 prune_instances([f(1,X),f(1,2),g(1)],L). 1029 (gives L=[f(1,X),g(1)]). 1030 1031 :- lib(ic). 1032 X::2..5, prune_instances([1,3,X,5,8], L). 1033 (gives L=[X,1,8]). 1034Fail: 1035 prune_instances([1,2,3,1,4,2],[2,3,4]). 1036 1037 1038 1039", 1040 see_also:[sort / 2, sort / 4]]). 1041 1042:- comment(sort / 2, [ 1043 summary:"Succeeds if List2 is the strictly ordered, no duplicates version of List1. 1044 1045", 1046 amode:(sort(+,-) is det), 1047 desc:html("\ 1048 List1 is sorted strictly according to standard term ordering 1049 (removing duplicates in the sense of ==/2), and unified with List2. 1050<P> 1051 The sort is done according to the standard ordering of terms. 1052 See compare/3 for this standard ordering. 1053 Note in particular that numbers are first ordered by their type (integer, 1054 float, etc) and only then by their magnitude, i.e. sorting numbers of 1055 different types may not give the expected result. 1056<P> 1057Note 1058 sort(L1,L2) is equivalent to sort(0,<,L1,L2). 1059 sort(L1,L2) differs from msort(L1,L2) in that it removes duplicates. 1060"), 1061 args:["List1" : "List.", "List2" : "List or variable."], 1062 eg:" 1063Success: 1064 sort([3,1,6,7,2],S). (gives S=[1,2,3,6,7]). 1065 sort([1,3,2,3,4,1],S). (gives S=[1,2,3,4]). 1066 sort([f(1,3),h(2,1)],S). (gives S=[f(1,3),h(2,1)]). 1067 sort([\"b\",2.0,a(1),1,a],S). 1068 (gives S=[2.0,1,\"b\",a,a(1)]). 1069Fail: 1070 sort([2,1,3,4],[2,1,3,4]). 1071 1072 1073 1074", 1075 see_also:[compare / 3, msort / 2, sort / 4, number_sort/2]]). 1076 1077:- comment(sort / 4, [ 1078 summary:"Succeeds if Sorted is the sorted list version of Random. The sort is done 1079according to the Key and Order specifications. 1080 1081", 1082 amode:(sort(+,+,+,-) is det), 1083 desc:html("<P>\ 1084 Generic sorting primitive: sorts the list Random according to the Key 1085 and Order specifications, and unifies Sorted with the result. The sort 1086 is stable, i.e. the order of elements with equal keys is preserved. 1087</P><P> 1088 The Key argument determines which part of the list elements is considered 1089 the sorting key. If Key is 0, then the entire term is taken as the 1090 sorting key (in this case, the list can contain anything, including 1091 numbers, atoms, strings, compound terms, and even variables). If Key 1092 is a positive integer (or a list of those), then the list elements will 1093 get ordered by their Keyth subterm (in this case, the list must contain 1094 compound terms with appropriate subterms). 1095</P><P> 1096 The Order argument specifies whether to use standard term order (@) or 1097 numeric order ($), whether the list is sorted into ascending (<, =<) 1098 or descending (>, >=) order, and whether duplicates are to be 1099 retained (=<, >=) or removed (<, >). The way to remember the Order 1100 argument is that it is the relation which holds between adjacent 1101 elements in the result. 1102<PRE> 1103 Order ordering direction duplicates 1104 --------------------------------------------------------------- 1105 @< (or <) standard ascending removed 1106 @=< (or =<) standard ascending retained 1107 @> (or >) standard descending removed 1108 @>= (or >=) standard descending retained 1109 1110 $< numeric ascending removed 1111 $=< numeric ascending retained 1112 $> numeric descending removed 1113 $>= numeric descending retained 1114</PRE> 1115 The alternative ordering criteria are: 1116 <DL> 1117 <DT>@ standard term order</DT><DD> 1118 The sort is done according to the standard ordering of terms. 1119 This can be applied to any term, see compare/3 for the definition. 1120 Note in particular that numbers are first ordered by their type 1121 (integer, float, etc) and only then by their magnitude, i.e. 1122 sorting numbers of different types may not give the expected result. 1123 </DD> 1124 <DT>$ numeric order</DT><DD> 1125 The sort is done according to numeric order. The sorting keys must 1126 all be numbers, but can be a mix of numeric types. They are compared 1127 in the way they are compared by the arithmetic comparisons (</2, <=/2, etc). 1128 Unlike standard order, this will consider numbers such as 3 and 3.0 1129 as equal, and -0.0 as equal to 0.0. 1130 </DD> 1131 </DL> 1132</P><P> 1133 The other sorting primitives may be defined in terms of sort/4 as follows: 1134<PRE> 1135 sort(Random, Sorted) :- sort(0, @<, Random, Sorted). 1136 msort(Random, Sorted) :- sort(0, @=<, Random, Sorted). 1137 keysort(Random, Sorted) :- sort(1, @=<, Random, Sorted). 1138 number_sort(Random, Sorted) :- sort(0, $=<, Random, Sorted). 1139</PRE> 1140 Sorting with _multiple_ keys can be done in one of two ways (see examples): 1141 <OL> 1142 <LI>First, sort according to the least important key. Sort the result 1143 by the next more important key, and so on. Thanks to the stability of 1144 sort/4, the ordering of the less important keys is preserved as required. 1145 </LI> 1146 <LI>For each list element, construct a compound key from the individual 1147 keys, and pair each new key with its list element. Sort the keyed list, 1148 then strip the auxiliary keys. 1149 </LI> 1150 </OL> 1151</P><P> 1152 The _algorithm_ used is natural merge sort. This implies a worst case 1153 complexity of N*ld(N), but many special cases will be sorted 1154 significantly faster. For instance, pre-sorted, reverse-sorted, and 1155 the concatenation of two sorted lists will all be sorted in linear time. 1156</P><P> 1157 NOTE regarding sorting bounded reals: While the standard ordering 1158 treats a bounded real as a compound term and orders them by lower 1159 bound and then upper bound, numerical ordering treats them as true 1160 intervals. As a consequence the order of overlapping intervals is 1161 undefined: 1.0__1.1 @< 1.0__1.2 while no numerical order is 1162 defined. In such cases an arithmetic exception is thrown. This can 1163 have unexpected consequences: care must be taken when sorting a 1164 list containing both rationals and bounded reals. While integers 1165 and floats are converted to zero-width intervals for the purposes 1166 of comparison, rationals are converted to small intervals 1167 guaranteed to contain the rational, e.g X is breal(1_1) gives 1168 X=0.99999999999999989__1.0000000000000002 and thus no order is 1169 defined between 1_1 and 1.0__1.0. 1170</P> 1171"), 1172 args:["Key" : "A non-negative integer, or a list of positive integers.", 1173 "Order" : "One of the atoms =<, >=, < or >, possibly prefixed with @ or $.", 1174 "Random" : "List.", "Sorted" : "List or variable."], 1175 exceptions:[ 1176 5 : "Key is greater than 0, and not all of Random's elements are compound terms.", 1177 5 : "Key is not an integer or a list of integers.", 1178 6 : "One of the compound terms in Random has not got as many as Key arguments.", 1179 20: "Random has elements whose numerical order is undefined."], 1180 eg:" 1181Success: 1182 sort(0, <, [], S). (gives S=[]). 1183 sort(0, <, [3,1,6,7,2], S). (gives S=[1,2,3,6,7]). 1184 sort(0, >, [q,1,3,a,e,N], S). (gives N=_g78,S=[q,e,a,3,1,_g78]). 1185 sort(0,=<, [1,3,2,3,4,1], S). (gives S=[1,1,2,3,3,4]). 1186 sort(2, <, [f(1,3),h(2,1)], S). (gives S=[h(2,1),f(1,3)]). 1187 sort(1, <, [f(1,3),h(2,1)], S). (gives S=[f(1,3),h(2,1)]). 1188 1189 sort([2,1],=<,[f(3,a(2)),f(1,a(1)),f(0,a(3)),f(1,a(4))],S). 1190 (gives S=[f(1,a(1)),f(3,a(2)),f(0,a(3)),f(1,a(4))]). 1191 1192 % standard vs numeric order 1193 sort(0, @<, [1,2,3,2.0,3], S). (gives S = [2.0, 1, 2, 3]) 1194 sort(0, $<, [1,2,3,2.0,3], S). (gives S = [1, 2, 3]) 1195 1196 sort(0,@=<, [1,2,3,2.0,3], S). (gives S = [2.0, 1, 2, 3, 3]) 1197 sort(0,$=<, [1,2,3,2.0,3], S). (gives S = [1, 2, 2.0, 3, 3]) 1198 1199 sort(0,@=<, [1,1.0,1_1], S). (gives S = [1.0, 1_1, 1]) 1200 sort(0,$=<, [1,1.0,1_1], S). (gives S = [1, 1.0, 1_1]) 1201 1202 sort(0, @<, [1,1.0,1_1], S). (gives S = [1.0, 1_1, 1]) 1203 sort(0, $<, [1,1.0,1_1], S). (gives S = [1]) 1204 sort(0, $<, [1.0,1,1_1], S). (gives S = [1.0]) 1205 sort(0, $<, [1_1,1.0,1], S). (gives S = [1_1]) 1206 1207 % Sort according to argument 3 (major) and 2 (minor) - method 1 1208 ?- S = [t(ok,a,2), t(good,b,1), t(best,a,1)], 1209 sort(2, =<, S, S2), % sort less important key first 1210 sort(3, =<, S2, S32). % sort more important key last 1211 1212 S2 = [t(ok,a,2), t(best,a,1), t(good,b,1)] 1213 S32 = [t(best,a,1), t(good,b,1), t(ok,a,2)] 1214 Yes (0.00s cpu) 1215 1216 % Sort according to argument 3 (major) and 2 (minor) - method 2 1217 ?- S = [t(ok,a,2), t(good,b,1), t(best,a,1)], 1218 ( foreach(T,S),foreach(K-T,KTs) do T=t(_,B,C), K=key(C,B) ), 1219 sort(1, =<, KTs, SKTs), % same as keysort(KTs, SKTs) 1220 ( foreach(_-T,SKTs), foreach(T,S32) do true ). 1221 1222 KTs = [key(2,a)-t(ok,a,2), key(1,b)-t(good,b,1), key(1,a)-t(best,a,1)] 1223 SKTs = [key(1,a)-t(best,a,1), key(1,b)-t(good,b,1), key(2,a)-t(ok,a,2)] 1224 S32 = [t(best,a,1), t(good,b,1), t(ok,a,2)] 1225 Yes (0.00s cpu) 1226 1227 1228Error: 1229 sort(0, <, [](5,3,7), S). (Error 5). 1230 sort(1, <, [f(1),f(3),5], S). (Error 5). 1231 sort(1, <, [f(1),f(3),5], S). (Error 5). 1232 sort(1.0, <, [f(1),f(3),f(5)], S). (Error 5). 1233 sort(2, <, [f(1,2),g(3,a),f(5)], S). (Error 6). 1234 sort(0, $<, [1,two,3], S). (Error 5). 1235 sort(0, $<, [1.0__1.1,1.0__1.1], S). (Error 20). 1236", 1237 see_also:[compare / 3, msort / 2, sort / 2, number_sort/2, keysort/2, array_sort/4]]). 1238 1239 1240:- comment(array_sort / 4, [ 1241 summary:"Succeeds if Sorted is the sorted version of Random. The sort is done 1242according to the Key and Order specifications.", 1243 amode:(array_sort(+,+,+,-) is det), 1244 desc:html("<P>\ 1245 Generic sorting primitive: sorts the array Random according to the Key 1246 and Order specifications, and unifies Sorted with the resulting array. 1247</P><P> 1248 This predicate is identical to sort/4, except that it sorts arrays 1249 instead of lists. See sort/4 for the details. 1250</P> 1251"), 1252 args:["Key" : "A non-negative integer, or a list of positive integers.", 1253 "Order" : "One of the atoms =<, >=, < or >, possibly prefixed with @ or $.", 1254 "Random" : "Array.", "Sorted" : "Array or variable."], 1255 exceptions:[ 1256 5 : "Key is greater than 0, and not all of Random's elements are compound terms.", 1257 5 : "Key is not an integer or a list of integers.", 1258 6 : "One of the compound terms in Random has not got as many as Key arguments.", 1259 20: "Random has elements whose numerical order is undefined."], 1260 eg:" 1261Success: 1262 array_sort(0, <, [], S). (gives S=[]). 1263 array_sort(0, <, [](3,1,6,7,2), S). (gives S=[](1,2,3,6,7)). 1264 array_sort(0, >, [](q,1,3,a,e,N), S). (gives N=_g78,S=[](q,e,a,3,1,_g78)). 1265 array_sort(0,=<, [](1,3,2,3,4,1), S). (gives S=[](1,1,2,3,3,4)). 1266 array_sort(2, <, [](f(1,3),h(2,1)), S). (gives S=[](h(2,1),f(1,3))). 1267 array_sort(1, <, [](f(1,3),h(2,1)), S). (gives S=[](f(1,3),h(2,1))). 1268 1269 array_sort([2,1], =<, [](f(3,a(2)),f(1,a(1)),f(0,a(3)),f(1,a(4))), S). 1270 (gives S=[](f(1,a(1)),f(3,a(2)),f(0,a(3)),f(1,a(4)))). 1271 1272 % standard vs numeric order 1273 array_sort(0, @<, [](1,2,3,2.0,3), S). (gives S = [](2.0, 1, 2, 3)) 1274 array_sort(0, $<, [](1,2,3,2.0,3), S). (gives S = [](1, 2, 3)) 1275 1276 array_sort(0,@=<, [](1,2,3,2.0,3), S). (gives S = [](2.0, 1, 2, 3, 3)) 1277 array_sort(0,$=<, [](1,2,3,2.0,3), S). (gives S = [](1, 2, 2.0, 3, 3)) 1278 1279 array_sort(0,@=<, [](1,1.0,1_1), S). (gives S = [](1.0, 1_1, 1)) 1280 array_sort(0,$=<, [](1,1.0,1_1), S). (gives S = [](1, 1.0, 1_1)) 1281 1282 array_sort(0, @<, [](1,1.0,1_1), S). (gives S = [](1.0, 1_1, 1)) 1283 array_sort(0, $<, [](1,1.0,1_1), S). (gives S = [](1)) 1284 array_sort(0, $<, [](1.0,1,1_1), S). (gives S = [](1.0)) 1285 array_sort(0, $<, [](1_1,1.0,1), S). (gives S = [](1_1)) 1286 1287 % Sort according to argument 3 (major) and 2 (minor) - method 1 1288 ?- S = [](t(ok,a,2), t(good,b,1), t(best,a,1)), 1289 array_sort(2, =<, S, S2), % sort less important key first 1290 array_sort(3, =<, S2, S32). % sort more important key last 1291 1292 S2 = [](t(ok,a,2), t(best,a,1), t(good,b,1)) 1293 S32 = [](t(best,a,1), t(good,b,1), t(ok,a,2)) 1294 Yes (0.00s cpu) 1295 1296 % Sort according to argument 3 (major) and 2 (minor) - method 2 1297 ?- S = [](t(ok,a,2), t(good,b,1), t(best,a,1)), 1298 ( foreach(T,S),foreach(K-T,KTs) do T=t(_,B,C), K=key(C,B) ), 1299 array_sort(1, =<, KTs, SKTs), % same as keysort(KTs, SKTs) 1300 ( foreach(_-T,SKTs), foreach(T,S32) do true ). 1301 1302 KTs = [](key(2,a)-t(ok,a,2), key(1,b)-t(good,b,1), key(1,a)-t(best,a,1)) 1303 SKTs = [](key(1,a)-t(best,a,1), key(1,b)-t(good,b,1), key(2,a)-t(ok,a,2)) 1304 S32 = [](t(best,a,1), t(good,b,1), t(ok,a,2)) 1305 Yes (0.00s cpu) 1306 1307 1308Error: 1309 array_sort(0, <, [5,6,2], S). (Error 5). 1310 array_sort(1, <, [](f(1),f(3),5), S). (Error 5). 1311 array_sort(1.0, <, [](f(1),f(3),f(5)), S). (Error 5). 1312 array_sort(2, <, [](f(1,2),g(3,a),f(5)), S). (Error 6). 1313 array_sort(0, $<, [](1,two,3), S). (Error 5). 1314 array_sort(0, $<, [](1.0__1.1,1.0__1.1), S). (Error 20). 1315", 1316 see_also:[compare/3, sort/4]]). 1317 1318 1319:- comment(term_hash / 4, [ 1320 summary:"Computes a hash value for an arbitrary term", 1321 amode:(term_hash(?,+,+,-) is det), 1322 args:[ 1323 "Term":"An arbitrary term", 1324 "Depth":"An integer", 1325 "Range":"An integer", 1326 "Hash":"A variable or an integer" 1327 ], 1328 desc:html("\ 1329 This predicate attempts to computes a hash value for an arbitrary term. 1330 The computed hash value lies between 0 and Range-1. 1331<P> 1332 The Depth argument specifies the nesting depth of the term up to 1333 which the term's components are taken into account for the 1334 computation of the hash value. More deeply nested parts of the 1335 term will be ignored. If the term contains uninstantiated parts in 1336 the portion up to Depth, no reliable hash value can be computed 1337 and the predicate succeeds, leaving Hash uninstantiated. If Depth 1338 is set to -1, the whole depth of the term will be used for computing 1339 the hash value. If Depth is set to 0, the hash value will be 0. 1340 The main functor of a term is taken to be at depth 1, its arguments 1341 at depth 2 etc. 1342"), 1343 exceptions:[ 1344 4:"Depth or Range are not instantiated", 1345 5:"Depth or Range are not integers"], 1346 eg:" 1347Success: 1348 [eclipse 1]: term_hash(hello, 1, 100, H). 1349 H = 4 1350 yes. 1351 1352 [eclipse 2]: term_hash(world, 1, 100, H). 1353 H = 84 1354 yes. 1355 1356 [eclipse 15]: term_hash(foo(bar,3,4.5), -1, 100, H). 1357 H = 40 1358 yes. 1359 1360 [eclipse 15]: term_hash(foo(bar,3,4.5), 1, 100, H). 1361 H = 72 1362 yes. 1363 1364 [eclipse 18]: term_hash(foo(X,3,4.5), 1, 100, H). 1365 X = X 1366 H = 72 1367 yes. 1368 1369 [eclipse 19]: term_hash(foo(X,3,4.5), 2, 100, H). 1370 X = X 1371 H = H 1372 yes. 1373", 1374 see_also:[hash:hash_create/1, dim/2]]). 1375 1376 1377 1378:- comment(domain / 1, [ 1379 summary:"Define a domain (a set of symbols mapped to natural numbers)", 1380 template:["local domain(++Def)", "export domain(++Def)"], 1381 amode:(domain(++) is det), 1382 desc:html("<P> 1383 This defines a domain. A domain definition is a ground structure 1384 with atomic arguments. The structure's functor name is taken as 1385 the name of the domain. The domain name is used e.g. for declaring 1386 domain variables in lib(ic_symbolic). 1387 </P><P> 1388 The structure's arguments are the domain values. A domain value 1389 can be any atomic term (atom, string, number), but will usually 1390 be an atom. Domains are ordered, and the argument order in the 1391 defining structure implies the order of the domain values. 1392 The domain values are mapped to natural numbers, with the first 1393 argument being mapped to 1, the second to 2 and so on. 1394 </P><P> 1395 After having been defined, the mapping can be looked up via the 1396 primitives domain_index/3 and current_domain/3. Certain libraries 1397 (e.g. lib(ic_symbolic)) use the defined mapping internally. 1398 </P><P> 1399 Domain definitions can be local or exported. The domain values of 1400 all visible domain definitions within a module must be mutually 1401 exclusive, i.e. there must not be any ambiguity as to which domain 1402 a particular value belongs to. The system checks this condition 1403 whenever new domains are defined or imported. 1404 </P>"), 1405 args:["Def" : "A structure with atomic arguments."], 1406 exceptions:[ 1407 4 : "Def is not ground", 1408 5 : "Def is neither variable nor structure", 1409 5 : "A domain value is not atomic", 1410 6 : "A domain value is not unique in this module", 1411 87 : "The domain name is already used locally", 1412 88 : "The domain name is already used and exported", 1413 89 : "The domain name is already used by an imported domain" 1414 ], 1415 eg:" 1416 :- local domain(colour(red,green,blue)). 1417 1418 :- export domain(vowel(a,e,i,o,u)). 1419 1420 :- local domain(abc(a,b,c)). 1421 Domain value a not unique in module eclipse 1422 out of range in local domain(abc(a, b, c)) 1423 Abort 1424 1425 ?- current_domain(Name, DefModule, Def). 1426 Name = colour 1427 DefModule = eclipse 1428 Def = colour(red, green, blue) 1429 More (0.00s cpu) ? ; 1430 1431 Name = vowel 1432 DefModule = eclipse 1433 Def = vowel(a, e, i, o, u) 1434 More (0.00s cpu) ? ; 1435 1436 No (0.00s cpu) 1437 1438 ?- domain_index(blue, Domain, Index). 1439 Domain = eclipse : colour 1440 Index = 3 1441 Yes (0.00s cpu) 1442 1443 ?- domain_index(o, Domain, Index). 1444 Domain = eclipse : vowel 1445 Index = 4 1446 Yes (0.00s cpu) 1447 1448 ?- domain_index(yellow, Domain, Index). 1449 No (0.00s cpu) 1450", 1451 see_also:[(local)/1, (export)/1, current_domain/3, domain_index/3, library(ic_symbolic)]]). 1452 1453 1454:- comment(current_domain/3, [ 1455 summary:"Name is the name of a visible domain, defined by DomainDef in DefModule", 1456 amode:(current_domain(+,-,-) is semidet), 1457 amode:(current_domain(-,-,-) is nondet), 1458 args:["Name":"Atom or variable", 1459 "DefModule":"Variable or atom (module)", 1460 "DomainDef":"Usually variable, will be bound to a ground structure"], 1461 see_also:[(domain)/1, domain_index/3], 1462 fail_if:"No visible domain name unifies with Name", 1463 eg:" 1464 :- local domain(colour(red,green,blue)). 1465 1466 :- export domain(vowel(a,e,i,o,u)). 1467 1468 :- local domain(abc(a,b,c)). 1469 Domain value a not unique in module eclipse 1470 out of range in local domain(abc(a, b, c)) 1471 Abort 1472 1473 ?- current_domain(Name, DefModule, Def). 1474 Name = colour 1475 DefModule = eclipse 1476 Def = colour(red, green, blue) 1477 More (0.00s cpu) ? ; 1478 1479 Name = vowel 1480 DefModule = eclipse 1481 Def = vowel(a, e, i, o, u) 1482 More (0.00s cpu) ? ; 1483 1484 No (0.00s cpu) 1485 1486 ?- current_domain(vowel, DefModule, Def). 1487 Name = vowel 1488 DefModule = eclipse 1489 Def = vowel(a, e, i, o, u) 1490 Yes (0.00s cpu) 1491 1492 ?- current_domain(abc, DefModule, Def). 1493 No (0.00s cpu) 1494 ", 1495 desc:html("<P> 1496 Used to look up a domain definition, or to enumerate all domain 1497 definitions visible in the caller module. Visible domain definitions 1498 are those which have been either declared locally, or exported, 1499 or which have been imported or reexported from another module. 1500 </P><P> 1501 DefModule is the module where the domain was declared local or 1502 exported. DomainDef is the structure which was specified in the 1503 original domain definition. 1504 </P> 1505")]). 1506 1507 1508:- comment(domain_index/3, [ 1509 summary:"Value is defined in Domain with positional number Index", 1510 amode:(domain_index(+,-,-) is semidet), 1511 args:["Value":"Atomic term", 1512 "Domain":"Variable or structure of the form Module:DomainName", 1513 "Index":"Variable or integer starting from 1"], 1514 see_also:[(domain)/1, current_domain/3], 1515 fail_if:"The value does not occur in any of the visible domain definitions", 1516 exceptions:[ 1517 4:"Value is not instantiated", 1518 5:"Value is not atomic" 1519 ], 1520 eg:" 1521 :- local domain(colour(red,green,blue)). 1522 1523 :- export domain(vowel(a,e,i,o,u)). 1524 1525 :- local domain(abc(a,b,c)). 1526 Domain value a not unique in module eclipse 1527 out of range in local domain(abc(a, b, c)) 1528 Abort 1529 1530 ?- domain_index(green, Domain, Index). 1531 Domain = eclipse : colour 1532 Index = 2 1533 Yes (0.00s cpu) 1534 1535 ?- domain_index(a, Domain, Index). 1536 Domain = eclipse : vowel 1537 Index = 1 1538 Yes (0.00s cpu) 1539 1540 ?- domain_index(b, Domain, Index). 1541 No (0.00s cpu) 1542 1543 ?- domain_index(yellow, Domain, Index). 1544 No (0.00s cpu) 1545 ", 1546 desc:html("<P> 1547 Used to look up which domain a particular value belongs to, and 1548 which numerical index it has within this domain. Only domain definitions 1549 which are visible in the caller module are taken into account. 1550 </P><P> 1551 Domain is returned as a pair DefinitionModule:DomainName which 1552 unabiguously identifies the domain definition that contains the value. 1553 Index is unified with a natural number corresponding to the position 1554 of Value within that domain definition (starting from 1). 1555 </P> 1556")]). 1557 1558