Prolog search key/value list and output a list of values

Question

I'm once again stuck with a pretty simple Prolog task. I want to define a predicate kv_search/3 that takes a key/value list such as [[a,1],[b,2],[c,3],[d,4],[e,8],[a,9],[b,10]] as a first argument, a key as second and outputs a list of all values with that key in the third argument.

My current approach looks like this:

kv_find([[K,V|_]|Rest], K, Result) :- 
    kv_find(Rest, K, [V|Result]).

kv_find([[Ks,_|_]|Rest], K, Result) :-
    Ks \= K ,
    kv_find(Rest, K, Result).

kv_find([], _, _).

The problem with this solution is however that it just outputs true or false instead of printing the missing parameter.

E.g. the following query result in true instead of my expected result of B=[1, 9]:

kv_find([[a,1],[b,2],[c,3],[d,4],[e,8],[a,9],[b,10]], a, B).

If the key is not present in the list I want to output an empty list.

Can you explain the reasoning behind your base case? For example, what should kv_find([],a,X) bind to X (if anything)? — Scott Hunter
For this task we can assume that the first parameter is a valid key/value list in the form I showed. But your example could result in X=[]. — KevKosDev
"Could"? Suggesting could be something else? And your code does not behave this way. — Scott Hunter
True. But I didn't think of this case until now because my excercise does not specify this case. — KevKosDev
@JohnnyKonfetti "my excercise does not specify this case." well thats not true when you have recursion you need always think the right base case since a wrong base case could lead to a wrong overall predicate... — coder

coder coder · Accepted Answer · 2018-10-21T16:17:53

Firstly your base case is wrong, you need to write:

kv_find([], _, []).

Since with empty list only an empty output list should succeed.

Then another problem in your solution is that you are writing:

kv_find([[K,V|_]|Rest], K, Result) :- 
    kv_find(Rest, K, [V|Result]).

While you should write something like:

kv_find([[K,V|_]|Rest], K, [V | Result]) :- 
    kv_find(Rest, K, Result).

And the above rule with the wrong base case made your predicate always succeed for any third list.

Moreover with a few changes I would write something like:

kv_find([[K,V]|Rest], K, [V|Result]) :- 
    kv_find(Rest, K, Result).

kv_find([[Ks,_]|Rest], K, Result) :-
    dif(Ks, K) ,
    kv_find(Rest, K, Result).

kv_find([], _, []).

Prolog search key/value list and output a list of values

1 Answers