Cutting `cut` from set difference #2507

jjtolton · 2024-08-27T15:56:02Z

jjtolton
Aug 27, 2024

I saw this relationship in a Prolog book:

delete_all([],_,[]).
delete_all([X|L1], L2, Diff) :-
        member(X, L2), !,
        delete_all(L1, L2, Diff).
delete_all([X|L1], L2, [X|Diff]) :-
        delete_all(L1, L2, Diff).

**Edit: ** (updated spacing, appreciated @UWN . Code mistakes remain mine!)

Despite the name delete_all, this is actually supposed to be a "set difference". It currently does not work properly without the cut !/0. I am trying to learn the correct way to write it so that it is correct "in general".

I started the conversation in another discussion but it was getting off track, so I'm moving the discussion here.

@UWN pointed out that he answered a nearly identical question on SO, and I'm working on using membert_d to adapt the answer.

Answered by UWN

Aug 28, 2024

This was the original version.

deleteall([], _X, []).
deleteall([E|Es], X, Ys0) :-
   if_( E = X, Ys0 = Ys, Ys0 = [E|Ys] ),
   deleteall(Es, X, Ys).

?- deleteall([A,B,C,A,C],A,Es).
   A = B, C = A, Es = []
;  A = B, Es = [C,C], dif:dif(C,A)
;  A = C, Es = [B], dif:dif(B,A)
;  Es = [B,C,C], dif:dif(B,A), dif:dif(C,A).

Which only deletes one element X. But we want to delete all elements of Xs. So we have to replace the condition (=)/3 above by a more sophisticated condition.

deletealls([], _Xs, []).
deletealls([E|Es], Xs, Ys0) :-
   if_( memberd_t(E, Xs), Ys0 = Ys, Ys0 = [E|Ys] ),
   deletealls(Es, Xs, Ys).

?- deletealls([A,B,C,A,C],[A],Es).
   A = B, C = A, Es = []
;  A = B, Es = [C,C],…

View full answer

triska · 2024-08-27T16:06:44Z

triska
Aug 27, 2024

It also does not work correctly with the cut. For example:

?-        delete_all([A], "a", As).
   A = a, As = [], unexpected, incomplete.
?- A = b, delete_all([A], "a", As).
   A = b, As = "b". % expected

0 replies

UWN · 2024-08-27T17:21:35Z

UWN
Aug 27, 2024

(Do not use empty lines between clauses of the same predicate. Use empty lines to separate different predicates only.)

0 replies

jjtolton · 2024-08-27T18:58:48Z

jjtolton
Aug 27, 2024
Author

So by "generate and test" I came up with this:

% xs_ts_setdiff(Xs, Ys, Diff): Diff is the elements of Xs without the elements of Ys
xs_ys_setdiff([], _, []).
xs_ys_setdiff([X|Xs], Ys, Diff0) :-
        if_(memberd_t(X, Ys),
            (   
                xs_ys_setdiff(Xs, Ys, Diff0)
            ),
            (
                Diff0=[X|Diff],
                xs_ys_setdiff(Xs, Ys, Diff)
            )
           ).
        
?- xs_ys_setdiff([1, 2, 3], [2, 3, 5], Diff).
%@    Diff = [1].
?- xs_ys_setdiff([1, 2, 3, 4, 3], [3, 5], Diff).
%@    Diff = [1,2,4].
?- length(Xs, _), xs_ys_setdiff(Xs, Ys, Diff).
%@    Xs = [], Diff = []
%@ ;  Xs = [_A], Ys = [], Diff = [_A]
%@ ;  Xs = [_A], Ys = [_A|_B], Diff = []
%@ ;  Xs = [_B], Ys = [_A], Diff = [_B], dif:dif(_A,_B)
%@ ;  Xs = [_B], Ys = [_A,_B|_C], Diff = [], dif:dif(_A,_B)
%@ ;  Xs = [_B], Ys = [_A,_C], Diff = [_B], dif:dif(_A,_B), dif:dif(_C,_B)
%@ ;  Xs = [_B], Ys = [_A,_C,_B|_D], Diff = [], dif:dif(_A,_B), dif:dif(_C,_B)
%@ ;  Xs = [_B], Ys = [_A,_C,_D], Diff = [_B], dif:dif(_A,_B), dif:dif(_C,_B), dif:dif(_D,_B)
%@ ;  ... .

I'm not sure if I'm happy that it seems to work or unhappy because I'm not sure why it works. As an experiment, I set this up:

% xs_ts_setdiff(Xs, Ys, Diff): Diff is the elements of Xs without the elements of Ys
xs_ys_setdiff([], _, []).
xs_ys_setdiff([X|Xs], Ys, Diff) :-
        memberd_t(X, Ys, true),
        xs_ys_setdiff(Xs, Ys, Diff).
