How to implement list item deletion for all argument modes?

Question

The following Prolog program defines a predicate deleted/3 for deleting all the occurrences of the item passed in first argument from the list passed in second argument and results in the list passed in third argument:

deleted(_, [], []).
deleted(X, [X|Y], Z) :-
  deleted(X, Y, Z).
deleted(U, [V|W], [V|X]) :-
  deleted(U, W, X),
  U \= V.

It works with queries in this argument mode:

?- deleted(a, [a, b, a], [b]).
   true
;  false.

It also works with queries in this argument mode:

?- deleted(X, [a, b, a], [b]).
   X = a
;  false.

It also works with queries in this argument mode:

?- deleted(a, [a, b, a], Z).
   Z = [b]
;  false.

It also works with queries in this argument mode:

?- deleted(X, [a, b, a], Z).
   X = a, Z = [b]
;  X = b, Z = [a, a]
;  false.

It also works with queries in this argument mode:

?- deleted(a, Y, Z).
   Y = Z, Z = []
;  Y = [a], Z = []
;  Y = [a, a], Z = []
;  Y = [a, a, a], Z = []
;  Y = [a, a, a, a], Z = []
;  …

It also works with queries in this argument mode:

?- deleted(X, Y, Z).
   Y = Z, Z = []
;  Y = [X], Z = []
;  Y = [X, X], Z = []
;  Y = [X, X, X], Z = []
;  Y = [X, X, X, X], Z = []
;  …

But it exhausts resources with queries in this argument mode:

?- deleted(a, Y, [b]).
Stack limit (0.2Gb) exceeded
  Stack sizes: local: 0.2Gb, global: 28.1Mb, trail: 9.3Mb
  Stack depth: 1,225,203, last-call: 0%, Choice points: 1,225,183
  Possible non-terminating recursion:
    [1,225,203] deleted(a, _1542, [length:1])
    [1,225,202] deleted(a, [length:1|_1584], [length:1])

It also exhausts resources with queries in this argument mode:

?- deleted(X, Y, [b]).
Stack limit (0.2Gb) exceeded
  Stack sizes: local: 0.2Gb, global: 28.1Mb, trail: 9.3Mb
  Stack depth: 1,225,179, last-call: 0%, Choice points: 1,225,159
  Possible non-terminating recursion:
    [1,225,179] deleted(_1562, _1564, [length:1])
    [1,225,178] deleted(_1596, [length:1|_1606], [length:1])

How to implement list item deletion for all argument modes?

