Prolog delete an element into a given list

Question

Hello I wish some advice or words about this task:

Define a statement with three parameters where the first one is a list, the second one is an element (atom or list) and the last one is a list which must accomplish it is equal to the first but first's list' elements which match second parameter,are gone.

Examples:

> elimina([f, e, d, [a, h], a, d, a], a, L)

L = [f, e, d, [a, h], d]

> elimina([f, e, d, [ a, h], a, [d, a]], [a, h], L)

L = [f, e, d, a, [d, a]]

I tried:

elimina([],_,[]).
elimina([X],X,[]).
elimina([X],Y,[X]).
elimina([H|T],H,Result) :-
 elimina([T],H,Result).
elimina([H|T],Y,Result):-
 elimina([T],H,Result).

I have the doubt about what to write when I shout the recursive call:

elimina([T],H,Result).

Because first I don't know how differently should be the behave when the input second element matchs the head rather than don't matching the head; so I put the same call. Also I doubt because: Is really needed to put the base case: elimina([X],Y,[X]).? I thought we could pass the exercise with just matching the element to delete with the ones which are really into the list.

Thank you for your time.

`elimina([a],a,[a])` incorrectly succeeds. – false May 09 '17 at 16:39 — false, May 09 '17 at 16:39

false · Accepted Answer · 2022-08-12T09:28:39.377

There is a very general method how you can test your own code in Prolog. Simply ask Prolog to generate via the most general question all possibilities.

?- elimina([], D, Ys).
   Ys = [].                  % 1: nice!
?- elimina([X], D, Ys).
   D = X, Ys = []            % 1: nice!
;  Ys = [X]                  % 2: lacks dif(X, D)
;  X = [], D = [], Ys = []   % 3: correct but subsumed by 1
;  D = X, Ys = [[]]          % 4: incorrect
;  X = [], D = [], Ys = []   % 5: correct but subsumed by 1
;  X = [], D = [], Ys = [[]] % 6: incorrect
;  X = [], D = [], Ys = []   % 7: correct but subsumed by 1
;  ... .

For the empty list everything is fine. But for the one-element list, there are many superfluous answers! Actually, there should only be two answers:

    D = X, Ys = []
;   dif(D, X), Ys = [X].

So now pick some case you want to improve!

Maybe take answer #4 and set D = a, X = a:

?- elimina([a], a, Ys).
   Ys = []        % 1: nice
;  Ys = [a]       % 2: incorrect
;  Ys = [[]]      % 3: incorrect
;  Ys = []        % 4: correct but subsumed by 1
;  Ys = [[]]      % 5: incorrect and subsumed by 3
;  Ys = []        % 6: correct but subsumed by 1
;  ... .

So I will pick #3 which actually should fail, but does not

?- elimina([a],a,[[]]).
   true
;  true
;  ... .

Narrow down the culprit by inserting false and some extra equations:

?- elimina([a],a,[[]]).
   false.

elimina([],_,[]) :- false.
elimina([X],X,[]) :- false.
elimina([X],Y,[X]) :- Y = a, X = [].
elimina([H|T],H,Result) :- false,
   elimina([T],H,Result).
elimina([H|T],Y,Result):- Result =  [[]],
   elimina([T],H,Result).

Now look at what is left and think about it. Should these remaining rules really hold?

In the remaining visible part there must be an error!

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

When describing lists, it's usually worthwhile to consider using DCGs for the task. You could describe the relation like so:

elimina(L1,X,L2) :-              % L2 is described by
   phrase(elimina_x(L1,X),L2).   % elimina_x//2

elimina_x([],_X) -->             % nothing to delete
   [].                           % from the empty list
elimina_x([X|Xs],X)  -->         % if the head of the list equals X
   elimina_x(Xs,X).              % it's not in the list, same for the tail
elimina_x([X|Xs],Y)  -->         % if the head of the list
   {dif(X,Y)},                   % differs from Y
   [X],                          % it is in the list
   elimina_x(Xs,Y).              % same for the tail

Your example queries yield the desired result.

   ?- elimina([f, e, d, [a, h], a, d, a], a, L).
L = [f,e,d,[a,h],d] ? ;
no
   ?- elimina([f, e, d, [ a, h], a, [d, a]], [a, h], L).
L = [f,e,d,a,[d,a]] ? ;
no

Alternatively, you can also express this relation more compactly, using if_/3, (=)/3 and tfilter/3:

dif_t(X,Y,T) :-
   if_(X=Y,T=false,T=true).

elimina(L1,X,L2) :-
   tfilter(dif_t(X),L1,L2).

The above queries yield the same answers with this version.

Prolog delete an element into a given list

2 Answers2