How to delete from a list the 1st, 2nd ,4th and 8th elements in Prolog

Question

I want to delete from a list the first, second, 4th and 8th element. How can I do? I tried this:

 del([],[]).
 del([H1,H2,H3,H4|T],[H3|T]).

And it works but how can I do it recursively, not to write 8 elements in order to delete the positions that I want?

I think the answer depends upon how you would want to generalize the problem. Jay's answer assumes you want a totally general solution in which you're given a list of indices for elements to remove. Paulo's solution is more literal for a fixed set of indices. A third option would be you're wanting to remove element `n` if `n` is a power of 2. The 1st and 3rd options would use recursion, but the 2nd doesn't require it. So in what way do you want to define *the positions that I want*? — lurker, Nov 05 '15 at 13:43

score 3 · Answer 1 · answered Nov 05 '15 at 12:13

3

Unification is your friend:

delete_one_two_four_eight_elements(
    [_, _, Third, _, Five, Six, Seven, _| Rest],
    [Third, Five, Six, Seven| Rest]
).

answered Nov 05 '15 at 12:13

Paulo Moura

18,373
3
23
33

If I understand correctly, the Original poster wanted a recursive solution, not enumerating each nth element (presumably so it would be possible to use with different sets of indices), but I could be wrong... – Jay Nov 05 '15 at 16:13

score 1 · Answer 2 · edited May 23 '17 at 12:29

The general solution, if indices are given as an increasing list of values, could also be done with a DCG:

del([C|Ns], C, Xs) --> [_], { C1 #= C + 1 }, del(Ns, C1, Xs).
del([N|Ns], C, [X|Xs]) --> [X], { N #\= C, C1 #= C + 1 }, del([N|Ns], C1, Xs).
del([], _, Xs) --> rest(Xs).
del(_, _, []) --> [].     % ***

rest([]) --> [].
rest([X|T]) --> [X], rest(T).

delete_indices(Indices, List, Result) :-
    phrase(del(Indices, 1, Result), List).

With the clause *** included above, indices which are beyond the length of the list are ignored:

| ?- delete_indices([1,3,5,12], [a,b,c,d,e,f,g], L).

L = [b,d,f,g] ? ;

no
| ?-

If you omit the *** clause, then queries that have an index beyond the list length will fail, so the above query would fail (since there is no 12th element), but lists with exclusively existing indices will work:

| ?- delete_indices([1,3,5], [a,b,c,d,e,f,g], L).

L = [b,d,f,g] ? ;

no
| ?-

Note that a deterministic solution can be achieved using if_//3.

Jay · Answer 3 · 2015-11-05T11:00:50.957

So... What about writing one predicate that deletes the nth element, then one that takes a list of indices and deletes all those?

Deleting the nth is simple:

del([_|T],T,1).
del([Head|Tail],B,N) :-
    K is N-1,
    del(Tail,C,K),
    B = [Head|C].

Since we know that N is not 1 (otherwise the first clause would have been used), we keep the first (see that B=[Head|C], we did not throw Head away!) and do a recursive call to del(Tail,C,K) to determine C with the nth removed.

Now, for listdel, that takes a list of indices:

listdelaux(A,A,[],_).
listdelaux(A,B,Indices,Level) :-
    Indices = [N|IndicesTail],
    K is N-Level,
    del(A,X,K),
    L is Level + 1,
    listdelaux(X,B,IndicesTail,L).

listdel(A,B,Indices) :- listdelaux(A,B,Indices,0).

The listdelaux predicate takes four arguments: The original list, the new list, the list of indices, and the level, which in the first call should be zero. It will remove the first index; then call itself again for the next index, but in the new call it should subtract from the new index to be removed the number of indices already removed:

Removing [2,4] from [a,b,c,d,e,f]:

[a,b,c,d,e,f] --> del(.,.,2) --> [a,c,d,e,f]

[a,c,d,e,f] --> del(.,.,3) --> [a,c,e,f]

See that we had to subtract 1 from 4 in the second call.

How to delete from a list the 1st, 2nd ,4th and 8th elements in Prolog

3 Answers3