xs_ys_setdiff([X|Xs], Ys, [X|Diff]) :-
        memberd_t(X, Ys, false),
        xs_ys_setdiff(Xs, Ys, Diff).

?- xs_ys_setdiff([1, 2, 3], [2, 3, 5], Diff).
%@    Diff = [1]
%@ ;  false.

?- xs_ys_setdiff([1, 2, 3, 4, 3], [3, 5], Diff).
%@    Diff = [1,2,4]
%@ ;  false.

?- length(Xs, N), length(Ys, N), xs_ys_setdiff(Xs, Ys, Diff).
%@    Xs = [], N = 0, Ys = [], Diff = []
%@ ;  Xs = [_A], N = 1, Ys = [_A], Diff = []
%@ ;  Xs = [_B], N = 1, Ys = [_A], Diff = [_B], dif:dif(_A,_B)
%@ ;  Xs = [_A,_A], N = 2, Ys = [_A,_B], Diff = []
%@ ;  Xs = [_A,_B], N = 2, Ys = [_A,_B], Diff = [], dif:dif(_A,_B)
%@ ;  Xs = [_A,_B], N = 2, Ys = [_A,_C], Diff = [_B], dif:dif(_A,_B), dif:dif(_C,_B)
%@ ;  ... .

which seems to work as well, but with redundant choice points. It is very interesting that the two implementations are not identical!

Referring to the top/first implementation of xs_ys_setdiff, this seems like an improvement over delete_all, although some things are very strange to me. I am surprised that there is no checking of Diff! That does result in some strange cases like,

?- length(Ls, _), xs_ys_setdiff([1, 2, 3], Ls, [2, 3, 5]).
%@  nontermination

I feel like if xs_ys_setdiff were working properly, that would return false, as there is no such Ls which could satisfy. Or is this nontermination result to be expected? I imagine there is yet a better way to implement this?

2 replies

jjtolton Aug 27, 2024
Author

Ok, I don't completely hate this version, but I feel like there's still probably a better way to do it:

:- use_module(library(charsio)).
:- use_module(library(debug)).
:- use_module(library(reif)).
:- use_module(library(lists)).
:- use_module(library(dif)).



set_subset(_, []).
set_subset(Xs, [Y|Ys]) :-
        maplist(dif(Y), Ys),    % no other occurences of Y in Ys
        memberd_t(Y, Xs, true), % Y is a member of YS
        set_subset(Xs, Ys).     

xs_ys_setdiff([], _, []).
xs_ys_setdiff([X|Xs], Ys, Diff0) :-
        if_(memberd_t(X, Ys),
            (
             xs_ys_setdiff(Xs, Ys, Diff0)
            ),
            (
             Diff0=[X|Diff],
             xs_ys_setdiff(Xs, Ys, Diff),
             set_subset([X|Xs], Diff0)
            )
           ).

Results

?- length(Xs, _N), xs_ys_setdiff(Xs, Ys, [1]).   
%@    Xs = [1], _N = 1, Ys = []
%@ ;  Xs = [1], _N = 1, Ys = [_A], dif:dif(_A,1)
%@ ;  Xs = [1], _N = 1, Ys = [_A,_B], dif:dif(_A,1), dif:dif(_B,1)
%@ ;  Xs = [1], _N = 1, Ys = [_A,_B,_C], dif:dif(_A,1), dif:dif(_B,1), dif:dif(_C,1)
%@ ;  ... .

?- length(Xs, _N), length(Ys, _N), xs_ys_setdiff(Xs, Ys, [1]).
%@    Xs = [1], _N = 1, Ys = [_A], dif:dif(_A,1)
%@ ;  Xs = [_A,1], _N = 2, Ys = [_A,_B], dif:dif(_A,1), dif:dif(_B,1)
%@ ;  Xs = [_B,1], _N = 2, Ys = [_A,_B], dif:dif(_A,_B), dif:dif(_A,1), dif:dif(_B,1)
%@ ;  Xs = [1,_A], _N = 2, Ys = [_A,_B], dif:dif(_A,1), dif:dif(_B,1)
%@ ;  Xs = [1,_B], _N = 2, Ys = [_A,_B], dif:dif(_A,_B), dif:dif(_A,1), dif:dif(_B,1)
%@ ;  ... .


?- xs_ys_setdiff([1, 2, 3, 4], [3, 5], Diff).
%@    Diff = [1,2,4].