It doesn't really work in `deleted(a, Y, Z)` and `deleted(X, Y, Z)` modes either. If it works, queries like this should succeed: `deleted(a, Y, Z), Y = [a, b, a], Z = [b].` — rajashekar, Aug 23 '21 at 06:25
Are you looking for one main predicate that determines the mode by inspecting the the input and then picking one of a few support predicates or are you looking for a single predicate that uses dif/2 or constraints or something similar? In other words what is the reason you want the predicate to do this? Are you going down the rabbit hole because you can? — Guy Coder, Aug 23 '21 at 11:13
@GuyCoder I am looking for the latter. I would like to avoid metalogic. — Géry Ogam, Aug 23 '21 at 12:47
@GuyCoder I don’t know for `dif/2` but I would like to avoid testing the type of the arguments with `var/1`, `nonvar/1`, or `ground/1`. In other words, I would like a purely declarative solution like [this one](https://stackoverflow.com/a/68851927/2326961), not like [this one](https://stackoverflow.com/a/68864099/2326961). — Géry Ogam, Aug 23 '21 at 14:06
So then `deleted(a,L,[])` could result in an infinite list? Think about it. Is that what you really want. — Guy Coder, Aug 23 '21 at 14:19
For `deleted(a,L,[b,c])` where should `a` be inserted? In the front, end, middle, randomly? Basically for each insert there are multiple combinations of answers. Which one is correct according to your specification? — Guy Coder, Aug 24 '21 at 09:48
On interest: [select/3](https://www.swi-prolog.org/pldoc/man?predicate=select/3) It is similar to your question but does not create infinite list. It will only add the single item once and then the query is considered solved. — Guy Coder, Aug 24 '21 at 09:50
FYI. I am not trying to solve this, I am just curious to see if an acceptable solution is posted that covers all of the possible conditions. Thus the questions about the possible conditions and solutions. Personally I would use select/3 in real world code and be satisfied unless there was a need for what you seek. — Guy Coder, Aug 24 '21 at 09:54
Perhaps you should reconsider the question `How to implement list item deletion for all argument modes?` Is what you seek really `deletion`? In other modes it is not deletion but insertion or even relationships as you saw with `Y = [X, X, X]`. — Guy Coder, Aug 24 '21 at 10:21
@false [SWISH](https://swish.swi-prolog.org/) does not use semicolons to separate answers because it uses background color for this role. But thanks for adding them as we do not have that visual clue on Stack Overflow. However you did not add indentation for single answers, was it on purpose? — Géry Ogam, Aug 25 '21 at 06:43
@Maggyero: SWI under Linux does produce the semicolons but they are put at the end of the line which suggests to beginners that the semicolon means something similar to C/C++/Java etc. As for the indentation otherwise: No, not really. As for the toplevel alone, Scryer has the nicest indentation. — false, Aug 25 '21 at 06:47
@GuyCoder ‘For `deleted(a,L,[b,c])` where should `a` be inserted? In the front, end, middle, randomly?’ Front, end, middle, combinations of these, and repetitions of these. — Géry Ogam, Aug 25 '21 at 06:49
@false Alright. I have just added indentation everywhere and used three-space indentation to align answers with queries, like in the README of [Scryer Prolog](https://github.com/mthom/scryer-prolog). Also I like the empty lines between answers that you used, it is easier to read than Scryer Prolog output which stacks answers without blank space, so I kept your version. — Géry Ogam, Aug 25 '21 at 07:08
While StackOverflow is not the best place to learn Prolog, answers by selected users are worthy of studying. For this question the answers by [repeat](https://stackoverflow.com/users/4609915/repeat) for `list` and `purity` are of value. Here is a [search](https://stackoverflow.com/search?q=user%3A4609915+%5Bprolog%5D+%5Blist%5D+is%3Aanswer) I used. It does have some answer that are off topic but better to grab more than remove something that is of value. continued. — Guy Coder, Aug 25 '21 at 11:04
I would note that the tag [logical-purity](https://stackoverflow.com/questions/tagged/logical-purity) should be on the answers you seek but sally it is missing from many. — Guy Coder, Aug 25 '21 at 11:06
Are you aware of how close your code is to this [answer](https://stackoverflow.com/a/55030527/1243762) - #4 in list? — Guy Coder, Aug 25 '21 at 11:18
@GuyCoder Thanks for the links. My program is the same as program #4 in repeat’s answer, except that I am using `\=/2` instead of `dif/2`, but it does not make a difference: both programs exhausts resources for the last two queries in this post. — Géry Ogam, Aug 25 '21 at 12:54
`a solution has been posted` I see but it did not pass your requirement. From earlier comments. My clarification, `For deleted(a,L,[b,c]) where should a be inserted?` In the front, end, middle, randomly? Your requirement `Front, end, middle, combinations of these, and repetitions of these.` As it is your question you can move the goal post. — Guy Coder, Aug 29 '21 at 13:23
@GuyCoder It passes my requirements. But you cannot see it from the first solutions where `a` is inserted at the front since there is an infinity of these front solutions, before the middle and end solutions are generated. — Géry Ogam, Aug 29 '21 at 13:29
`But you cannot see it from the first solutions where a is inserted at the front since there is an infinity of these front solutions, before the middle and end solutions are generated.` I agree. Perhaps the answer should note using, `length(L,N),deleted(a,L,[b,c]).` I don't plan to add another answer with that detail but hopefully @repeat will modify his answer mentioning that. — Guy Coder, Aug 29 '21 at 13:35
Do you plan on adding logical-purity as a tag to your question? — Guy Coder, Aug 29 '21 at 13:36
@GuyCoder `length(L, N), deleted(a, L , [b, c]).` Excellent remark, I did not think about adding a length constraint to generate solutions in a specific order (by length). Let’s ask repeat what he thinks about this. — Géry Ogam, Aug 29 '21 at 18:02
@GuyCoder My question was not specifically about logical purity but about non termination. However it turns out the solution involves using logically pure predicates, so yes, I am adding this tag. Thanks for the suggestion! — Géry Ogam, Aug 29 '21 at 18:03
For `Let’s ask repeat what he thinks about this.`, since you have accepted an answer, it would be proper StackOverflow etiquette to ask a new question and reference this one. That way you and repeat can also gain more points. :) — Guy Coder, Aug 29 '21 at 18:31

score 4 · Accepted Answer · edited Aug 29 '21 at 12:46

Intro

Pure Prolog conjunctions and disjunctions are, in fact, commutative and associative.

This allows us to ignore clause and goal order, provided that all answer sequences are finite.

When queries have infinite solution sets, Prolog may need to systematically enumerate infinite answer sequences.

The fix

To help Prolog find answers for above “problematic” queries, swap the two recursive rules:

deleted(_,[],[]).
deleted(U,[V|W],[V|X]) :-  % this clause was last
   dif(U,V),
   deleted(U,W,X).
deleted(X,[X|Y],Z) :-
   deleted(X,Y,Z).

Demo

Let’s run your queries again with above code changes!

The finite ones work like before¹:

?- deleted(a,[a,b,a],[b]).         % Q1
   true
;  false.

?- deleted(X,[a,b,a],[b]).         % Q2
   X = a
;  false.

?- deleted(a,[a,b,a],Z).           % Q3
   Z = [b]
;  false.

?- deleted(X,[a,b,a],Z).           % Q4
   Z = [a,b,a], dif(X,a), dif(X,b)
;  Z = [a,  a],               X=b
;  Z = [  b  ],     X=a
;  false.

Some infinite ones were okay before—they still are:

?- deleted(a,Y,Z).                 % Q5
   Y = Z, Z = []
;  Y = Z, Z = [_A],       dif(_A,a)
;  Y = Z, Z = [_A,_B],    dif(_A,a), dif(_B,a)
;  Y = Z, Z = [_A,_B,_C], dif(_A,a), dif(_B,a), dif(_C,a)
;  …

?- deleted(X,Y,Z).                 % Q6
   Y = Z, Z = []
;  Y = Z, Z = [_A],       dif(X,_A)
;  Y = Z, Z = [_A,_B],    dif(X,_A), dif(X,_B) 
;  Y = Z, Z = [_A,_B,_C], dif(X,_A), dif(X,_B), dif(X,_C)
;  …

Some infinite ones used to be “problematic”—not anymore:

?- deleted(a,Y,[b]).               % Q7
   Y = [b]
;  Y = [b,a]
;  Y = [b,a,a]
;  Y = [b,a,a,a]
;  …

?- deleted(X,Y,[b]).               % Q8
   Y = [b],         dif(X,b)
;  Y = [b,X],       dif(X,b)
;  Y = [b,X,X],     dif(X,b)
;  Y = [b,X,X,X],   dif(X,b)
;  Y = [b,X,X,X,X], dif(X,b)
;  …

Analysis

Now, ?- deleted(X,Y,[b]). makes Prolog give us answers.

But why did we run out-of-memory? How come it did not work?

To explain this, let’s take a step back: the default / vanilla / out-of-the-box prolog-toplevel of many² Prolog systems initially runs each query until it discovers either (0) finite failure or (1) the 1st answer³.

Before the fix, we observed neither. Why not?

Why no finite failure?

deleted(a,[a,b,a],[b]) holds true.

Therefore, the more general deleted(X,Y,[b]) must not fail.
Why no (1st) answer?

Prolog proceeds depth-first, top-down, left-to-right.

So when …
```
    ?- deleted(X,Y,[b]).
```
… “meets” …
```
    deleted(X,[X|Y],Z) :-
       deleted(X,Y,Z).
```
… inside the Prolog machine, the following happens:
- A choicepoint is created for saving the information—to be used upon backtracking—that another clause could have been selected.
- Next, Prolog proceeds with a recursive goal which is just like the original one: we are no closer to an answer, as the 3rd argument—the only instantiated one—stays exactly the same.
Eventually, this loop runs out of memory—which is exactly the behavior that you observed.

If we swap two recursive clauses, the following clause becomes our top-most recursive clause:

deleted(U,[V|W],[V|X]) :-
   dif(U,V),
   deleted(U,W,X).

Now, something is going on with the 3rd argument: Prolog recursively walks down the single-linked list until [] (or a free logical variable) is reached. Only then can Prolog make use of the fact deleted(_,[],[]). and give us an answer.

Footnotes:

In fact better, as we preserve logical-purity by using dif/2 for expressing syntactic term inequality.

More on dif/2: prolog-dif
All command-line-interface based Prolog systems I have ever used.
Not stopping at the 1st answer is way better for code quality—particularly in regard to universal termination properties.

GUPU, an excellent environment specialized for Prolog and constraint programming courses, does the right thing—by default!

“Answer substitutions are displayed in chunks of five.”

GuyCoder made an excellent remark: the query `deleted(a, Y, [b, c]).` returns solutions *by position*: `Y = [b, c]; Y = [b, c, a]; Y = [b, c, a, a]; Y = [b, c, a, a, a]; Y = [b, c, a, a, a, a]; …`, while the query `length(Y, _), deleted(a, Y, [b, c]).` returns solutions *by length*: `Y = [b, c]; Y = [b, c, a]; Y = [b, a, c]; Y = [a, b, c]; Y = [b, c, a, a]; Y = [b, a, c, a]; Y = [b, a, a, c]; Y = [a, b, c, a]; Y = [a, b, a, c]; Y = [a, a, b, c]; …`, which is a nicer ordering. Should the predicate `length/2` be included in the predicate `deleted/3`, or should it be left outside in queries? — Géry Ogam, Aug 29 '21 at 18:18
@Maggyero. I took me a moment to grasp what you actually meant when you wrote (1) "by position" and (2) "by length" :-) Both are usually referred to as "search algorithms" or "*search strategies*": (1) is called [*depth-first search* with chronological backtracking](https://en.wikipedia.org/wiki/Depth-first_search). (2) is called [*iterative deepening* depth-first search](https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search). Want to know more? If so, summon the Power of Prolog and read the chapter [Sorting and Searching with Prolog](https://www.metalevel.at/prolog/sorting)! — repeat, Aug 29 '21 at 21:30
@Maggyero. I'd rather leave it out, document the behavior and implementation limitations, and use iterative deepening only when needed. YMMV! — repeat, Aug 29 '21 at 22:35

How to implement list item deletion for all argument modes?

1 Answers1

Intro

The fix

Demo

Analysis

Linked