列表中小于给定数字的数字

Question

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

xMenores 接受三个参数：

第一个是数字。
第二个是数字列表。
第三个是列表，是将包含结果的变量。

规则xMenores的objective是获取一个列表，其中列表（第二个参数）的编号小于第一个参数的值。例如：

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

问题是 xMenores returns false 当 X > H 为假时，我的编程技能在 prolog 时几乎是零。所以：

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

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

我考虑 X > H, R is H. 因为我需要每当 X 大于 H 时，R 取 H 的值。但是我不知道 Prolog 中的 if 之类的控制结构来处理这个问题。

请问有什么解决办法吗？谢谢。

Answer 1

您可以使用 findall:

将其写成一行

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

但是，我怀疑练习的目的是学习递归，所以像这样的东西会起作用：

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

但是，它确实在回溯时将列表解包两次。这里的优化是通过引入 soft cut 来组合第二和第三个子句，如下所示：

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

Answer 2

使用`( if -> then ; else )`

您可能正在寻找的控制结构是 ( if -> then ; else )。

警告：你应该调换前两个参数的顺序：

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

但是，如果您正在编写真正的代码，您几乎肯定应该使用 library(apply), for example include/3, as :

中的谓词之一

?- 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].

如果您想知道此类问题是如何解决的，请参阅the implementation of include/3。您会注意到上面的 lessthan/3 只不过是 library(apply) 中更通用的 include/3 的特化： include/3 将重新排序参数并使用 ( if -> then ; else ).

"Declarative"解决方案

或者，少 "procedural" 多 "declarative" 谓词：

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 和 lessthan_decl/3 几乎与相同，除了参数的顺序。）

不利的一面是，lessthan_decl/3 留下了选择点。但是，对于一般的、可读的解决方案来说，这是一个很好的起点。我们需要两个代码转换：

用 CLP(FD) 约束替换算术比较 < 和 >=：#< 和 #>=；
使用 DCG 规则删除定义中的参数。

您将到达。

一种不同的方法

Prolog 中最通用的比较谓词是compare/3。使用它的一种常见模式是显式枚举 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).

（与任何其他解决方案相比，这个解决方案适用于任何项，而不仅仅是整数或算术表达式。）

将 compare/3 替换为 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).

这绝对比任何其他解决方案的代码都多，但它不会留下不必要的选择点：

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

在其他情况下，它的行为与 lurker 的 DCG 解决方案一样：

?- 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.

除非您需要这种通用方法，否则 include(>(X), List, Result) 就足够了。

Answer 3

这也可以使用 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] ? ;

您可以将谓词写成：

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

Answer 4

（这更像是评论而不是答案，但对于评论来说太长了。）

之前的一些回答和评论建议使用 "if-then-else" (->)/2 或使用 library(apply) meta-predicate include/3。这两种方法都可以正常工作，只要只使用普通的 Prolog 算术——is/2、(>)/2 等......

?- 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.

...，但是在执行从 (>)/2 到 (#>)/2 的 看似良性的切换 时，我们失去了稳健性！

?- 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 5

此答案中没有新代码。

下面我们详细看看的不同版本。

Revision #1, renamed to less_than_ver1//2. By using dcg and clpfd，代码可读性强，用途广泛：

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).

来查询吧！

?-  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.

作为一个小瑕疵，less_than_ver1//2留下了一些无用的选择点。

让我们看看新版本的进展情况...

Revision #3，重命名为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).

此代码使用 if-then-else ((->)/2 + (;)/2) 以提高确定性。

让我们简单地重新运行上面的查询！

?- 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!

惊喜！以前工作的两个案例现在（有点）坏了，地面案例中的确定性也好不到哪里去...... 为什么？

香草 if-then-else 经常削减太多太快，这对于使用协程 and/or 约束的代码尤其有问题。

请注意 (*->)/2（a.k.a。"soft-cut" 或 if/3），票价只是好一点，不是很多！
因为 if_/3 永远不会（经常）削减普通的 if-then-else (->)/2，所以不能在上面的代码中使用它来提高确定性。
如果要结合约束使用if_/3，退一步，先写非dcg的代码。
如果你像我一样懒惰，可以考虑使用 meta-predicate，比如 tfilter/3 和 (#>)/3。

Answer 6

presented a logically pure solution which utilizes clpfd:zcompare/3 以帮助改善某些（地面）情况下的确定性。

在这个答案中，我们将探索不同的逻辑纯 Prolog 编码方式，同时尽量避免创建无用的选择点。

让我们从 zcompare/3 和 (#<)/3 开始吧！

zcompare/3 实现有限域变量的 three-way comparison 并将三分法具体化为 <、= 或 >.[=87= 之一]
由于OP使用的包含标准是算术小于测试，我们建议使用 (#<)/3 用于将二分法具体化为 true 或 false 之一。

考虑以下问题的答案：

?- 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.

请注意，对于所有要选择的项目，Ord = (<) 和 B = true 都成立。

这是三个非dcg solutions based on clpfd的并排比较：

左图在 <、= 和 > 三种情况下使用 zcompare/3 和第一个参数索引。
中间的在true和false这两种情况下使用(#<)/3和第一个参数索引。
右边的是(#<)/3结合if_/3。

注意我们不需要在右栏定义辅助谓词！

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).   %                              %

接下来，让我们使用dcg！

在右栏中我们使用 if_//3 而不是 if_/3.
注意 dcg 和非 dcg 解决方案的不同参数顺序：less_than([1,2,3],Zs,3) vs phrase(less_than([1,2,3],3),Zs).

以下dcg实现对应于上述非dcg代码：

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_(>,_) --> [].      %                              %

好的！把最好的留到最后...只需使用 meta-predicate tfilter/3 together with (#>)/3!

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

Answer 7

dcg variant in 是我们的起点。

考虑辅助非终结符ord_lt_//2:

ord_lt_(<,Z) --> [Z].
ord_lt_(=,_) --> [].
ord_lt_(>,_) --> [].

可以使用两个条件涵盖这三个子句：

Ord = (<)：项目应该包含在内。
dif(Ord, (<))：应该不包含。

我们可以使用 if_//3 来表达这个 "either-or choice":

less_than([],_) --> [].
less_than([Z|Zs],X) -->
   { zcompare(Ord,Z,X) },
   if_(Ord = (<), [Z], []),
   less_than(Zs,X).

因此ord_lt_//2变得多余。

净收益？ 3 lines-of-code !-)

列表中小于给定数字的数字

Numbers in a list smaller than a given number

list

prolog

使用`( if -> then ; else )`

"Declarative"解决方案

一种不同的方法

列表中小于给定数字的数字

Numbers in a list smaller than a given number

list

prolog

使用( if -> then ; else )

"Declarative"解决方案

一种不同的方法

使用`( if -> then ; else )`