Find the number of elements greater than a number in a list in PROLOG

3
votes

Hello and thank you for taking the time to read this question. I have the following problem:

Given a list that returned the number of numbers greater than X Example:

greater (4, [1,2,3,4,5,6], N) Result. N = 2 My code is:

greater(0,[],0):-!, fail.
greater(N,[N],1).
greater(N,[H|Q],X):-H>N,greater(Q,N,X),X is X+1.

The problem is that PROLOG only returns False but not the value of X.

I hope you can explain to me what I am doing wrong, I thank you in advance for your

1
prolog
X is X+1 is non-sensical. A variable can only be unified with one value, and a variable thus can not be 1 and 2 at the same time. – Willem Van Onsem
Why do you write fail in the first clause? Furthermor what should happen if H <= N here? – Willem Van Onsem
I write fail in case the list is empty. – Krasnax
then I do not use the same variable I can use an auxiliary variable. – Krasnax
Since the absence of a successful query is failure in Prolog, you don't need greater(0,[],0):-!, fail.. greater(0, [], 0) will fail if it doesn't succeed via your other predicate clauses. Your base case, greater(N,[N],1). is not correct. This says that N is greater than N, which certainly isn't true. What should the base case be? What is the case where you have a single element list and a number? When should it succeed with 1? – lurker

1 Answers

1
votes

Since a predicate call fails in Prolog if there are no success paths for that call, then the following predicate clause serves no purpose. You can remove it.

greater(0,[],0):-!, fail.

Your next clause is your recursive base case and is incorrectly formulated:

greater(N,[N],1).

This succeeds even though it violates your condition that you want to count elements in the list that are greater than N. N is not greater than N. What should this clause look like if you want greater(N, [X], 1). to succeed?

In your recursive clause, you have a problem:

greater(N,[H|Q],X):-H>N,greater(Q,N,X),X is X+1.

X is X+1 will always fail because the value of X cannot possibly ever be the same as the value X+1. That is, there is no number that is equal to itself plus one. You need to use an auxiliary variable:

greater(N,[H|Q],X):-H>N,greater(Q,N,X1),X is X1+1.

Finally, you're missing the case when H =< N:

greater(N,[H|Q],X):-H=<N, ....

What should this clause look like?