home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / lifeos2.zip / LIFE-1.02 / LIB / SETS.LF < prev    next >
Text File  |  1996-06-04  |  22KB  |  838 lines
  1. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  2. %    $Id: sets.lf,v 1.2 1994/12/09 00:20:02 duchier Exp $    
  3. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  4. %
  5. % Set manipulation
  6. %
  7. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  8. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  9.  
  10. module("sets") ?
  11.  
  12. add_man(sets,
  13.      "module(""sets"").
  14.  
  15.       This module contains a number of utilities for set manipulation.
  16.  
  17.       The names of the procedures and functions have two parts separated by 
  18.       underscore: 
  19.  
  20.       the suffix describes the functionality:
  21.         member, 
  22.         union,intersect,difference, 
  23.         part,member_and_rest,
  24.         remove,insert,
  25.         make_set
  26.  
  27.       The prefix describes the kind of test used to test for identity of two
  28.       elements: 
  29.           gen: the procedure is generic, and the method must be given as an  
  30.                argument; 
  31.           sort: :== is used to test identity;
  32.           ad  : === is used to test identity.
  33.  
  34.       Sets are implemented as lists with no redundant element (according to the
  35.       identity test).
  36.  
  37.       See also: pick.")?
  38.  
  39. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  40. %%%
  41. %%% generic operations on sets; the method feature describes the function used
  42. %%% to method for equality.
  43. %%%
  44. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  45.  
  46. add_man(gen_member,
  47.      " gen_member(Elt,Set,test => Test) -> Res
  48.  
  49.        input: Elt: any psi term. 
  50.               Set: a set of terms.
  51.               Test: the test used for checking membership. Must be a boolean 
  52.                     function of two arguments
  53.  
  54.        output: Res: a boolean.
  55.  
  56.        Tests if Elt belongs to set, using Test.")?
  57.  
  58.  
  59. public(gen_member) ? 
  60. gen_member(A,[B|C],test => Comp) ->
  61.     cond( Comp(A,B),
  62.           true,
  63.           gen_member(A,C,test => Comp)
  64.         ).
  65. gen_member(_,[]) -> false.
  66.  
  67.  
  68. %%% union: merging two sets
  69.  
  70.  
  71. add_man(gen_union,
  72.      " gen_union(Set1,Set2,test => Test) -> Set3
  73.  
  74.        input: Set1 and Set2: sets. 
  75.               Test: the test used for checking equality between members of the
  76.                     two sets. Must be a boolean function of two arguments
  77.  
  78.        output: Set3: a set.
  79.  
  80.        Set3 is Set1 union Set2")?
  81.        
  82. public(gen_union) ?
  83. gen_union([],L) -> L. 
  84. gen_union([A|B],C,test => Comp) -> 
  85.     cond( gen_member(A,C,test => Comp),
  86.           gen_union(B,C,test => Comp),
  87.           [A|gen_union(B,C,test => Comp)]).
  88.  
  89. %%% make_set: get rid of redundant elements of a set
  90.  
  91.  
  92. add_man(gen_make_set,
  93.      " gen_make_set(List,test => Test) -> Set
  94.  
  95.        input: List: list;
  96.               Test: the test used for checking equality between members of the
  97.                     set. Must be a boolean function of two arguments
  98.  
  99.        output: Set: a set.
  100.  
  101.        Set is list with no redundant element.")?
  102.  
  103. public(gen_make_set) ?
  104. gen_make_set([]) -> [].
  105. gen_make_set([A|B],test => Comp) -> 
  106.     cond( gen_member(A,B,test => Comp),
  107.           gen_make_set(B,test => Comp),
  108.           [A|gen_make_set(B,test => Comp)]).
  109.  
  110. %%% intersect: returns the intersection of two sets
  111.  
  112. add_man(gen_intersect,
  113.      " gen_intersect(Set1,Set2,test => Test) -> Set3
  114.  
  115.        input: Set1 and Set2: sets. 
  116.               Test: the test used for checking equality between members of the
  117.                     two sets. Must be a boolean function of two arguments
  118.  
  119.        output: Set3: a set.
  120.  
  121.        Set3 is the intersection of the two sets Set1 and Set2")? 
  122.  
  123. public(gen_intersect) ?
  124. gen_intersect([]) -> [].
  125. gen_intersect([A|B],C,test =>  Comp) ->
  126.     cond( gen_member(A,C,test => Comp),
  127.           [A| gen_intersect(B,C,test => Comp)],
  128.           gen_intersect(B,C,test => Comp)).
  129.  
  130. %%%
  131. %%% gen_difference(L1,L2) returns L1 \ (L1 inter L2)
  132. %%%
  133.  
  134. add_man(gen_difference,
  135.      " gen_difference(Set1,Set2,test => Test) -> Set3
  136.  
  137.        input: Set1 and Set2: sets. 
  138.               Test: the test used for checking equality between members of the
  139.                     two sets. Must be a boolean function of two arguments
  140.  
  141.        output: Set3: a set.
  142.  
  143.        Set3 is  Set1 - (Set1 inter Set2)")?
  144.  
  145. public(gen_difference) ?
  146. gen_difference(L1,[]) -> L1.
  147. gen_difference(L1,L2:[A|NewL2],test => Comp) ->
  148.     cond( gen_member_and_rest(A,L1,InterRestL1,test => Comp),
  149.           gen_difference(InterRestL1,NewL2,test => Comp),
  150.           gen_difference(L1,NewL2,test => Comp)).
  151.  
  152. %%%
  153. %%% gen_member_and_rest(A,Set,Rest) returns true if A is a member of Set,
  154. %%% with  Rest containing the other members of Set.  
  155. %%%
  156.  
  157. add_man(gen_member_and_rest,
  158.      " gen_member_and_rest(Elt,Set1,Rest,test => Test) -> Bool
  159.  
  160.        input: Set1,Rest: sets.
  161.               Elt: any psi term.
  162.               Test: the test used for checking equality between Elt and the
  163.                     members of Set1.
  164.                     Must be a boolean function of two arguments.
  165.  
  166.        output: Rest: a set.
  167.                Bool: a boolean.
  168.  
  169.        Bool is true if Elt belongs to Set1, false otherwise. If Bool is true, 
  170.        Rest is bound to a set containing the elements of Set1 minus the
  171.        recognised occurrence of Elt.")? 
  172.  
  173. public(gen_member_and_rest) ?
  174. gen_member_and_rest(_,[]) -> false.
  175. gen_member_and_rest(A,[B|C],Rest,test => Comp) ->
  176.     cond( Comp(A,B),
  177.           ( true | Rest = C),
  178.           gen_member_and_rest(A,C,OtherRest,test => Comp) |
  179.           Rest = [B|OtherRest] ).
  180.  
  181.  
  182. add_man(gen_remove,
  183.      " gen_remove(Elt,Set,test => Test) -> Set2
  184.  
  185.        input: Elt: any psi term. 
  186.               Set: a set of terms.
  187.               Test: the test used for checking membership. Must be a boolean 
  188.                     function of two arguments
  189.  
  190.        output: Set2: a set.
  191.  
  192.        Set2 is Set1 with no occurrence of Elt")?
  193.  
  194.  
  195. public(gen_remove) ? 
  196. gen_remove(A,[B|C],test => Comp) ->
  197.     cond( Comp(A,B),
  198.           C,
  199.           [B|gen_remove(A,C,test => Comp)]
  200.         ).
  201. gen_remove(_,[]) -> [].
  202.  
  203.  
  204. add_man(gen_remove_all,
  205.      " gen_remove_all(Elt,Set,test => Test) -> Set2
  206.  
  207.        input: Elt: any psi term. 
  208.               Set: a set of terms.
  209.               Test: Any test (boolean function of two arguments)
  210.  
  211.        output: Set2: a set.
  212.  
  213.        Set2 is Set1 with no elt Elt2  such that Test(Elt,Elt2) is true")?
  214.  
  215.  
  216. public(gen_remove_all) ? 
  217. gen_remove_all(A,[B|C],test => Comp) ->
  218.     cond( Comp(A,B),
  219.           gen_remove_all(A,C,test => Comp),
  220.           [B|gen_remove_all(A,C,test => Comp)]
  221.         ).
  222. gen_remove_all(_,[]) -> [].
  223.  
  224.  
  225. add_man(gen_insert,
  226.      " gen_insert(Elt,Set,test => Test) -> Set2
  227.  
  228.        input: Elt: any psi term. 
  229.               Set: a set of terms.
  230.               Test: the test used for checking membership. Must be a boolean 
  231.                     function of two arguments
  232.  
  233.        output: Set2: a set.
  234.  
  235.        Elt is added to Set to form Set2 if it was not present in Set.")?
  236.  
  237. public(gen_insert) ?
  238. gen_insert(Elt,Set,test => Test) -> cond( gen_member(Elt,Set,test => Test),
  239.                       Set,
  240.                       [Elt|Set]).
  241.  
  242. add_man(gen_order_included,
  243.      " gen_order_included(Set1,Set2,test => Test) -> Res
  244.  
  245.        input: Set1,Set2: sets. 
  246.               Test: the test used for checking membership. Must be a boolean 
  247.                     function of two arguments
  248.  
  249.        output: Res: result
  250.  
  251.        Res is true(true) if Set1 is strictly included in Set2,
  252.               true       if Set1 has the exactly the same elements as Set2,
  253.               false otherwise.
  254.  
  255.        Set1 and Set2 are supposed to be ordered in the same way.")?
  256.  
  257. public(gen_order_included) ?
  258.  
  259. gen_order_included( [],[]) -> true.
  260. gen_order_included( [],X) -> true(true).
  261. gen_order_included( L1:[A|B],[C|D],test => Comp) -> 
  262.     cond( Comp(A,C),
  263.           gen_order_included(B,D,test => Comp),
  264.               gen_order_included(L1,D,test => Comp) & @(true)).
  265. gen_order_included(X,[]) -> false.
  266.  
  267.  
  268. add_man(gen_included,
  269.      " gen_included(Set1,Set2,test => Test) -> Res
  270.  
  271.        input: Set1,Set2: sets. 
  272.               Test: the test used for checking membership. Must be a boolean 
  273.                     function of two arguments
  274.  
  275.        output: Res: result
  276.  
  277.        Res is true(true) if Set1 is strictly included in Set2,
  278.               true       if Set1 has the exactly the same elements as Set2,
  279.               false otherwise.")?
  280.  
  281. public(gen_included) ?
  282.  
  283. gen_included( [],[]) -> true.
  284. gen_included( [],X) -> true(true).
  285. gen_included( [A|B],L,test => Comp) -> 
  286.     cond( gen_member_and_rest(A,L,L1,test => Comp),
  287.           gen_included(B,L1,test => Comp),
  288.           false).
  289.  
  290.  
  291.  
  292. add_man(gen_part,
  293.     " gen_part(Set1,Set2,Inter,Rest1,Rest2,test => Test)
  294.  
  295.           input: Set1,Set2: sets;
  296.                  Test: the test used for checking membership. Must be a boolean 
  297.                        function of two arguments.
  298.           output: Inter,Rest1,Rest2: sets
  299.  
  300.           Inter is the intersection of Set1 and Set2;
  301.           Rest1 is Set1 \ Inter.
  302.           Rest2 is Set2 \ Inter.")?
  303.  
  304. public(gen_part) ?
  305. gen_part([],L2,[],[],L2) :- !.
  306. gen_part(L1:[A|NewL1],L2,Intersect,RestL1,RestL2,test => Comp) :-
  307.     cond( gen_member_and_rest(A,L2,InterRestL2,test => Comp),
  308.           (
  309.           gen_part(NewL1,InterRestL2,Intersect2,RestL1,RestL2,
  310.                test => Comp),
  311.           Intersect = [A|Intersect2]
  312.           ),
  313.           (
  314.           gen_part(NewL1,L2,Intersect,RestNewL1,RestL2,test => Comp),
  315.           RestL1 = [A|RestNewL1]
  316.           )).
  317.  
  318. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  319. %%%
  320. %%% operations on sets; :== is the function used to test for equality.
  321. %%%
  322. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  323.  
  324. add_man(sort_member,
  325.      " sort_member(Elt,Set) -> Res
  326.  
  327.        input: Elt: any psi term. 
  328.               Set: a set of terms.
  329.  
  330.        output: Res: a boolean.
  331.  
  332.        Tests if Elt belongs to set, using :==.")?
  333.  
  334.  
  335. public(sort_member) ? 
  336. sort_member(A,[B|C]) ->
  337.     cond( A :== B,
  338.           true,
  339.           sort_member(A,C)
  340.         ).
  341. sort_member(_,[]) -> false.
  342.  
  343.  
  344. %%% union: merging two sets
  345.  
  346.  
  347. add_man(sort_union,
  348.      " sort_union(Set1,Set2) -> Set3
  349.  
  350.        input: Set1 and Set2: sets. 
  351.  
  352.        output: Set3: a set.
  353.  
  354.        Set3 is Set1 union Set2.
  355.        The test that checks the identity of two elements is :== .")?
  356.        
  357. public(sort_union) ?
  358. sort_union([],L) -> L. 
  359. sort_union([A|B],C) -> 
  360.     cond( sort_member(A,C),
  361.           sort_union(B,C),
  362.           [A|sort_union(B,C)]).
  363.  
  364. %%% make_set: get rid of redundant elements of a set
  365.  
  366.  
  367. add_man(sort_make_set,
  368.      " sort_make_set(Set1) -> Set2
  369.  
  370.        input: Set1: sets. 
  371.  
  372.        output: Set2: a set.
  373.  
  374.        Gets rid of redundant elements in Set1.
  375.        The test that checks the identity of two elements is :== .")?
  376.  
  377. public(sort_make_set) ?
  378. sort_make_set([]) -> [].
  379. sort_make_set([A|B]) -> 
  380.     cond( sort_member(A,B),
  381.           sort_make_set(B),
  382.           [A|sort_make_set(B)]).
  383.  
  384. %%% intersect: returns the intersection of two sets
  385.  
  386. add_man(sort_intersect,
  387.      " sort_intersect(Set1,Set2) -> Set3
  388.  
  389.        input: Set1 and Set2: sets. 
  390.  
  391.        output: Set3: a set.
  392.  
  393.        Set3 is the intersection of the two sets Set1 and Set2.
  394.        The test that checks the identity of two elements is :== .")? 
  395.  
  396. public(sort_intersect) ?
  397. sort_intersect([]) -> [].
  398. sort_intersect([A|B],C) ->
  399.     cond( sort_member(A,C),
  400.           [A| sort_intersect(B,C)],
  401.           sort_intersect(B,C)).
  402.  
  403. %%%
  404. %%% sort_difference(L1,L2) returns L1 \ (L1 inter L2)
  405. %%%
  406.  
  407. add_man(sort_difference,
  408.      " sort_difference(Set1,Set2) -> Set3
  409.  
  410.        input: Set1 and Set2: sets. 
  411.  
  412.        output: Set3: a set.
  413.  
  414.        Set3 is  Set1 - (Set1 inter Set2).
  415.        The test that checks the identity of two elements is :== .")?
  416.  
  417. public(sort_difference) ?
  418. sort_difference(L1,[]) -> L1.
  419. sort_difference(L1,L2:[A|NewL2]) ->
  420.     cond( sort_member_and_rest(A,L1,InterRestL1),
  421.           sort_difference(InterRestL1,NewL2),
  422.           sort_difference(L1,NewL2)).
  423.  
  424. %%%
  425. %%% sort_member_and_rest(A,Set,Rest) returns true if A is a member of Set,
  426. %%% with  Rest containing the other members of Set.  
  427. %%%
  428.  
  429. add_man(sort_member_and_rest,
  430.      " sort_member_and_rest(Elt,Set1,Rest) -> Bool
  431.  
  432.        input: Set1,Rest: sets.
  433.               Elt: any psi term.
  434.  
  435.        output: Rest: a set.
  436.                Bool: a boolean.
  437.  
  438.        Bool is true if Elt belongs to Set1, false otherwise. If Bool is true, 
  439.        Rest is bound to a set containing the elements of Set1 minus the
  440.        recognised occurrence of Elt.
  441.        The test that checks the identity of two elements is :== .")? 
  442.  
  443. public(sort_member_and_rest) ?
  444. sort_member_and_rest(_,[]) -> false.
  445. sort_member_and_rest(A,[B|C],Rest) ->
  446.     cond( A :== B,
  447.           ( true | Rest = C),
  448.           sort_member_and_rest(A,C,OtherRest) | Rest = [B|OtherRest] ).
  449.  
  450.  
  451. add_man(sort_remove,
  452.      " sort_remove(Elt,Set) -> Set2
  453.  
  454.        input: Elt: any psi term. 
  455.               Set: a set of terms.
  456.  
  457.        output: Set2: a set.
  458.  
  459.        Set2 is Set1 with no occurrence of Elt.
  460.        The test that checks the identity of two elements is :== .")?
  461.  
  462.  
  463. public(sort_remove) ? 
  464. sort_remove(A,[B|C]) ->
  465.     cond( A :== B,
  466.           C,
  467.           [B|sort_remove(A,C)]
  468.         ).
  469. sort_remove(_,[]) -> [].
  470.  
  471.  
  472. add_man(sort_insert,
  473.      " sort_insert(Elt,Set) -> Set2
  474.  
  475.        input: Elt: any psi term. 
  476.               Set: a set of terms.
  477.        output: Set2: a set.
  478.  
  479.        Elt is added to Set to form Set2 if no element of the same sort was
  480.        present in Set.
  481.        The test that checks the identity of two elements is :== .")? 
  482.  
  483. public(sort_insert) ?
  484. sort_insert(Elt,Set) -> cond( sort_member(Elt,Set),
  485.                       Set,
  486.                       [Elt|Set]).
  487.  
  488.  
  489.  
  490. add_man(sort_order_included,
  491.      " sort_order_included(Set1,Set2) -> Res
  492.  
  493.        input: Set1,Set2: sets. 
  494.  
  495.        output: Res: result
  496.  
  497.        Res is true(true) if Set1 is strictly included in Set2,
  498.               true       if Set1 has the exactly the same elements as Set2,
  499.               false otherwise.
  500.  
  501.        Set1 and Set2 are supposed to be ordered in the same way.
  502.        The test that checks the identity of two elements is :== .")?
  503.  
  504. public(sort_order_included) ?
  505.  
  506. sort_order_included( [],[]) -> true.
  507. sort_order_included( [],X) -> true(true).
  508. sort_order_included( L1:[A|B],[C|D]) -> 
  509.     cond( A :== C,
  510.           sort_order_included(B,D),
  511.               sort_order_included(L1,D) & @(true)).
  512. sort_order_included(X,[]) -> false.
  513.  
  514.  
  515. add_man(sort_included,
  516.      " sort_included(Set1,Set2) -> Res
  517.  
  518.        input: Set1,Set2: sets. 
  519.  
  520.        output: Res: result
  521.  
  522.        Res is true(true) if Set1 is strictly included in Set2,
  523.               true       if Set1 has the exactly the same elements as Set2,
  524.               false otherwise.
  525.        The test that checks the identity of two elements is :== .")?
  526.  
  527. public(sort_included) ?
  528.  
  529. sort_included( [],[]) -> true.
  530. sort_included( [],X) -> true(true).
  531. sort_included( [A|B],L) -> 
  532.     cond( sort_member_and_rest(A,L,L1),
  533.           sort_included(B,L1),
  534.           false).
  535.  
  536.  
  537.  
  538. add_man(sort_part,
  539.     " sort_part(Set1,Set2,Inter,Rest1,Rest2)
  540.  
  541.           input: Set1,Set2: sets;
  542.  
  543.           output: Inter,Rest1,Rest2: sets
  544.  
  545.           Inter is the intersection of Set1 and Set2;
  546.           Rest1 is Set1 \ Inter.
  547.           Rest2 is Set2 \ Inter.
  548.           The test that checks the identity of two elements is :== .")?
  549.  
  550. public(sort_part) ?
  551. sort_part([],L2,[],[],L2) :- !.
  552. sort_part(L1:[A|NewL1],L2,Intersect,RestL1,RestL2) :-
  553.     cond( sort_member_and_rest(A,L2,InterRestL2),
  554.           (
  555.           sort_part(NewL1,InterRestL2,Intersect2,RestL1,RestL2),
  556.           Intersect = [A|Intersect2]
  557.           ),
  558.           (
  559.           sort_part(NewL1,L2,Intersect,RestNewL1,RestL2),
  560.           RestL1 = [A|RestNewL1]
  561.           )).
  562.  
  563.  
  564. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  565. %%%
  566. %%% operations on sets; === is the function used to test for equality.
  567. %%%
  568. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  569.  
  570. add_man(ad_member,
  571.      " ad_member(Elt,Set) -> Res
  572.  
  573.        input: Elt: any psi term. 
  574.               Set: a set of terms.
  575.  
  576.        output: Res: a boolean.
  577.  
  578.        Tests if Elt belongs to set, using ===.")?
  579.  
  580.  
  581. public(ad_member) ? 
  582. ad_member(A,[B|C]) ->
  583.     cond( A === B,
  584.           true,
  585.           ad_member(A,C)
  586.         ).
  587. ad_member(_,[]) -> false.
  588.  
  589.  
  590. %%% union: merging two sets
  591.  
  592.  
  593. add_man(ad_union,
  594.      " ad_union(Set1,Set2) -> Set3
  595.  
  596.        input: Set1 and Set2: sets. 
  597.  
  598.        output: Set3: a set.
  599.  
  600.        Set3 is Set1 union Set2.
  601.        The test that checks the identity of two elements is === .")?
  602.        
  603. public(ad_union) ?
  604. ad_union([],L) -> L. 
  605. ad_union([A|B],C) -> 
  606.     cond( ad_member(A,C),
  607.           ad_union(B,C),
  608.           [A|ad_union(B,C)]).
  609.  
  610. %%% make_set: get rid of redundant elements of a set
  611.  
  612.  
  613. add_man(ad_make_set,
  614.      " ad_make_set(Set1) -> Set2
  615.  
  616.        input: Set1: sets. 
  617.  
  618.        output: Set2: a set.
  619.  
  620.        Gets rid of redundant elements in Set1.
  621.        The test that checks the identity of two elements is === .")?
  622.  
  623. public(ad_make_set) ?
  624. ad_make_set([]) -> [].
  625. ad_make_set([A|B]) -> 
  626.     cond( ad_member(A,B),
  627.           ad_make_set(B),
  628.           [A|ad_make_set(B)]).
  629.  
  630. %%% intersect: returns the intersection of two sets
  631.  
  632. add_man(ad_intersect,
  633.      " ad_intersect(Set1,Set2) -> Set3
  634.  
  635.        input: Set1 and Set2: sets. 
  636.  
  637.        output: Set3: a set.
  638.  
  639.        Set3 is the intersection of the two sets Set1 and Set2.
  640.        The test that checks the identity of two elements is === .")? 
  641.  
  642. public(ad_intersect) ?
  643. ad_intersect([]) -> [].
  644. ad_intersect([A|B],C) ->
  645.     cond( ad_member(A,C),
  646.           [A| ad_intersect(B,C)],
  647.           ad_intersect(B,C)).
  648.  
  649. %%%
  650. %%% ad_difference(L1,L2) returns L2 \ (L1 inter L2)
  651. %%%
  652.  
  653. add_man(ad_difference,
  654.      " ad_difference(Set1,Set2) -> Set3
  655.  
  656.        input: Set1 and Set2: sets. 
  657.  
  658.        output: Set3: a set.
  659.  
  660.        Set3 is  Set1 - (Set1 inter Set2).
  661.        The test that checks the identity of two elements is === .")?
  662.  
  663. public(ad_difference) ?
  664. ad_difference(L1,[]) -> L1.
  665. ad_difference(L1,L2:[A|NewL2]) ->
  666.     cond( ad_member_and_rest(A,L1,InterRestL1),
  667.           ad_difference(InterRestL1,NewL2),
  668.           ad_difference(L1,NewL2)).
  669.  
  670. %%%
  671. %%% ad_member_and_rest(A,Set,Rest) returns true if A is a member of Set,
  672. %%% with  Rest containing the other members of Set.  
  673. %%%
  674.  
  675. add_man(ad_member_and_rest,
  676.      " ad_member_and_rest(Elt,Set1,Rest) -> Bool
  677.  
  678.        input: Set1,Rest: sets.
  679.               Elt: any psi term.
  680.  
  681.        output: Rest: a set.
  682.                Bool: a boolean.
  683.  
  684.        Bool is true if Elt belongs to Set1, false otherwise. If Bool is true, 
  685.        Rest is bound to a set containing the elements of Set1 minus the
  686.        recognised occurrence of Elt.
  687.        The test that checks the identity of two elements is === .")? 
  688.  
  689. public(ad_member_and_rest) ?
  690. ad_member_and_rest(_,[]) -> false.
  691. ad_member_and_rest(A,[B|C],Rest) ->
  692.     cond( A === B,
  693.           ( true | Rest = C),
  694.           ad_member_and_rest(A,C,OtherRest) | Rest = [B|OtherRest] ).
  695.  
  696.  
  697. add_man(ad_remove,
  698.      " ad_remove(Elt,Set) -> Set2
  699.  
  700.        input: Elt: any psi term. 
  701.               Set: a set of terms.
  702.  
  703.        output: Set2: a set.
  704.  
  705.        Set2 is Set1 with no occurrence of Elt.
  706.        The test that checks the identity of two elements is === .")?
  707.  
  708.  
  709. public(ad_remove) ? 
  710. ad_remove(A,[B|C]) ->
  711.     cond( A === B,
  712.           C,
  713.           [B|ad_remove(A,C)]
  714.         ).
  715. ad_remove(_,[]) -> [].
  716.  
  717.  
  718.  
  719. add_man(ad_insert,
  720.      " ad_insert(Elt,Set) -> Set2
  721.  
  722.        input: Elt: any psi term. 
  723.               Set: a set of terms.
  724.        output: Set2: a set.
  725.  
  726.        Elt is added to Set to form Set2 if it was not already present in
  727.        Set.
  728.        The test that checks the identity of two elements is === .")?  
  729.  
  730. public(ad_insert) ?
  731. ad_insert(Elt,Set) -> cond( ad_member(Elt,Set),
  732.                 Set,
  733.                 [Elt|Set]).
  734.  
  735.  
  736. add_man(ad_order_included,
  737.      " ad_order_included(Set1,Set2) -> Res
  738.  
  739.        input: Set1,Set2: sets. 
  740.  
  741.        output: Res: result
  742.  
  743.        Res is true(true) if Set1 is strictly included in Set2,
  744.               true       if Set1 has the exactly the same elements as Set2,
  745.               false otherwise.
  746.  
  747.        Set1 and Set2 are supposed to be ordered in the same way.
  748.        The test that checks the identity of two elements is === .")?
  749.  
  750. public(ad_order_included) ?
  751.  
  752. ad_order_included( [],[]) -> true.
  753. ad_order_included( [],X) -> true(true).
  754. ad_order_included( L1:[A|B],[C|D]) -> 
  755.     cond( A === C,
  756.           ad_order_included(B,D),
  757.               ad_order_included(L1,D) & @(true)).
  758. ad_order_included(X,[]) -> false.
  759.  
  760.  
  761. add_man(ad_included,
  762.      " ad_included(Set1,Set2) -> Res
  763.  
  764.        input: Set1,Set2: sets. 
  765.  
  766.        output: Res: result
  767.  
  768.        Res is true(true) if Set1 is strictly included in Set2,
  769.               true       if Set1 has the exactly the same elements as Set2,
  770.               false otherwise.
  771.        The test that checks the identity of two elements is === .")?
  772.  
  773. public(ad_included) ?
  774.  
  775. ad_included( [],[]) -> true.
  776. ad_included( [],X) -> true(true).
  777. ad_included( [A|B],L) -> 
  778.     cond( ad_member_and_rest(A,L,L1),
  779.           ad_included(B,L1),
  780.           false).
  781.  
  782.  
  783.  
  784. add_man(ad_part,
  785.     " ad_part(Set1,Set2,Inter,Rest1,Rest2)
  786.  
  787.           input: Set1,Set2: sets;
  788.  
  789.           output: Inter,Rest1,Rest2: sets
  790.  
  791.           Inter is the intersection of Set1 and Set2;
  792.           Rest1 is Set1 \ Inter.
  793.           Rest2 is Set2 \ Inter.
  794.  
  795.           The test that checks the identity of two elements is === .")?
  796.  
  797. public(ad_part) ?
  798. ad_part([],L2,[],[],L2) :- !.
  799. ad_part(L1:[A|NewL1],L2,Intersect,RestL1,RestL2) :-
  800.     cond( ad_member_and_rest(A,L2,InterRestL2),
  801.           (
  802.           ad_part(NewL1,InterRestL2,Intersect2,RestL1,RestL2),
  803.           Intersect = [A|Intersect2]
  804.           ),
  805.           (
  806.           ad_part(NewL1,L2,Intersect,RestNewL1,RestL2),
  807.           RestL1 = [A|RestNewL1]
  808.           )).
  809.  
  810.  
  811.  
  812.  
  813. add_man(pick,
  814.     "pick(Term,List)?
  815.  
  816.          input: List
  817.          output: Term, List
  818.  
  819.          Enumerates all the possible values of 'Term' in 'List' and removes
  820.          them from the list.
  821.  
  822.          Useful when several variables have to have mutually different values
  823.          from a single domain.")?
  824.  
  825. public(pick)?
  826.  
  827. %% pick(X,L:[H|T]) :- !,(X=H,L<-T;pick(X,T)).
  828. %% pick(X,[]).
  829.  
  830. pick(X,L:[H|T]) :-
  831.     (
  832.         X = H,
  833.         L <- T
  834.     ;
  835.         pick(X,T)
  836.     ).
  837.  
  838.