Excluding all occurrences of the minimum number in a list

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