排除列表中出现的所有最小值

Question

作为 Prolog 新手，我尝试定义一个谓词 filter_min/2，它接受两个列表来确定第二个列表是否与第一个列表相同，但删除所有出现的最小值。

具有预期结果的示例查询：

?- filter_min([3,2,7,8], N).
N = [3,7,8].

?- filter_min([3,2,7,8], [3,7,8]).
true.

我试过了，但总是得到相同的结果：false。我不知道是什么问题。我需要帮助！

这是我的代码：

filter_min(X,Y) :-
    X == [],
    write("ERROR: List parameter is empty!"),
    !;
    min_list(X,Z),
    filter(X,Y,Z).

filter([],[],0).
filter([H1|T1],[H2|T2],Z) :-
    \+ number(H1),
    write("ERROR: List parameter contains a non-number element"),
    !;
    H1 \= Z -> H2 is H1, filter(T1,T2,Z);
    filter(T1,T2,Z).

Answer 1

您的代码有几个问题：

filter([],[],0). 在处理任何不以 0 作为其最小值的列表时不会统一，这不是您想要的。无论最小值如何，您都希望它统一以结束递归。
您编写 filter([H1|T1],[H2|T2],Z) 的方式及其正文将使两个列表始终具有相同数量的元素，而实际上第二个列表至少应少一个。

filter/3 的正确实现如下：

filter([],[],_).
filter([H1|T1],L2,Z):-
    \+ number(H1),
    write("ERROR: List parameter contains a non-number element"),
    !;
    H1 \= Z -> filter(T1,T2,Z), L2 = [H1|T2];
    filter(T1,L2,Z).

Answer 2

首先，我们可以使用谓词list_minnum/2:

得到最小数

?- list_minnum([3,2,7,8],M).
M = 2.

我们可以这样定义list_minnum/2：

list_minnum([E|Es],M) :-
   V is E,
   list_minnum0_minnum(Es,V,M).

list_minnum0_minnum([],M,M).
list_minnum0_minnum([E|Es],M0,M) :-
   M1 is min(E,M0),
   list_minnum0_minnum(Es,M1,M).

为了完整起见，这里是超级相似的list_maxnum/2：

list_maxnum([E|Es],M) :-
   V is E,
   list_maxnum0_maxnum(Es,V,M).

list_maxnum0_maxnum([],M,M).
list_maxnum0_maxnum([E|Es],M0,M) :-
   M1 is max(E,M0),
   list_maxnum0_maxnum(Es,M1,M).

接下来，我们使用 meta-predicate tfilter/3 in tandem with dif/3 来排除所有次出现的 M:

?- M=2, tfilter(dif(M),[2,3,2,7,2,8,2],Xs).
Xs = [3,7,8].

把这两个步骤放在一起定义min_excluded/2:

min_excluded(Xs,Ys) :-
   list_minnum(Xs,M),
   tfilter(dif(M),Xs,Ys).

让我们运行一些查询！

?- min_excluded([3,2,7,8],Xs).
Xs = [3,7,8].

?- min_excluded([3,2,7,8,2],Xs).
Xs = [3,7,8].

Answer 3

提供赏金...

... for a pure solution that terminates for (certain) cases where neither the length of the first nor of the second argument is known.

这是一个处理整数值的候选实现，构建于 clpfd:

:- use_module(library(clpfd)).

filter_min(Xs,Ys) :-
   filter_min_picked_gt(Xs,_,false,Ys).

filter_min_picked_gt([]    ,_,true  ,[]).
filter_min_picked_gt([Z|Xs],M,Picked,[Z|Zs]) :-
   Z #> M,
   filter_min_picked_gt(Xs,M,Picked,Zs).
filter_min_picked_gt([M|Xs],M,_,Zs) :-
   filter_min_picked_gt(Xs,M,true,Zs).

一些示例查询：

?- filter_min([3,2,7,8],[3,7,8]).
true ; false.                        % correct, but leaves choicepoint

?- filter_min([3,2,7,8],Zs).
Zs = [3,7,8] ; false.                % correct, but leaves choicepoint

现在，即使两个列表的长度都未知，一些查询也会终止：

?- filter_min([2,1|_],[1|_]).
false.                               % terminates

?- filter_min([1,2|_],[3,2|_]).
false.                               % terminates

请注意，在逻辑错误的情况下，实现不会总是最终失败（终止）：

?- filter_min([1,2|_],[2,1|_]).      % does _not_ terminate

Answer 4

对于 Prolog 新手，最好从基础开始。当第一个参数被完全实例化时，以下工作，第二个是一个未实例化的变量，计算一次输入列表的结果。

% remmin( +From, -Result). 

% remmin([],[]).              % no min elem to remove from empty list
remmin([A|B], R):- 
  remmin(B, A, [A], [], R).   % remove A from B to get R, keeping [A]
                              % in case a smaller elem will be found

remmin([C|B], A, Rev, Rem, R):-  
  C > A -> remmin(B, A, [C|Rev], [C|Rem], R) ;
  C==A  -> remmin(B, A, [C|Rev],    Rem,  R) ;
  C < A -> remmin(B, C, [C|Rev],    Rev,  R).

remmin([], _, _, Rem, R) :- reverse(Rem, R).

排除列表中出现的所有最小值

Excluding all occurrences of the minimum number in a list

list

prolog