?- length(Ls, _N), xs_ys_setdiff([1, 2, 3], Ls, Diff).
%@    Ls = [], _N = 0, Diff = [1,2,3]
%@ ;  Ls = [1], _N = 1, Diff = [2,3]
%@ ;  Ls = [2], _N = 1, Diff = [1,3]
%@ ;  Ls = [3], _N = 1, Diff = [1,2]
%@ ;  Ls = [_A], _N = 1, Diff = [1,2,3], dif:dif(_A,1), dif:dif(_A,2), dif:dif(_A,3)
%@ ;  Ls = [1,2], _N = 2, Diff = [3]
%@ ;  ... .

?- length(Ls, _), xs_ys_setdiff([1,2,3,4,5], Ls, [3,4]).
%@    Ls = [1,2,5]
%@ ;  Ls = [1,5,2]
%@ ;  Ls = [2,1,5]
%@ ;  Ls = [5,1,2]
%@ ;  ... .

I do find if_ really cool and mysterious and powerful, pretty amazing that it can accomplish what it does while staying monotonic!

jjtolton Aug 27, 2024
Author

There are many mysteries here, though. For instance, the most general query enumerates, but a query with two ground values for the first and last argument does NOT terminate (unless enumerated with length/2). I find that very strange.

?- xs_ys_setdiff(Xs, Ys, Diff).
%@    Xs = [], Diff = []
%@ ;  Xs = [_A], Ys = [], Diff = [_A]
%@ ;  Xs = [_A,_B], Ys = [], Diff = [_A,_B], dif:dif(_A,_B)
%@ ;  Xs = [_C,_A,_B], Ys = [], Diff = [_C,_A,_B], dif:dif(_A,_B), dif:dif(_C,_A), dif:dif(_C,_B)
%@ ;  Xs = [_D,_C,_A,_B], Ys = [], Diff = [_D,_C,_A,_B], dif:dif(_A,_B), dif:dif(_C,_A), dif:dif(_C,_B), dif:dif(_D,_A), dif:dif(_D,_B), dif:dif(_D,_C)
%@ ;  ... .

?- xs_ys_setdiff([1,2,3], Ys, Diff).
%@    Ys = [], Diff = [1,2,3]
%@ ;  Ys = [1], Diff = [2,3]
%@ ;  Ys = [1,2], Diff = [3]
%@ ;  Ys = [1,2,3|_A], Diff = []
%@ ;  Ys = [1,2,_A], Diff = [3], dif:dif(_A,3)
%@ ;  Ys = [1,2,_A,3|_B], Diff = [], dif:dif(_A,3)
%@ ;  Ys = [1,2,_A,_B], Diff = [3], dif:dif(_A,3), dif:dif(_B,3)
%@ ;  Ys = [1,2,_A,_B,3|_C], Diff = [], dif:dif(_A,3), dif:dif(_B,3)
%@ ;  ... .

?- xs_ys_setdiff([1,2,3], Ys, [1]).
%@    nontermination

UWN · 2024-08-28T07:27:18Z

UWN
Aug 28, 2024

This was the original version.

deleteall([], _X, []).
deleteall([E|Es], X, Ys0) :-
   if_( E = X, Ys0 = Ys, Ys0 = [E|Ys] ),
   deleteall(Es, X, Ys).

?- deleteall([A,B,C,A,C],A,Es).
   A = B, C = A, Es = []
;  A = B, Es = [C,C], dif:dif(C,A)
;  A = C, Es = [B], dif:dif(B,A)
;  Es = [B,C,C], dif:dif(B,A), dif:dif(C,A).

Which only deletes one element X. But we want to delete all elements of Xs. So we have to replace the condition (=)/3 above by a more sophisticated condition.

deletealls([], _Xs, []).
deletealls([E|Es], Xs, Ys0) :-
   if_( memberd_t(E, Xs), Ys0 = Ys, Ys0 = [E|Ys] ),
   deletealls(Es, Xs, Ys).

?- deletealls([A,B,C,A,C],[A],Es).
   A = B, C = A, Es = []
;  A = B, Es = [C,C], dif:dif(A,C)
;  A = C, Es = [B], dif:dif(A,B)
;  Es = [B,C,C], dif:dif(A,C), dif:dif(A,B).

?- deletealls([A,B,C,A,C],[A,B],Es).
   A = B, C = A, Es = []
;  A = B, Es = [C,C], dif:dif(A,C)
;  A = C, Es = [], dif:dif(A,B)
;  B = C, Es = [], dif:dif(A,B)
;  Es = [C,C], dif:dif(A,C), dif:dif(A,B), dif:dif(B,C).

To understand termination, you need first to master the notion of a failure slice. Now in your case of

?- deletealls("abc",Ys,"a").
   loops.

