CODEWITHSUNDEEP
listprolog
PEREZje
PEREZje

Reputation: 2492

Prolog - How to remove N number of members from a list

So I'm making a predicate called removeN(List1, N, List2). It should basically function like this:

removeN([o, o, o, o], 3, List2).

List2 = [o].

The first argument is a list with a number of the same members ([o, o, o] or [x, x, x]). The second argument is the number of members you wanna remove, and the third argument is the list with the removed members.

How should I go about this, I was thinking about using length of some sort.

Thanks in advance.

Upvotes: 2

Views: 1653

Answers (5)

Oshan Muththettupita
Oshan Muththettupita

Reputation: 1

This works for me. I think this is the easiest way to do this. trim(L,N,L2). L is the list and N is number of elements.

trim(_,0,[]).
trim([H|T],N,[H|T1]):-N1 is N-1,trim(T,N1,T1).

Upvotes: 0

code_x386
code_x386

Reputation: 798

Alternative solution using foldl/4:

remove_step(N, _Item, Idx:Tail, IdxPlusOne:Tail) :-
    Idx < N, succ(Idx, IdxPlusOne).
remove_step(N, Item, Idx:Tail, IdxPlusOne:NewTail) :-
    Idx >= N, succ(Idx, IdxPlusOne),
    Tail = [Item|NewTail].

remove_n(List1, N, List2) :-
    foldl(remove_step(N), List1, 0:List2, _:[]).

The idea here is to go through the list while tracking index of current element. While element index is below specified number N we essentially do nothing. After index becomes equal to N, we start building output list by appending all remaining elements from source list.

Not effective, but you still might be interested in the solution, as it demonstrates usage of a very powerful foldl predicate, which can be used to solve wide range of list processing problems.

Upvotes: 2

tas
tas

Reputation: 8140

Think about what the predicate should describe. It's a relation between a list, a number and a list that is either equal to the first or is missing the specified number of the first elements. Let's pick a descriptive name for it, say list_n_removed/3. Since you want a number of identical elements to be removed, let's keep the head of the list for comparison reasons, so list_n_removed/3 is just the calling predicate and another predicate with and additional argument, let's call it list_n_removed_head/4, describes the actual relation:

list_n_removed([X|Xs],N,R) :-
   list_n_removed_head([X|Xs],N,R,X).

The predicate list_n_removed_head/4 has to deal with two distinct cases: either N=0, then the first and the third argument are the same list or N>0, then the head of the first list has to be equal to the reference element (4th argument) and the relation has to hold for the tail as well:

list_n_removed_head(L,0,L,_X).
list_n_removed_head([X|Xs],N,R,X) :-
   N>0,
   N0 is N-1,
   list_n_removed_head(Xs,N0,R,X).

Now let's see how it works. Your example query yields the desired result:

?- list_n_removed([o,o,o,o],3,R).
R = [o] ;
false.

If the first three elements are not equal the predicate fails:

?- list_n_removed([o,b,o,o],3,R).
false.

If the length of the list equals N the result is the empty list:

?- list_n_removed([o,o,o],3,R).
R = [].

If the length of the list is smaller than N the predicate fails:

?- list_n_removed([o,o],3,R).
false.

If N=0 the two lists are identical:

?- list_n_removed([o,o,o,o],0,R).
R = [o, o, o, o] ;
false.

If N<0 the predicate fails:

?- list_n_removed([o,o,o,o],-1,R).
false.

The predicate can be used in the other direction as well:

?- list_n_removed(L,0,[o]).
L = [o] ;
false.

?- list_n_removed(L,3,[o]).
L = [_G275, _G275, _G275, o] ;
false.

However, if the second argument is variable:

?- list_n_removed([o,o,o,o],N,[o]).
ERROR: >/2: Arguments are not sufficiently instantiated

This can be avoided by using CLP(FD). Consider the following changes:

:- use_module(library(clpfd)).              % <- new

list_n_removed([X|Xs],N,R) :-
   list_n_removed_head([X|Xs],N,R,X).

list_n_removed_head(L,0,L,_X).
list_n_removed_head([X|Xs],N,R,X) :-
   N #> 0,                                  % <- change
   N0 #= N-1,                               % <- change
   list_n_removed_head(Xs,N0,R,X).

Now the above query delivers the expected result:

?- list_n_removed([o,o,o,o],N,[o]).
N = 3 ;
false.

As does the most general query:

?- list_n_removed(L,N,R).
L = R, R = [_G653|_G654],
N = 0 ;
L = [_G653|R],
N = 1 ;
L = [_G26, _G26|R],
N = 2 ;
L = [_G26, _G26, _G26|R],
N = 3 ;
.
.
.

The other queries above yield the same answers with the CLP(FD) version.

Upvotes: 3

lurker
lurker

Reputation: 58244

Another approach would be to use append/3 and length/2:

remove_n(List, N, ShorterList) :-
    length(Prefix, N),
    append(Prefix, ShorterList, List).

Upvotes: 4

Armatorix
Armatorix

Reputation: 1128

Counting down should work fine

removeN([],K,[]) :- K>=0.
removeN(X,0,X).
removeN([_|R],K,Y) :- K2 is K-1, removeN(R,K2,Y).

Upvotes: 1

Related Questions