Numbers in a list smaller than a given number

Question

xMenores(_,[],[]).
xMenores(X,[H|T],[R|Z]) :-
   xMenores(X,T,Z),
   X > H,
   R is H.

xMenores takes three parameters:

• The first one is a number.
• The second is a list of numbers.
• The third is a list and is the variable that will contain the result.

The objective of the rule xMenores is obtain a list with the numbers of the list (Second parameter) that are smaller than the value on the first parameter. For example:

?- xMenores(3,[1,2,3],X).
X = [1,2].                        % expected result

The problem is that xMenores returns false when X > H is false and my programming skills are almost null at prolog. So:

?- xMenores(4,[1,2,3],X).
X = [1,2,3].                      % Perfect.

?- xMenores(2,[1,2,3],X).
false.                            % Wrong! "X = [1]" would be perfect.

I consider X > H, R is H. because I need that whenever X is bigger than H, R takes the value of H. But I don't know a control structure like an if or something in Prolog to handle this.

Please, any solution? Thanks.

Answer 1

You could write it as a one-liner using findall\3:

filter( N , Xs , Zs ) :- findall( X, ( member(X,Xs), X < N ) , Zs ) .

However, I suspect that the point of the exercise is to learn about recursion, so something like this would work:

filter( _ , []     , []     ) .
filter( N , [X|Xs] , [X|Zs] ) :- X <  N , filter(N,Xs,Zs) .
filter( N , [X|Xs] , Zs     ) :- X >= N , filter(N,Xs,Zs) .

It does, however, unpack the list twice on backtracking. An optimization here would be to combine the 2nd and 3rd clauses by introducing a soft cut like so:

filter( _ , []     , []     ) .
filter( N , [X|Xs] , [X|Zs] ) :-
  ( X < N -> Zs = [X|Z1] ; Zs = Z1 ) ,
  filter(N,Xs,Zs)
  .

Answer 2

No new code is presented in this answer.

In the following we take a detailed look at different revisions of this answer by @lurker.

---

Revision #1, renamed to less_than_ver1//2. By using dcg and clpfd, the code is both very readable and versatile:

