Excluding all occurrences of the minimum number in

Question

As a Prolog newbie, I try to define a predicate filter_min/2 which takes two lists to determine if the second list is the same as the first, but with all occurrences of the minimum number removed.

Sample queries with expected results:

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

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

I tried but I always get the same result: false. I don't know what the problem is. I need help!

Here is my code:

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

There are a couple of problems with your code:

• filter([],[],0). will not unify when working with any list that does not have 0 as its minimum value, which is not what you want. You want it to unify regardless of the minimum value to end your recursion.
• The way you wrote filter([H1|T1],[H2|T2],Z) and its body will make it so that the two lists always have the same number of elements, when in fact the second one should have at least one less.

A correct implementation of filter/3 would be the following:

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

A bounty was offered...

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

Here's a candidate implementation handling integer values, built on 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).

Some sample queries:

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

Now, some queries terminate even though both list lengths are unknown:

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

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

Note that the implementation doesn't always finitely fail (terminate) in cases that are logically false:

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

Answer 3

First, we can get the minimum number using the predicate list_minnum/2:

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

We can define list_minnum/2 like this:

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

For the sake of completeness, here's the super-similar 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).

Next, we use meta-predicate tfilter/3 in tandem with dif/3 to exclude all occurrences of M:

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

Put the two steps together and define min_excluded/2:

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

Let's run some queries!

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

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

Answer 4

For a Prolog newbie, better start with the basics. The following works when first argument is fully instantiated, and the second is an uninstantiated variable, computing the result in one pass over the input list.

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