I don't understand why this query do not terminate

Help!
1

I’m trying to implement a distinct/2 predicate, that takes two lists A and B where B has the same elements as A without duplicates (ordering is preserved).

some examples:

distinct([1,2,2,3],[1,2,3]).
distinct([3,2,3,1,2,3],[3,2,1]).

Here is my code

not_member(_,[]).
not_member(X,[Y|Z]) :-
  dif(X,Y),
  not_member(X,Z).

distinct([],[]).
distinct(A,B) :-
    length(A,LA),
    length(B,LB),
    LA #>= LB,
    distinct_(A,B,[]).

distinct_([],B,Seen) :-
    reverse(B,Seen).
distinct_([X|A],B,Seen) :-
    member(X,Seen),
    distinct_(A,B,Seen).
distinct_([X|A],B,Seen) :-
    not_member(X,Seen),
    distinct_(A,B,[X|Seen]).

% ?- distinct([1,2,2,3,2],X).
%@ X = [1, 2, 3] ;
% DO NOT TERMINATE

% ?- distinct(X,[1,2,3]).
%@ X = [1, 2, 3] ;
%@ X = [1, 1, 2, 3] ;
%@ X = [1, 2, 2, 3] ;
%@ X = [1, 2, 1, 3] ;
%@ X = [1, 2, 3, 3] ;
%@ X = [1, 2, 3, 2] ;
%@ X = [1, 2, 3, 1] ;
%@ X = [1, 1, 1, 2, 3] ;
%@ X = [1, 1, 2, 2, 3] ...

% ?- length(X,3), length(Y,2), distinct(X,Y).
%@ X = [_A, _A, _B],
%@ Y = [_A, _B],
%@ dif(_B, _A) ;
%@ X = [_A, _B, _B],
%@ Y = [_A, _B],
%@ dif(_B, _A) ;
%@ X = [_A, _B, _A],
%@ Y = [_A, _B],
%@ dif(_B, _A) ;
%@ false.

I’m trying to understand why the first query do not terminate.
I am also open to learn about a better way to implement such relation.

Thank you

2

I think your problem could be that on backtracking there is an useless loop:

distinct(A,B) :-
    length(A,LA),
    length(B,LB),  % loop on B free, generating always increasing LB
    LA #>= LB,
    distinct_(A,B,[]).
1 Like
3

Thank you @CapelliC, I understand, but I think that the culprit is the line above (in the non terminating case).
In this particular relation, For a given A there is only one possible B, how can I stay this in my code ? (in order to stop the search)

4

See How to remove duplicates from a list in SWI-Prolog? - Stack Overflow

swi-prolog’s built-in sort/2 is faster, being native.

1 Like
5

Thank you @brebs, I am aware of sort/2 but I’m looking for a fully relational solution (where any of the arguments can be a variable) also I don’t want the output to be sorted.

6

Can be “pure” using e.g. memberd_t/3 - an example of its usage is prolog - Delete from a list the non-duplicated items - Stack Overflow

1 Like
7

Instead of trying to compare the two values against each other consider converting each to a canonical representation and then comparing that. Just remove the duplicates for each list to create the canonical value.

This one has me a bit confused because one can change the values, E.g. 1,2,3 into variables, E.g. A,B,C and most Prolog predicates work. However if you do that then a,b,c would be the same as 1,2,3 and that sounds like something you don’t want. See my confusion?

If however you do allow a,b,c to be the same as 1,2,3 then look at using =@=/2.

The predicates from Analysing and Constructing Terms will soon become your friends.

Normally I would write example code but am busy at the moment so a simple description is better than nothing.

1 Like
8

CLP(FD) and length/2 don’t necessarily mix as you’d like. Completely avoid using CLP(FD) for that, and instead use normal Prolog. This:

length(A,LA),
length(B,LB),
LA #>= LB

Another way to say the same as you attempted to do would be:

length(A, LA),
between(0, LA, LB),
length(B, LB)

If I change it like this without any other changes, I get:

?- distinct([1,2,2,3,2],X).
X = [1, 2, 3] ;
false.

Everything else works as now.

You should probably have just debugged your code to see what happened.

PS: Since this answer has now been accepted as “solution”. While this technically solves your issue, I am not at all convinced that this is the best way to solve it, nor do I understand the need for this altogether.

1 Like
9

I see. You can ignore all complexities related to constraints, purity, etc, since you are stuck here:

length(_,LB),0>=LB,

My suggestion is to simply drop such (useless) code.

distinct(A,B) :-
    distinct_(A,B,[]).

