3

I am trying my hand in writing a relational prolog program that manages a key, value store. The initial code is taken from some lecture slides i found on the internet (http://people.eng.unimelb.edu.au/pstuckey/book/course.html -- see: using data structure slides).

newdic([]).
addkey(D0,K,I,D) :- D = [p(K,I)|D0].
delkey([],_,[]).
delkey([p(K,_)|D],K,D).
delkey([p(K0,I)|D0],K,[p(K0,I)|D]) :-
    dif(K, K0), delkey(D0,K,D).

This code allows adding more than one value with the same key -- which, is fine with me. However, it also adds the same key, value pair twice, e.g.

?- newdic(D), addkey(D, a, 1, D2), addkey(D2, a, 1, D3), lookup(D3, a, X).
D = [],
D2 = [p(a, 1)],
D3 = [p(a, 1), p(a, 1)],
X = 1

D3 includes p(a,1) twice.

To ensure that this doesn't happen i added the following code; and to ensure that backtracking doesn't find the alternative addkey clause, I added a cut in the end of the first clause.

Is this fair game for a purely relational program -- or are the better ways to ensure that no duplicate key,value pairs are added --without the use of a cut. 

newdic([]).
addkey(D0,K,I,D0) :- lookup(D0, K, I), !.   % if the key already do nothing
addkey(D0,K,I,D) :- D = [p(K,I)|D0].
delkey([],_,[]).
delkey([p(K,_)|D],K,D).
delkey([p(K0,I)|D0],K,[p(K0,I)|D]) :-
    dif(K, K0), delkey(D0,K,D).

this leads to the following:

?- newdic(D), addkey(D, a, 1, D2), addkey(D2, a, 1, D3), lookup(D3, a, X).
D = [],
D2 = D3, D3 = [p(a, 1)],
X = 1.

No, more solutions are available -- the program returns immediately.

any suggestions are much appreciated,

Daniel

Note: as an aside: that if i add for the same key different values, the cut does allow to backtrack to identify the second value for the same key:

?- newdic(D), addkey(D, a, 1, D2), addkey(D2, a, 1, D3), addkey(D3, a, 2, D4), lookup(D4, a, X).
D = [],
D2 = D3, D3 = [p(a, 1)],
D4 = [p(a, 2), p(a, 1)],
X = 2 ;
D = [],
D2 = D3, D3 = [p(a, 1)],
D4 = [p(a, 2), p(a, 1)],
X = 1.
false
  • 10,264
  • 13
  • 101
  • 209
user2193970
  • 345
  • 2
  • 10
  • You could use something like `once(lookup(D0, K, I))` if you only want it to succeed one time. – lurker Dec 04 '17 at 15:06
  • Are you really happy with the current answers? After all, you ask something somewhat different. – false Dec 06 '17 at 14:57

2 Answers2

2

SWI Prolog has library predicates for dealing with key-value pairs and associations. I haven't looked at them closely to see what might match your situation, but something to consider.

If you want to roll your own solution, you could write addkey/4 out recursively and maintain the relational behavior:

addkey([], K, V, [p(K,V)]).             % Add to empty dict
addkey([p(K,V)|T], K, _, [p(K,V)|T]).   % Don't add
addkey([p(K,V)|T], Kadd, Vadd, [p(K,V)|TK]) :-
    dif(Kadd, K),
    addkey(T, Kadd, Vadd, TK).

This implementation adds if the key is unique. It ignores the addition and yields the same dictionary back if you try the same key even with different a value (which is usually how a dictionary of key-value pairs behaves). You can enhance it for the uniqueness of the key-value pair pretty easily. Of course, the Prolog you're using would need to include dif/2, or you'd need to roll your own dif/2. :)

lurker
  • 56,987
  • 9
  • 69
  • 103
  • Thank you. I was interested in trying my own to get a handle on relational prolog; but now that you mention it, i will probably soon switch to using the assoc library in swi-prolog -- which is much more mature and likely more scalable as well. – user2193970 Dec 04 '17 at 19:35
0

You can use if-then-else instead of cut:

addkey(D0,K,I,D0) :-
  ( lookup(D0, K, I) ->
    D = D0 % if the key already [exists] do nothing
  ; D = [p(K,I)|D0] ).
Tomas By
  • 1,396
  • 1
  • 11
  • 23
  • Thank you for the prompt response. Does this if-then-else qualify as relational ... – user2193970 Dec 04 '17 at 14:46
  • 3
    @user2193970 The "if-then-else" is equivalent to using a cut and is no more "relational" in its behavior. The expression, `p1 -> p2 ; p3` behaves as: `(p1, !, p2) ; p3`. It may be visually more acceptable, but behaviorially is no more so. The relational version of an if-then-else is [`if_/3`](https://stackoverflow.com/questions/27358456/prolog-union-for-a-u-b-u-c/27358600#27358600). – lurker Dec 04 '17 at 14:59
  • 1
    Not only visually/aesthetically, it is also harder to misuse. Cuts are mostly used to avoid fixing problems with the logic. – Tomas By Dec 04 '17 at 15:10
  • 1
    I can't find if_/3 in swi-prolog -- can i write it out with other constructs? – user2193970 Dec 04 '17 at 15:17
  • 3
    @user2193970 unfortunately, `if_/3` isn't a standard predicate. It's defined in the link I provided. – lurker Dec 04 '17 at 15:18
  • I now have this code: addkey(D0,K,I,D) :- if_(lookup(D0, K, I), D = D0, % key already exists do nothing D = [p(K,I)|D0]). i am getting an error with call(If_1, T), which seems to add an additional parameter to the lookup/3, leading to the following error: ?- newdic(D), trace, addkey(D, a, 1, D2), addkey(D2, a, 1, D3), addkey(D3, a, 2, D4), lookup(D4, a, X). ERROR: [... ]Undefined procedure: lookup/4 ERROR: [... ] However, there are definitions for: ERROR: [...] lookup/3 – user2193970 Dec 04 '17 at 16:12
  • Perhaps call/2 in swi-prolog and call/2 in iso-prolog behave differently, with the latter providing a return value and the former expecting another parameter. Nope -- somehow the last parameter is understood as return value -- so not sure why the call/2 failed in this case. – user2193970 Dec 04 '17 at 16:18
  • You can edit the question instead of posting code in comments. – Tomas By Dec 04 '17 at 16:20