Remove pair from list, only if it exists

Question

I'm attempting to make a predicate that takes a list of pairs and, if it finds the key in the list it will remove that item from the list and return the rest. However, it also needs to return the full list if the key given does not exist.

unmap(K, M1, M2):-
    select(E, M1, MM1),
    select(E, [(K, _)], K1),
    unmap(MM1, K1, M2).
unmap(X, _, X).

Called with:

unmap(key1, [(key1, value1),(key2, value2),(key3, value3)], R).

Results in:

R = [(key2, value2), (key3, value3)]

Works, but theres a problem. I'm trying to make it return the identical list thats given if the key1 does not exist. Here's what it returns:

Calling:

unmap(key4, [(key1, value1),(key2, value2),(key3, value3)], R).

Returns:

R = key4

I think it's something to do with my terminating rule, but I'm not sure how to go about fixing it. Thanks very much in advance for all that can help.

score 2 · Answer 1 · edited May 23 '17 at 10:24

Of course, you can do it with logical-purity! Here's how...

Let's call the actual relation pairs_key_unmapped/3. That's a somewhat more descriptive name. unmap/3 is just a wrapper for pairs_key_unmapped/3:

unmap(Key,Ps0,Ps) :-
    pairs_key_unmapped(Ps0,Key,Ps).

The implementation of pairs_key_unmapped/3 is built on the predicates if_/3 and =/3 (a.k.a. equal_truth/3), as defined by @false in an answer to "Prolog union for A U B U C":

pairs_key_unmapped([],_,[]).
pairs_key_unmapped([P|Ps],K,Us) :-
    P = (K0,_),
    if_(K0=K, Ps=Us, (Us=[P|Us0],pairs_key_unmapped(Ps,K,Us0))).

Let's run some queries!

?- unmap(key1,[(key1,value1),(key2,value2),(key3,value3)],Ps).
Ps = [(key2,value2),(key3,value3)].                % succeeds deterministically

?- unmap(key4,[(key1,value1),(key2,value2),(key3,value3)],Ps).
Ps = [(key1,value1),(key2,value2),(key3,value3)].  % succeeds deterministically

Let's try something different... What if Key occurs twice in Ps0?

?- unmap(key1,[(key1,x),(key1,y)],Ps).   % only the 1st occurrence is removed
Ps = [(key1,y)].                         % succeeds deterministically

What if Ps0 is unknown, but Ps is known?

?- unmap(key4,Ps0,[(key1,value1),(key2,value2),(key3,value3)]).
Ps0 = [(key4,_A),    (key1,value1),(key2,value2),(key3,value3)] ;
Ps0 = [(key1,value1),(key4,_A),    (key2,value2),(key3,value3)] ;
Ps0 = [(key1,value1),(key2,value2),(key4,_A),    (key3,value3)] ;
Ps0 = [(key1,value1),(key2,value2),(key3,value3)              ] ;
Ps0 = [(key1,value1),(key2,value2),(key3,value3),(key4,_A)    ] ;
false.

How about something a little more general?

?- unmap(Key,Ps0,[_,_]).
Ps0 = [(Key,_A),_B,       _C      ]                           ;
Ps0 = [(_A,_B), (Key,_C), _D      ], dif(_A,Key)              ;
Ps0 = [(_A,_B), (_C,_D)           ], dif(_A,Key), dif(_C,Key) ;
Ps0 = [(_A,_B), (_C,_D),  (Key,_E)], dif(_A,Key), dif(_C,Key) ;
false.

And what answers does the most general query give us?

?- unmap(Key,Ps0,Ps).
Ps0 = [],                    Ps = []                             ;
Ps0 = [(Key,_A)|Ps]                                              ;
Ps0 = [(_A,_B)],             Ps = [(_A,_B)],         dif(_A,Key) ;
Ps0 = [(_A,_B),(Key,_C)|_Z], Ps = [(_A,_B)|_Z],      dif(_A,Key) ;
Ps0 = [(_A,_B),(_C,_D)],     Ps = [(_A,_B),(_C,_D)], dif(_A,Key), dif(_C,Key) ...

lurker · Accepted Answer · 2014-02-22T17:31:19.077

1

The issue is with your base case:

unmap(X, _, X).

If your main predicate clause fails (the key isn't found), it reverts to the base case, which will instantiate your result (third argument) with only the key (first argument). Your base case should be:

unmap(_, X, X).

Which will instantiate the result (third argument) with the original list (second argument).

Note that the main clause could be simpler (this will work in GNU or SWI prolog):

unmap(K, M, R):-
    select((K, _), M, M1),
    unmap(K, M1, R), !.

The cut prevents backtracking to the base case if the first clause succeeds.

In SWI Prolog, the delete/3 predicate will work in your favor:

unmap(K, M, R) :-
    delete(M, (K,_), R), !.

delete/3 is more strict in GNU Prolog and will not work in this case.

edited Feb 22 '14 at 17:31

answered Feb 22 '14 at 17:05

lurker

56,987
9
69
103

Thank you very much! This works exactly as I wanted. I'm using WIN-PROLOG so, not sure if it supports delete/3. Also, what does the "!" mean? I'm still a beginner so have not come across it. Thanks again! – Linkandzelda Feb 22 '14 at 17:34
@Linkandzelda The `!` is a cut in prolog. You should read some information about how it works. It can be tricky to use if done without much thought. It prevents prolog from backtracking to any point before the cut and is used to eliminate choice points in a predicate. Sometimes you want those choice points to get all the solutions! But in this case, you are after the one main solution. So cut is appropriate. If you're happy with an answer you should upvote it at least, and mark it as the answer if it's the one you want. – lurker Feb 22 '14 at 17:36
Thanks, I understand now about "!", and will read up more about it as well. Marked your answer ;) – Linkandzelda Feb 22 '14 at 17:42

score 1 · Answer 3 · answered Feb 22 '14 at 17:36

This isn't so much an answer to the question, but a simpler way of attacking it, without using the 'select' (or any other built-in predicates), and only using recursion.

Considering that the output list is just a list of items that didn't match the key, you need 2 main clauses, and iterate around the list. One where the key matches the head of the list, and one that doesn't.

unmap(_, [], []).

% head of the list matches key, do not add K/H to unmatched list (ie remove it)
unmap(K, [(H, _)|Tail], Unmatched) :-
    H == K,
    unmap(K, Tail, Unmatched).

% above rule fails, add H to unmatched list
unmap(K, [H|Tail], [H|Unmatched]) :-
    unmap(K, Tail, Unmatched).


?- unmap(key1, [(key1, value1),(key2, value2),(key3, value3)], R).
R = [ (key2, value2), (key3, value3)] .

?- unmap(key4, [(key1, value1),(key2, value2),(key3, value3)], R).
R = [ (key1, value1), (key2, value2), (key3, value3)] .

So if the key doesn't exist, it just iterates around adding all list items, and so the input and output lists are identical.

You can remove the `H == K` line in the second clause and make the head of the clause be, `unmap(K, [(K, _)|Tail], Unmatched) :-`. Also, to prevent backtracking to unwanted solutions, the third clause implementation should start with `K \== H`. — lurker, Feb 22 '14 at 17:37

Remove pair from list, only if it exists

3 Answers3