before looking into the actual implementation, just think of how an answer should look like. Ys has to be at least of length 2, and it must contain b and c, but never a. So how can we express this with answer substitutions and answer constraints? There is no other way than to write it down as a disjunction of infinitely many leaf answers. At least one for each length starting with 2. In other words, this query must not terminate, or we would miss some solutions. It now all depends where Prolog might start to enumerate those answers. You cannot expect Prolog to be very clever here, as this would make the enumeration mechanism ("chronological backtracking") way more complex (and it would not eliminate non-termination)

?- length(Ys,N),deletealls("abc",Ys,"a").
   Ys = "bc", N = 2
;  Ys = "cb", N = 2
;  Ys = [b,c,_A], N = 3, dif:dif(_A,a)
;  Ys = [b,_A|"c"], N = 3, dif:dif(_A,a), dif:dif(_A,c)
;  Ys = [c,b,_A], N = 3, dif:dif(_A,a)
;  Ys = [_A|"bc"], N = 3, dif:dif(_A,a), dif:dif(_A,b), dif:dif(_A,c)
;  Ys = [c,_A|"b"], N = 3, dif:dif(_A,a), dif:dif(_A,b)
;  Ys = [_A|"cb"], N = 3, dif:dif(_A,a), dif:dif(_A,b), dif:dif(_A,c)
;  Ys = [b,c,_A,_B], N = 4, dif:dif(_A,a), dif:dif(_B,a)
;  ... .

Now from the viewpoint of the implementation, we have the following failure slice:

?- deletealls("abc",Ys,"a"), false.
   loops.

deletealls([], _Xs, []) :- false.
deletealls([E|Es], Xs, Ys0) :-
   if_( memberd_t(E, Xs), Ys0 = Ys, Ys0 = [E|Ys] ), false,
   deletealls(Es, Xs, Ys).

In case of doubt, opt for better termination than fair enumeration. For, better termination permits us to enumerate solutions manually, whereas a definition that favors fair enumeration cannot be made to terminate.

1 reply

jjtolton Aug 28, 2024
Author

My exact reaction. The answer was so concise at first I thought it was pseudocode until I punched it in. Astonishing, I will spend some time reflecting on this.

UWN · 2024-08-28T14:26:44Z

UWN
Aug 28, 2024

A case of fair enumeration:

?- memberd_t(E, Xs, T).
   Xs = [], T = false
;  Xs = [E|_A], T = true
;  Xs = [_A], T = false, dif:dif(_A,E)
;  Xs = [_A,E|_B], T = true, dif:dif(_A,E)
;  Xs = [_A,_B], T = false, dif:dif(_A,E), dif:dif(_B,E)
;  Xs = [_A,_B,E|_C], T = true, dif:dif(_A,E), dif:dif(_B,E)
;  Xs = [_A,_B,_C], T = false, dif:dif(_A,E), dif:dif(_B,E), dif:dif(_C,E)
;  Xs = [_A,_B,_C,E|_D], T = true, dif:dif(_A,E), dif:dif(_B,E), dif:dif(_C,E)
;  Xs = [_A,_B,_C,_D], T = false, dif:dif(_A,E), dif:dif(_B,E), dif:dif(_C,E), dif:dif(_D,E)
;  ... .

Note how the positive and negative answers are almost the same, except for that tiny detail at the end...

1 reply

jjtolton Aug 28, 2024
Author

It boggles the imagination that this is possible in so few lines of code!

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Cutting `cut` from set difference #2507

{{title}}

{{editor}}'s edit

{{editor}}'s edit

Replies: 5 comments 4 replies

{{title}}

{{editor}}'s edit

{{editor}}'s edit

{{title}}

{{title}}

{{title}}

{{title}}

{{title}}

{{title}}

{{title}}

{{editor}}'s edit

{{editor}}'s edit

{{title}}

{{editor}}'s edit

{{editor}}'s edit

Select a reply

Cutting cut from set difference #2507

jjtolton Aug 27, 2024

Replies: 5 comments · 4 replies

triska Aug 27, 2024

UWN Aug 27, 2024

jjtolton Aug 27, 2024 Author

jjtolton Aug 27, 2024 Author

jjtolton Aug 27, 2024 Author

UWN Aug 28, 2024

jjtolton Aug 28, 2024 Author

UWN Aug 28, 2024

jjtolton Aug 28, 2024 Author

Cutting `cut` from set difference #2507

jjtolton
Aug 27, 2024

Replies: 5 comments 4 replies

triska
Aug 27, 2024

UWN
Aug 27, 2024

jjtolton
Aug 27, 2024
Author

jjtolton Aug 27, 2024
Author

jjtolton Aug 27, 2024
Author

UWN
Aug 28, 2024

jjtolton Aug 28, 2024
Author

UWN
Aug 28, 2024

jjtolton Aug 28, 2024
Author