What I want is something like merge(Dict1, Dict2, Merged) that behaves like the following:
?- merge(counter{a: 1, b: 2}, counter{a: 3, c: 4, d: 5}, Merged).
Merged = counter{a: 4, b: 2, c: 4, d: 5}
What should I do to achieve this? I'm totally new to logic programming, so I end up failing trying to write something that looks like a terrible port of for loop of other languages.
dicts_merge_add(Dict1, Dict2, DictMerged) :-
% Convert to sorted key-value pairs
dict_pairs(Dict1, Tag, Pairs1),
dict_pairs(Dict2, Tag, Pairs2),
% Merge the pairs
pairs_merge_add(Pairs1, Pairs2, PairsMerged),
% Convert to dict
dict_pairs(DictMerged, Tag, PairsMerged).
% When reached end of 1 list, insert the remains of the other list
pairs_merge_add([], T, T) :- !.
pairs_merge_add(T, [], T) :- !.
pairs_merge_add([K-V1|T1], [K-V2|T2], L) :-
% Keys are same
!,
Sum is V1 + V2,
L = [K-Sum|Merg],
pairs_merge_add(T1, T2, Merg).
pairs_merge_add([K1-V1|T1], [K2-V2|T2], L) :-
K1 @< K2,
!,
L = [K1-V1|Merg],
pairs_merge_add(T1, [K2-V2|T2], Merg).
pairs_merge_add([K1-V1|T1], [K2-V2|T2], L) :-
K1 @> K2,
!,
L = [K2-V2|Merg],
pairs_merge_add([K1-V1|T1], T2, Merg).
Result in swi-prolog:
?- D1 = counter{a: 1, b: 2, z:6},
D2 = counter{a: 3, c: 4, z:8, d: 5},
time(dicts_merge_add(D1, D2, Merg)).
% 17 inferences, 0.000 CPU in 0.000 seconds (88% CPU, 389265 Lips)
D1 = counter{a:1,b:2,z:6},
D2 = counter{a:3,c:4,d:5,z:8},
Merg = counter{a:4,b:2,c:4,d:5,z:14}.
Simple performance test:
?- C = 30_000, numlist(1, C, L1N),
findall(N-N, member(N, L1N), L1),
dict_pairs(D1, v, L1), numlist(1, C, L2N),
findall(N-N, member(N, L2N), L2), dict_pairs(D2, v, L2),
time(merge(D1, D2, D3)), sleep(10).
% 180,005 inferences, 5.475 CPU in 5.486 seconds (100% CPU, 32877 Lips)
Vs mine: time(dicts_merge_add(D1, D2, D3))
% 60,005 inferences, 0.012 CPU in 0.012 seconds (100% CPU, 4987461 Lips)
This shows the huge performance advantage from using the fact that the lists are sorted.