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

What if the minimum occurs more than once in the given list, like in `[3,2,7,2,8,2]`? — repeat, Jul 29 '15 at 20:52
in SWI-Prolog, `filter_min(L,N) :- min_list(L,M),delete(L,M,N).`, but @Fatalize answer is better if you are going to learn Prolog — CapelliC, Jul 30 '15 at 06:54
Promise: Will put a bounty for a pure solution that terminates for (certain) cases where neither the length of the first nor of the second argument is known. (Please remind me should I forget it, these 48h time spans are pretty long) — false, Jul 30 '15 at 13:55
@false. Please provide more information on the particular solution you seek with the bounty: Does it have to deal with floats (and other non-integer numbers), too? May it use [tag:prolog-coroutining]? May it use / should it use [tag:clpfd]? What about determinism? Do you mean "pure from the outside" when you demand a "pure" solution? — repeat, Aug 01 '15 at 15:58

score 4 · Accepted Answer · answered Jul 29 '15 at 08:15

4

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

answered Jul 29 '15 at 08:15

Fatalize

3,513
15
25

you are right, filter([],[],0) does't make sense. I find another question, I call function `min_list ` before ` \+number` so I will get an error before goes to my own error check. Is there any way for me to check and stop before call the `min` function. – G_cy Jul 29 '15 at 23:43
@G_cy you can use [`min_member(X,Min)`](http://www.swi-prolog.org/pldoc/man?predicate=min_member/2) before min_list, and check that `number(Min)` is true, before calling min_list. Don't forget to accept this answer if this solved your problems – Fatalize Jul 30 '15 at 06:02
2

`E = 2, filter([1],[1],E).` succeeds, but `filter([1],[1],E), E = 2.` incorrectly fails. It should: either succeed, or produce an instantiation error, or (not here, but in principle) loop. – false Jul 30 '15 at 14:53
@false Adding the rule `filter([],L,_) :- L \= [], !.` fixes the case were the number to remove is not in the first list. The case where the second list is longer than the first list can easily be taken care of by failing if the length of the second list is longer than the length of the first list. – Fatalize Jul 30 '15 at 15:45
2

I cannot see what your suggested fix would improve: You either need an instantiation error or correct success – false Jul 30 '15 at 16:06

score 3 · Answer 2 · answered Aug 03 '15 at 07:12

3

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

answered Aug 03 '15 at 07:12

repeat

18,496
4
54
166

@false. Indeed, but I see no alternative to meeting the bounty-objective. – repeat Aug 07 '15 at 13:30
It is not only choice-point un-friendly but leads to all kinds of anomalous behaviour for lists like `[0*1,1*0,-1,-1*1]` – false Aug 07 '15 at 13:33
`filter_min([1,2,3,4],[3,2,4]).` fails but `filter_min([1,2,3,4],[2,3,4]).` succeeds? – Will Ness Aug 07 '15 at 14:21
@Will: But that's a feature! – false Aug 07 '15 at 14:49
@WillNess. The OP stated "takes two lists to determine if the second list is the same as the first, but with all occurrences of the minimum number removed." – repeat Aug 07 '15 at 15:30
@repeat ah, so "same" meant with ordering too, not only membership. OK, thanks. – Will Ness Aug 07 '15 at 15:52

score 2 · Answer 3 · edited May 23 '17 at 10:31

2

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

edited May 23 '17 at 10:31

Community

1
1

answered Jul 30 '15 at 11:13

repeat

18,496
4
54
166

2

~ : `min_list/2` is not very pure – false Jul 30 '15 at 13:10
2

Also the argument order/name is bad. `list_min` would be better. – false Jul 30 '15 at 13:56
I'm not sure a "newbie in Prolog" is looking for a solution that uses meta-predicates for such a simple task. – Fatalize Jul 30 '15 at 14:04
@Fatalize. Granted. OTOH, meta-predicates enable people to solve the task at hand **before** they master the ins-and-outs of recursion. – repeat Jul 30 '15 at 14:37
@Fatalize: Can you provide a solution that gives correct answers and does not use meta-predicates? This would be a constructive contribution. – false Jul 30 '15 at 14:47
2

Its just an ill-defined predicate. Consider: `min_list([1+1],Y).` succeeds with `Y = 1+1` but `min_list([1+1,1+1],Y).` succeeds with `Y = 2`. – false Jul 30 '15 at 15:24
1

Why do you insist on `min_excluded([X,Y],Zs)` to produce an instantiation errror? It could produce clean and correct answers! (At least when restricting one to integers) – false Jul 30 '15 at 16:08
@false. U r right! OTOH I wasn't sure if the OP was dealing with integers, or with floats, too. – repeat Jul 30 '15 at 16:09
1

@repeat element in the first list should be a number. integers, floats, or others. It should not be a string. – G_cy Jul 30 '15 at 18:22

score 2 · Answer 4 · answered Aug 07 '15 at 16:07

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

Excluding all occurrences of the minimum number in a list

4 Answers4

Linked