fork download
copy 
  1. :- set_prolog_flag(verbose,silent).
  2. :- prompt(_, '').
  3. :- use_module(library(readutil)).
  4.  
  5. % unify finite maps
  6. unify_map(A,B) :- submap_of(A,B), submap_of(B,A).
  7.  
  8. submap_of([], _).
  9. submap_of([X:V|R],M) :- first(X:V,M), submap_of(R,M).
  10.  
  11. % search key and find value in a finite map
  12. first(X:V,[X:V|_]).
  13. first(X:V,[Y:_|L]) :- X \== Y, first(X:V,L).
  14.  
  15. % finite map minus
  16. mapminus(A,[],A).
  17. mapminus([],_,[]).
  18. mapminus([X:V|Ps],B,C) :- first(X:V1,B), !, (V1 = V -> mapminus(Ps,B,C); fail).
  19. mapminus([X:V|Ps],B,[X:V|C]) :- mapminus(Ps,B,C).
  20.  
  21.  
  22. % unify open ended maps with possibly uninstantiated variable tail at the end
  23. unify_oemap(A,B) :- ( var(A); var(B) ), !, A=B.
  24. unify_oemap(A,B) :-
  25. 	split_heads(A,Xs-T1), make_map(Xs,M1),
  26. 	split_heads(B,Ys-T2), make_map(Ys,M2),
  27. 	unify_oe_map(M1-T1, M2-T2).
  28.  
  29. make_map(L,M) :- setof(X:V,first(X:V,L),M). % unlike sets this may not remove duplicates
  30.  
  31. split_heads([],[]-[]).
  32. split_heads([X:V|T],[X:V]-T) :- var(T), !, true.
  33. split_heads([X:V|Ps],[X:V|Hs]-T) :- split_heads(Ps,Hs-T).
  34.  
  35. % helper function for unify_oemap
  36. unify_oe_map(Xs-T1,Ys-T2) :- T1==[], T2==[], unify_map(Xs,Ys).
  37. unify_oe_map(Xs-T1,Ys-T2) :- T1==[], submap_of(Ys,Xs), mapminus(Xs,Ys,T2).
  38. unify_oe_map(Xs-T1,Ys-T2) :- T2==[], submap_of(Xs,Ys), mapminus(Ys,Xs,T1).
  39. unify_oe_map(Xs-T1,Ys-T2) :- 
  40. 	mapminus(Ys,Xs,L1), append(L1,T,T1),
  41. 	mapminus(Xs,Ys,L2), append(L2,T,T2).
  42.  
  43.  
  44. main:-
  45. 	process,
  46. 	halt.
  47.  
  48. process:-
  49. 	unify_oemap([z:string,y:bool|M1],[y:T,x:int|M2]),
  50. 	write("T = "), print(T), nl,
  51. 	write("M1 = "), print(M1), nl,
  52. 	write("M2 = "), print(M2), nl,
  53. 	true.
  54.  
  55. :- main.
Success #stdin #stdout 0.06s 7732KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
T = bool
M1 = [x:int|_G1681]
M2 = [z:string|_G1681]
https://ideone.com/GAcIVa
map unification of possibly open eded maps (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!