CODEWITHSUNDEEP
recursionprolog
imolaflora
imolaflora

Reputation: 23

How to return in prolog all elements from right to left greater than an integer in one predicate?

I have to write a code that return all elements from a given list which are strictly greater than a given integer, it returns from left to right. I cannot use recursion or any other function except the built-in functions: append/3, append/2, member/2, select/3, reverse/2, findall/3, bagof/3, setof/3, sumlist/2

Example case:

greater_list([1,9,2,8,3,7,12],7, X).
 X = 12 ? ;
 X = 8 ? ;
 X = 9 ? ;
 no

I can write it with recursion or help predicates, but without them I do not know how to start. I could use findall/3 but it would not return element by elements, but a list of elements greater than that given number.

Upvotes: 2

Views: 1021

Answers (3)

coredump
coredump

Reputation: 38809

NB. this relies on recursion, I didn't notice that you couldn't use it at first

Instead of reversing the list, you can write the predicate without other helper predicates and consider first the recursive case. This ensures the first element to be checked against N will be the last element of the list.

greater_list([_|L], N, X) :- greater_list(L,N,X).
greater_list([X|_], N, X) :- X > N.

The lack of a clause for the empty list means that the predicate fails for empty lists.

The first clause above declares that X is item from a list that is greater than N if it is such an item in the sublist L.

The second clause, tried on backtracking, declares that the predicate is also true if X is the front element of the list and it is greater than N.

Both clause make Prolog search first in the sublist, and only when backtracking, consider the values stored in the list. As backtracking unfolds from deeper recursion levels first, the rule will be applied in a way that checks the last element first, then second to last, etc.

[eclipse 2]: greater_list([1,9,2,8,3,7,12],7, X).

X = 12
Yes (0.00s cpu, solution 1, maybe more) ? ;

X = 8
Yes (0.00s cpu, solution 2, maybe more) ? ;

X = 9
Yes (0.00s cpu, solution 3, maybe more) ? ;

No (0.00s cpu)

Upvotes: 0

David Tonhofer
David Tonhofer

Reputation: 15316

You can use findall/3 to get a list of the sought elements and then use member/2 to enumerate the members of that list:

greater_list(L,Limit,X) :- 
   findall(E,(member(E,L),E>Limit),Es),
   member(X,Es).

Then:

?- greater_list([1,9,2,8,3,7,12],7, X).
X = 9 ;
X = 8 ;
X = 12.

?- greater_list([],7, X).
false.

And in a roundabout way:

?- findall(X, greater_list([1,9,2,8,3,7,12],7, X), Xs).
Xs = [9, 8, 12].

Upvotes: 1

Isabelle Newbie
Isabelle Newbie

Reputation: 9378

I can write it with recursion or help predicates, but without them I do not know how to start.

I would be interested in how you think you can solve this with helper predicates but not without.

But for starting, consider this: What you need to do is to enumerate certain elements of the list. That is, enumerate elements of the list that have some property.

So to start, you need to know how to enumerate elements of the list. Once you know how to do that, you can worry about the property that they must fulfill.

You can enumerate list elements using member/2:

?- member(X, [1,9,2,8,3,7,12]).
X = 1 ;
X = 9 ;
X = 2 ;
X = 8 ;
X = 3 ;
X = 7 ;
X = 12.

Now, we want to enumerate elements, but only those that fulfill the property X > 7. This is equivalent to saying that "X is a member of the list, and X > 7". In Prolog, (something like) "and" is written with a comma (,):

?- member(X, [1,9,2,8,3,7,12]), X > 7.
X = 9 ;
X = 8 ;
X = 12.

Your predicate is supposed to take a variable limit, not hardcode the limit of 7. This will be similar to:

?- Limit = 7, member(X, [1,9,2,8,3,7,12]), X > Limit.
Limit = 7,
X = 9 ;
Limit = 7,
X = 8 ;
Limit = 7,
X = 12.

Packing this up in a predicate definition will get you started. It looks like the order in which the elements are enumerated here is the reverse of what is intended. Maybe one of your built-ins helps you with this...

(Also, if you know how to write this using findall, you can then use member to enumerate the elements of the findall'ed list. But you shouldn't get in the habit of using findall in general, and especially not if the required solution isn't even a list. Beginners and bad teachers tend to over-emphasize putting things in lists, because that is what you have to do in lesser programming languages. Free yourself from thinking in other languages, even if your teacher can't.)

Upvotes: 5

Related Questions