CODEWITHSUNDEEP
prolog
iMajna
iMajna

Reputation: 499

Get all elements of the list which are less than particular number

By the time I'm learning Prolog I encountered on a problem. I'm trying to make function like this 

   ?- less_than([1,2,3,2,1,5],3,Y).
      Y= [1,2,2,1]

Because I was learning object-oriented programming I stacked with this and can't figure out how to solve. This is mine code:

  less_than([],X,Y).
  less_than([H|T], X, [H1|T1]) :-
            H<X, less_than(T,X,H).

And also, I tried with findall:

  less_than([],X,Y).
  less_than([H|T],X,[H1|T1]) :-
            findall(H, (H<X, less_than(T,X,Y)), Z).

Where I'm getting this result:

Y = [_G2274|_G2275]  for ?- less_than([1,2,3,4,5],3,X)

I know that they are unknown values but how to set values in that list? I tried to change Y with and H but it wont work.

I tried to debug it but with no success, it keeps falling apart and this is only logical explanation how to solve it for me. Any1 has an idea?

Upvotes: 0

Views: 1705

Answers (1)

mat
mat

Reputation: 40768

I won't solve the whole issue for you, but I would like to show you how you can approach such issues in general.

A major advantage of Prolog is that you can debug issues declaratively. This means that you use logical properties of Prolog to locate the causes of unintended answers.

For example, in your case, you have the program:

less_than([], X, Y).
less_than([H|T], X, [H1|T1]) :-
        H < X,
        less_than(T, X, H).

and the following unintended failure of a query:

?- less_than([1,2,3,2,1,5], 3, Y).
false.

Let us use the following definition to generalize a Prolog program, like in GUPU:

:- op(950,fy, *).

*_.

For example, consider the following generalization, which we obtain by placing (*)/1 in front of all goals:

less_than([], X, Y).
less_than([H|T], X, [H1|T1]) :-
        * H < X,
        * less_than(T, X, H).

With this generalization, we have:

?- less_than([1,2,3,2,1,5],3,Y).
Y = [_G946|_G947].

So, while this is now too general, at least the query succeeds.

By refining the generalization, we can narrow down the exact cause of the problem. For example:

less_than([], X, Y).
less_than([H|T], X, [H1|T1]) :-
        * H < X,
        less_than(T, X, H).

This again yields:

?- less_than([1,2,3,2,1,5],3,Y).
false.

Observe that adding further goals can at most specialize the program, never generalize it. Therefore, the remaining fragment must be generalized if we want this query to succeed at all.

So, if you want your query to succeed at all, you must make at least the following fragment succeed for the query:

less_than([], X, Y).
less_than([H|T], X, [H1|T1]) :-
        less_than(T, X, H).

Why does this currently fail? Try the following further generalization:

less_than([], /*X*/_, /*Y*/_).
less_than([H|T], /*X*/_, [/*H1*/_|/*T1*/_]) :-
        less_than(T, /*X*/_, H).

This still fails:

?- less_than([1,2,3,2,1,5],3,Y).
false.

So, we have now reduced this to:

less_than([], _, _).
less_than([H|T], _, [_|_]) :-
        less_than(T, _, H).

And now the point: Interestingly, the following generalization succeeds:

less_than([], _, _).
less_than([H|T], _, [_|_]) :-
        less_than(T, _, /*H*/_).

Therefore, this last argument of the call of less_than/3 is a hot candidate for closer scrutiny...

Upvotes: 3

Related Questions