fork download
copy 
  1. :- set_prolog_flag(verbose,silent).
  2. :- prompt(_, '').
  3. :- use_module(library(readutil)).
  4.  
  5. % set membership with non-pure builtin \==
  6. % to cut down duplicate answers as sets
  7. memb(X,[X|_]).
  8. memb(X,[Y|L]) :- X \== Y, memb(X,L).
  9.  
  10. % unify finite sets (i.e. set with [] at the end)
  11. unify_set(A,B) :- subset_of(A,B), subset_of(B,A).
  12.  
  13. subset_of([], _).
  14. subset_of([X|R],L) :- memb(X,L), subset_of(R,L).
  15.  
  16. % finite set union
  17. union([],B,B).
  18. union(A,[],A).
  19. union([X|Xs],B,C) :- memb(X,B), !, union(Xs,B,C).
  20. union([X|Xs],B,[X|C]) :- union(Xs,B,C).
  21.  
  22. % finite set intersection
  23. intersect([],_,[]).
  24. intersect(_,[],[]).
  25. intersect([X|Xs],B,[X|C]) :- memb(X,B), !, intersect(Xs,B,C).
  26. intersect([_|Xs],B,C) :- intersect(Xs,B,C).
  27.  
  28. % finite set minus
  29. setminus(A,[],A).
  30. setminus([],_,[]).
  31. setminus([X|Xs],B,C) :- memb(X,B), !, setminus(Xs,B,C).
  32. setminus([X|Xs],B,[X|C]) :- setminus(Xs,B,C).
  33.  
  34. % unify open ended sets with possibly uninstantiated variable tail at the end
  35. unify_oeset(A,B) :- ( var(A); var(B) ), !, A=B.
  36. unify_oeset(A,B) :-
  37. 	split_heads(A,Xs-T1), make_set(Xs,S1),
  38. 	split_heads(B,Ys-T2), make_set(Ys,S2),
  39. 	unify_oe_set(S1-T1, S2-T2).
  40.  
  41. make_set(L,S) :- setof(X,memb(X,L),S).
  42.  
  43. split_heads([],[]-[]).
  44. split_heads([X|T],[X]-T) :- var(T), !, true.
  45. split_heads([X|Xs],[X|Hs]-T) :- split_heads(Xs,Hs-T).
  46.  
  47. % helper function for unify_oeset (almost no duplication)
  48. unify_oe_set(Xs-T1,Ys-T2) :- T1==[], T2==[], unify_set(Xs,Ys).
  49. unify_oe_set(Xs-T1,Ys-T2) :- T1==[], subset_of(Ys,Xs), T2=Xs.
  50. unify_oe_set(Xs-T1,Ys-T2) :- T2==[], subset_of(Xs,Ys), T1=Ys.
  51. unify_oe_set(Xs-T1,Ys-T2) :- 
  52. 	setminus(Ys,Xs,L1), append(L1,T,T1),
  53. 	setminus(Xs,Ys,L2), append(L2,T,T2).
  54.  
  55. main:-
  56. 	process,
  57. 	halt.
  58.  
  59. process:-
  60. 	/* your code goes here */
  61. 	unify_oeset([1,3,5,9|T1],[2,3,5,6|T2]), print(T1), nl, print(T2), nl,
  62. 	true.
  63.  
  64. :- main.
Success #stdin #stdout 0.06s 7736KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[2,6|_G1663]
[1,9|_G1663]
https://ideone.com/SyDfCy
set unification of possibly open ended sets (i.e. tail could be a variable rather than [])
language:
Prolog (swi 7.6.4)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!