Since I didn’t debugged distinct_/3, I’m not sure it will work ‘out-of-the-box’, but I would try anyway. Simpler code is better.

1 Like
10

@brebs thank you for the SO pointer, this answer looks really interesting to me (I have to dig reifmore)

@EricGT, thank you, I was not aware of =@=/2 it looks interesting, and sure, Analysing and constructing Terms will be very useful in the future !

@Boris, nice catch ! I should indeed run my code into the debugger, I simply forgot this option, I’m really new to prolog, I will get used to it. thank you a lot.

@CapelliC, yes that sounds that like great advice, I will remember this, thank you.

11

Why do you want this? There’s an infinite number of solutions to distinct(X,[1,2,3]).

Anyway, if you don’t want it to be fully relational, there’s a solution in the library: list_to_set/2 whose code is here:

But this depends on the first argument being sufficiently ground, such that sort/2 always gives the same answer regardless of how any of its arguments are instantiated (e.g., [a,b(X),[Y]) is sufficiently ground by [X,Y] isn’t).

12

Is the following desirable or undesirable, @pbaille ?

?- list_to_set([3, A], S), A = 3.
A = 3,
S = [3,3].    <-- Duplicates
13

Thank you for the answer, I don’t know if I really need this particular predicate to be fully relational, but in general this seems to be the most be appealing aspect of prolog for me, so I try to stay relational as much as I can while learning the language.

14

Yes it seems weird to me, is this what is called “non-monotonic” ?

15

Yeah. I find the more generic pure vs nonpure to be easier to grasp than the monotonic vs steadfast subtlety :grinning:

16

Yes, Power of Prolog is what bring me back here :), It is a wonderful introduction to prolog I think.

18

This can significantly complicate your code. Often you have to add var/1 tests or use wait/2 or freeze/2 to get full relational, and end up with something like this, for little obvious benefit:

pred(X, Y) :-
    ( var(X)
    -> pred_forward(X, Y)
    ;  pred_backward(Y, X)
    ).

As another example, the arithmetic constraint #=/2 is effectively the same as if defined below; but if you know that Y is always ground, you can just do X is Y (or X=:=Y if you know that both X and Y are ground).

eq(X, Y) :-
    when((ground(X) ; ground(Y)),
    (   ground(X)
    ->  (   ground(Y)
        ->  X =:= Y
        ;   Y is X
    ;   X is Y
    )).

Also, it can be tricky to get the semantics correct – in the example of your distinct/2, you could define it like this:

distinct(X, Y) :-
    (  var(X)
    -> X = Y
    ;  list_to_set(X, Y)
    ).

but that’s not really correct because it fails with distinct(X,[1,2]), X=[1,2,1] whereas X=[1,2,1], distinct(X,[1,2]) succeeds.

On the other hand, the mostly works, and doesn’t get into infinite backtracking if X is uninstantiated:

distinct(X, Y) :-
    freeze(X, list_to_set(X, Y)).

but it’s still not enough – try it with distinct(X,[1,2]), X=[1,2|Z].

It would be nice to have a tool to validate assumptions about things being sufficiently ground, but I’m not aware of such a tool (type inferencing could possibly do this, but research into type inferencing for Prolog seems to have died out quite a while ago).

2 Likes
19

Do you see another way to achieve the same thing in a better way ?
Concerning the need for such a relation, I’m not convinced either that it will be so useful, but it seems quite basic, and I don’t see why not either.

20

Thank you for those explanations, indeed splitting a predicate based on the “groundness” of its parts seems to be handy in some cases.
The freeze/2 predicate looks really useful too, I didn’t know it.

For me, what makes prolog so special is this relation thing, this is the facet of the language that I really want to dig, it seems to me that when we do non-relational things we are going away from its beauty toward functional programming land (which I like a lot, I’m a lisper, but this is not why I’m here).

That being said, I understand that as a prolog programmer you absolutly need all those non-relational things to do all the common things that a programmer has to do.

21

The relational view is really nice of course as it creates a fully declarative language. It isn’t all that useful when one side of the relation is infinite, as is the case for removing duplicates. Now, called with the non-duplicate side instantiated (or nothing instantiated) you generate an infinite set. If the set is denumerable and you generate the elements accordingly the computation still terminates. Often far too slow to be of any practical use though.

In many cases you can reorder the computation to make sure such relations are used in the right direction and you get to practical results. Often you can also use coroutining like freeze/2 to achieve the same result. I wouldn’t advice that in general. If you have a black box computation onto which you want to put an additional constraint, doing so using freeze/2 before entering the back box may be more efficient than doing the filtering at the end.

3 Likes