Trying to implement a delete_all/3 relation but it does not terminate in some case

Help!
1

I’m using: SWI-Prolog version 8.2.1

delete_all(X,L1,L2) represent the relation of removing all occurences of X from L1 resulting in L2

list_rem(_,[],[]).
list_rem(Z,[X|Xs],[X|Ys]) :- dif(Z,X), list_rem(Z,Xs,Ys).
list_rem(X,[X|Xs],Ys):- list_rem(X,Xs,Ys).

% list_rem(0,[0,1,2,0],[1,2]). => true
% list_rem(3,[1,2,3,2,3,4],X) => X = [1,2,2,4].
% list_rem(0,X,[1,2]). => does not terminate

Any help will be appreciated, I’m just starting to learn prolog, i have a bit of experience in logic programing with mini-kanren (in clojure).

2

Since this looks like homework I won’t go into details or even check this suggestion.

See:
library(apply): Apply predicates on a list
Package “list_util” - Predicates for working with lists

If this is not homework let me know and I will add more detail. :grinning:

3

it is not homework, just curiosity :slight_smile:

4

Do you need more help or you will let us know?

5

Thank you for the links and the quick response!
Those libraries look interesting
Maybe I should mention that I would like this predicate to work in both ways
Ideally it would work like delete/3 that can take only variables.
Also maybe I would like to know why it does not terminate in the case I mentioned.
Thank you a lot

6

Let me take a few minutes to write the code. Don’t know if the reverse way will work as you need it.

While I am writing this, also take a look at SWI-Prolog unit test.

7

Here is the code that removes the values with unit test.

remove(X,L1,L2) :-
    exclude(remove(X),L1,L2).

remove(X,Element) :-
    X = Element.

:- begin_tests(remove).

remove_test(success,0,[1,2,3],[1,2,3]).
remove_test(success,1,[1,2,3],[2,3]).
remove_test(success,1,[1,1,2],[2]).
remove_test(success,1,[1,2,1],[2]).
remove_test(success,1,[2,1,1],[2]).

test(remove_success,[forall(remove_test(success,X,L1,Expected_result))]) :-
    remove(X,L1,L2),

    assertion( L2 == Expected_result ).

:- end_tests(remove).

The code above can be refactored/simplified a lot more but I left it as is so that it is easier to understand.

EDIT

Now for the reverse, or at least one way of doing it. The description was not specific enough.
Also this uses a different predicate name; remember that one predicate can call another so I don’t see this as an issue.

add_element(X,L1,L2) :-
    append([X],L1,L0),
    permutation(L0,L2).

:- begin_tests(add_element).

add_element_test(success,0,[1,2],[[0,1,2],[0,2,1],[1,0,2],[1,2,0],[2,0,1],[2,1,0]]).

test(add_element_success,[forall(add_element_test(success,X,L1,Expected_result)),set(L2 == Expected_result )]) :-
    add_element(X,L1,L2).

:- end_tests(add_element).
8

Hi.

This is a very basic exercise, of how to use recursion in order to achive ones goal. This does it:

list_rem(_, [], []).

list_rem(X, [A|As], Bs) :-
    ( 
        X = A
    ->
        list_rem(X, As, Bs)
    ;
        Bs = [A|Bs1],
        list_rem(X, As, Bs1)
    ).

Be sure to check out how this example works.

If you really want it to work in reverse direction too, then it will be a lot more involved. But I don’t see how this would be useful.

Happy hacking,
Volker

9

Thank you a lot @EricGT , unit test library looks nice, I will use it for sure.
But it looks to me that your solution have the same limitation than mine.

% remove(0,X,[1,2,3,4]). does not terminate
10

Thank you for the code, I like this kind of if statement. I think I understand how it works.
But really the reversability is the thing that brings me to Prolog, and in this case I really want to acheive reversability, I am a bit surprised that it “involves a lot more”, may I ask you to show me?

Thank you agin

11

I would not expect it to terminate. X needs to be bound.

Can you give some examples of what the result should be. I am expecting more than one result so you should explain why there is more than one result and/or how the output is the way it is, e.g. is it sorted?

12

maybe results could be ordered like this:

[1,2,3,4]
[0,1,2,3,4]
[1,0,2,3,4]
...
[0,0,1,2,3,4]
[0,1,0,2,3,4]
...
13

That also will never terminate as you don’t limit the number of times the valued being added can be added. In my example using add_element/3 the value is only added once.

14

Hi

For instance, you might have this reverse call of list_rem:

list_rem(0, L, [1,2,3]).

This would mean that all (infinitely many) lists, which get reduced to [1,2,3], would be bound to L, one at a time:

[1,2,3],
[0,1,2,3],
[1,0,2,3],
[0,1,0,2,3],
[0,0,1,2,3],
[0,0,1,0,2,3],
...

You can formulate the forward direction easily (like in the example). But it isn’t easy to do the backwards direction in SLD-resolution. You would possibly do it with some kind meta-interpreter which does a breadth first search. I don’t know a simple, elegant way to do it.

Bye
Volker

15

I know you did not ask me and I don’t have a magical answer for all cases, but one way that may help you get your desired reversible predicate is to think about relationships.

Draw the two sets then connect all the items in one set to and item in the other set such that no item is left unconnected. What are the rules you need to create to make the connections correct and consistent and work both ways? Also what are the rules that define how each set is constructed, these might also be needed in making a reversible relationship.

EDIT

Many reversible predicates in Prolog are really made up of more than one clause. They use guard statements to decide which clause to use. So if one list is larger than another then using < in one guard and > in the other would decide which clause to use.

16

Thank you :slight_smile: I will think about this, it is really interesting to think in terms of relations instead of functions. It will slowly make its way into my head I hope!

1 Like
17

If you want to go down the rabbit hole on one of the main concepts of sets which is Cardinality, then see: Cantor’s diagonal argument

Hopefully you will see the connection between your question and Cantor’s diagonal argument.

I did not understand Cantor’s diagonal argument until I read a chapter in a book that explained it with a few examples. Can’t recall the book at the moment.