Исключая все вхождения минимального числа в список

Как новичок в 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).

Ответы

Ответ 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).

Ответ 2

Была предложена щедрость...

... для чистого решения, которое заканчивается для (определенных) случаев, когда неизвестна ни длина первого, ни второго аргумента.

Здесь целая ценность реализации реализации реализации, построенная на 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

Ответ 3

Сначала мы можем получить минимальное число, используя предикат 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 в тандеме с 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].

Ответ 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).