less_than_ver1(_, []) --> [].
less_than_ver1(N, [H|T]) --> [H], { H #< N }, less_than_ver1(N, T).
less_than_ver1(N, L) --> [H], { H #>= N }, less_than_ver1(N, L).

Let's query!

?-  phrase(less_than_ver1(N,Zs),[1,2,3,4,5]).
  N in 6..sup, Zs = [1,2,3,4,5]
; N  = 5     , Zs = [1,2,3,4]
; N  = 4     , Zs = [1,2,3]
; N  = 3     , Zs = [1,2]
; N  = 2     , Zs = [1]
; N in inf..1, Zs = []
; false.

?- N = 3, phrase(less_than_ver1(N,Zs),[1,2,3,4,5]).
  N = 3, Zs = [1,2]       % succeeds, but leaves useless choicepoint
; false.

?-        phrase(less_than_ver1(N,Zs),[1,2,3,4,5]), N = 3.
  N = 3, Zs = [1,2]
; false.

As a small imperfection, less_than_ver1//2 leaves some useless choicepoints.

Let's see how things went with the newer revision...

---

Revision #3, renamed to less_than_ver3//2:

less_than_ver3([],_) --> [].
less_than_ver3(L,N) --> [X], { X #< N -> L=[X|T] ; L=T }, less_than_ver3(L,N).

This code uses the if-then-else ((->)/2 + (;)/2) in order to improve determinism.

Let's simply re-run the above queries!

?- phrase(less_than_ver3(Zs,N),[1,2,3,4,5]).
  N in 6..sup, Zs = [1,2,3,4,5]
; false.                              % all other solutions are missing!

?- N = 3, phrase(less_than_ver3(Zs,N),[1,2,3,4,5]).
  N = 3, Zs = [1,2]                   % works as before, but no better.
; false.                              % we still got the useless choicepoint

?-        phrase(less_than_ver3(Zs,N),[1,2,3,4,5]), N = 3.
false.                                % no solution! 
                                      % we got one with revision #1!

Surprise! Two cases that worked before are now (somewhat) broken, and the determinism in the ground case is no better... Why?

1. The vanilla if-then-else often cuts too much too soon, which is particularly problematic with code which uses coroutining and/or constraints.

   Note that (*->)/2 (a.k.a. "soft-cut" or if/3), fares only a bit better, not a lot!

2. As if_/3 never ever cuts more (often than) the vanilla if-then-else (->)/2, it cannot be used in above code to improve determinism.

3. If you want to use if_/3 in combination with constraints, take a step back and write code that is non-dcg as the first shot.

4. If you're lazy like me, consider using a meta-predicate like tfilter/3 and (#>)/3.

Answer 3

(This is more like a comment than an answer, but too long for a comment.)

Some previous answers and comments have suggested using "if-then-else" (->)/2 or using library(apply) meta-predicate include/3. Both methods work alright, as long as only plain-old Prolog arithmetics—is/2, (>)/2, and the like—are used ...

?- X = 3, include(>(X),[1,3,2,5,4],Xs).
X = 3, Xs = [1,2].

?-        include(>(X),[1,3,2,5,4],Xs), X = 3.
ERROR: >/2: Arguments are not sufficiently instantiated
% This is OK. When instantiation is insufficient, an exception is raised.

..., but when doing the seemingly benign switch from (>)/2 to (#>)/2, we lose soundness!

?- X = 3, include(#>(X),[1,3,2,5,4],Xs).
X = 3, Xs = [1,2].

?-        include(#>(X),[1,3,2,5,4],Xs), X = 3.
false.
% This is BAD! Expected success with answer substitutions `X = 3, Xs = [1,2]`.

Answer 4

Using ( if -> then ; else )

The control structure you might be looking for is ( if -> then ; else ).

Warning: you should probably swap the order of the first two arguments:

lessthan_if([], _, []).
lessthan_if([X|Xs], Y, Zs) :-
    (   X < Y
    ->  Zs = [X|Zs1]
    ;   Zs = Zs1
    ),
    lessthan_if(Xs, Y, Zs1).

However, if you are writing real code, you should almost certainly go with one of the predicates in library(apply), for example include/3, as suggested by @CapelliC:

?- include(>(3), [1,2,3], R).
R = [1, 2].

?- include(>(4), [1,2,3], R).
R = [1, 2, 3].

?- include(<(2), [1,2,3], R).
R = [3].

See the implementation of include/3 if you want to know how this kind of problems are solved. You will notice that lessthan/3 above is nothing but a specialization of the more general include/3 in library(apply): include/3 will reorder the arguments and use the ( if -> then ; else ).

"Declarative" solution

Alternatively, a less "procedural" and more "declarative" predicate:

lessthan_decl([], _, []).
lessthan_decl([X|Xs], Y, [X|Zs]) :- X < Y,
    lessthan_decl(Xs, Y, Zs).
lessthan_decl([X|Xs], Y, Zs) :- X >= Y,
    lessthan_decl(Xs, Y, Zs).

(lessthan_if/3 and lessthan_decl/3 are nearly identical to the solutions by Nicholas Carey, except for the order of arguments.)

On the downside, lessthan_decl/3 leaves behind choice points. However, it is a good starting point for a general, readable solution. We need two code transformations:

1. Replace the arithmetic comparisons < and >= with CLP(FD) constraints: #< and #>=;
2. Use a DCG rule to get rid of arguments in the definition.

You will arrive at the solution by lurker.

A different approach

The most general comparison predicate in Prolog is compare/3. A common pattern using it is to explicitly enumerate the three possible values for Order:

lessthan_compare([], _, []).
lessthan_compare([H|T], X, R) :-
    compare(Order, H, X),
    lessthan_compare_1(Order, H, T, X, R).

lessthan_compare_1(<, H, T, X, [H|R]) :-
    lessthan_compare(T, X, R).
lessthan_compare_1(=, _, T, X, R) :-
    lessthan_compare(T, X, R).
lessthan_compare_1(>, _, T, X, R) :-
    lessthan_compare(T, X, R).

(Compared to any of the other solutions, this one would work with any terms, not just integers or arithmetic expressions.)

Replacing compare/3 with zcompare/3:

:- use_module(library(clpfd)).

lessthan_clpfd([], _, []).
lessthan_clpfd([H|T], X, R) :-
    zcompare(ZOrder, H, X),
    lessthan_clpfd_1(ZOrder, H, T, X, R).

lessthan_clpfd_1(<, H, T, X, [H|R]) :-
    lessthan_clpfd(T, X, R).
lessthan_clpfd_1(=, _, T, X, R) :-
    lessthan_clpfd(T, X, R).
lessthan_clpfd_1(>, _, T, X, R) :-
    lessthan_clpfd(T, X, R).

This is definitely more code than any of the other solutions, but it does not leave behind unnecessary choice points:

?- lessthan_clpfd(3, [1,3,2], Xs).
Xs = [1, 2]. % no dangling choice points!

In the other cases, it behaves just as the DCG solution by lurker:

?- lessthan_clpfd(X, [1,3,2], Xs).
Xs = [1, 3, 2],
X in 4..sup ;
X = 3,
Xs = [1, 2] ;
X = 2,
Xs = [1] ;
X = 1,
Xs = [] .

?- lessthan_clpfd(X, [1,3,2], Xs), X = 3. %
X = 3,
Xs = [1, 2] ; % no error!
false.

?- lessthan_clpfd([1,3,2], X, R), R = [1, 2].
X = 3,
R = [1, 2] ;
false.

Unless you need such a general approach, include(>(X), List, Result) is good enough.

Answer 5

This can also be done using a DCG:

less_than([], _) --> [].
less_than([H|T], N) --> [H], { H #< N }, less_than(T, N).
less_than(L, N) --> [H], { H #>= N }, less_than(L, N).

| ?- phrase(less_than(R, 4), [1,2,3,4,5,6]).

R = [1,2,3] ? ;

You can write your predicate as:

xMenores(N, NumberList, Result) :- phrase(less_than(Result, N), NumberList).

Answer 6

This answer by @Boris presented a logically pure solution which utilizes clpfd:zcompare/3 to help improve determinism in certain (ground) cases.

In this answer we will explore different ways of coding logically pure Prolog while trying to avoid the creation of useless choicepoints.

---

Let's get started with zcompare/3 and (#<)/3!

• zcompare/3 implements three-way comparison of finite domain variables and reifies the trichotomy into one of <, =, or >.
• As the inclusion criterion used by the OP was a arithmetic less-than test, we propose using (#<)/3 for reifying the dichotomy into one of true or false.

Consider the answers of the following queries:

?- zcompare(Ord,1,5), #<(1,5,B).
Ord = (<), B = true.    

?- zcompare(Ord,5,5), #<(5,5,B).
Ord = (=), B = false.   

?- zcompare(Ord,9,5), #<(9,5,B).
Ord = (>), B = false.    

Note that for all items to be selected both Ord = (<) and B = true holds.

---

Here's a side-by-side comparison of three non-dcg solutions based on clpfd:

• The left one uses zcompare/3 and first-argument indexing on the three cases <, =, and >.
• The middle one uses (#<)/3 and first-argument indexing on the two cases true and false.
• The right one uses (#<)/3 in combination with if_/3.

Note that we do not need to define auxiliary predicates in the right column!

less_than([],[],_).       % less_than([],[],_).          % less_than([],[],_).
less_than([Z|Zs],Ls,X) :- % less_than([Z|Zs],Ls,X) :-    % less_than([Z|Zs],Ls,X) :-
   zcompare(Ord,Z,X),     %    #<(Z,X,B),                %    if_(Z #< X,
   ord_lt_(Ord,Z,Ls,Rs),  %    incl_lt_(B,Z,Ls,Rs),      %        Ls = [Z|Rs],
   less_than(Zs,Rs,X).    %    less_than(Zs,Rs,X).       %        Ls = Rs),
                          %                              %    less_than(Zs,Rs,X).   
ord_lt_(<,Z,[Z|Ls],Ls).   % incl_lt_(true ,Z,[Z|Ls],Ls). %
ord_lt_(=,_,   Ls ,Ls).   % incl_lt_(false,_,   Ls ,Ls). %    
ord_lt_(>,_,   Ls ,Ls).   %                              % 

---

Next, let's use dcg!

• In the right column we use if_//3 instead of if_/3.
• Note the different argument orders of dcg and non-dcg solutions: less_than([1,2,3],Zs,3) vs phrase(less_than([1,2,3],3),Zs).

The following dcg implementations correspond to above non-dcg codes:

less_than([],_) --> [].   % less_than([],_) --> [].      % less_than([],_) --> [].  
less_than([Z|Zs],X) -->   % less_than([Z|Zs],X) -->      % less_than([Z|Zs],X) -->  
   { zcompare(Ord,Z,X) }, %    { #<(Z,X,B) },            %    if_(Z #< X,[Z],[]),
   ord_lt_(Ord,Z),        %    incl_lt_(B,Z),            %    less_than(Zs,X).     
   less_than(Zs,X).       %    less_than(Zs,X).          %
                          %                              %  
ord_lt_(<,Z) --> [Z].     % incl_lt_(true ,Z) --> [Z].   % 
ord_lt_(=,_) --> [].      % incl_lt_(false,_) --> [].    %
ord_lt_(>,_) --> [].      %                              % 

---

OK! Saving the best for last... Simply use meta-predicate tfilter/3 together with (#>)/3!

less_than(Xs,Zs,P) :-
   tfilter(#>(P),Xs,Zs).