Returning multiple values from a Prolog list

user_12828320 0
Viewed 75

In this Prolog exercise, I'm trying to return the values from a list which are greater than a number N.

For example: greater_than([5,6,1,7], 5, X) should return X = 6 ; X = 7.

I tried to solve this by doing:

greater_than([],_,_).   % to stop recursion when list is empty
greater_than([H|T],N,X) :-
   H > N,
   X is H,
   greater_than(T,N,M). % if H>N return X=H
greater_than([H|T],N,X) :-
   H =< N,
   greater_than(T,N,X). % if H=<N just continue recursion.

My code works when there is only one result: greater_than([1,2,5], 2, X) returns X = 5.

But it doesn't work with multiple results: greater_than([1,2,5,7], 2, X) returns false.

I understood from this that X is already binded to a number and (X is H) for the second time returns false.

But I didn't know how to get multiple results.

I tried to change variables name:

greater_than([H|T],N,X) :-
   H > N,
   X is H,
   greater_than(T,N,X1).   % X1 for example

but that didn't work.

prolog
1 Answers

I understood from this that X is already binded to a number and (X is H) for the second time returns false.

Almost, but not quite because those happen in different calls so that could work on its own. Your code binds X=5 and then in the next call it binds M=7, and there's nowhere for you to see the value of M. The 7 is already used, when you search again, there's no more answers to find because it has found all the answers, reached the end of the list.

You are mixing up backtracking with recursion, two different ways of solving this.

A backtracking solution:

greater_than(List, Cutoff, X) :-
   member(X, List),
   X > Cutoff.

Then:

?- greater_than([1,2,5,7], 2, X).
X = 5 ;
X = 7

It finds one answer, and waits, then you ask for more, and it finds more.

A recursive solution walks the list in your code, instead of having Prolog do it, e.g. to build a list with all the answers:

greater_than([], _, []).  % recursion base case. Empty list input, empty list output.
greater_than([H|T], Cutoff, [H|Result_T]) :-
    H > Cutoff,
    greater_than(T, Cutoff, Result_T).
greater_than([H|T], Cutoff, Result) :-
    H =< Cutoff,
    greater_than(T, Cutoff, Result).

Then:

?- greater_than([1,2,5], 2, X).
X = [5]
user_4786560
Related