CODEWITHSUNDEEP
prolog
Max
Max

Reputation: 23

Prolog: eliminate repetitions in query

I've been trying to write a simple code, that would behave in this manner: 

| ?- hasCoppiesOf(X,[a,b,a,b,a,b,a,b]).
X = [a,b] ? ;
X = [a,b,a,b] ? ;
X = [a,b,a,b,a,b,a,b] ? ;

And 

| ?- hasCoppiesOf([a,b,a,b,a,b,a,b], X).    
X = [] ? ;    
X = [a,b,a,b,a,b,a,b] ? ;    
X = [a,b,a,b,a,b,a,b,a,b,a,b,a,b,a,b] ? ;    
X = ...

This desire resulted in next piece of code: 

hasCoppiesOf(A,[]).


hasCoppiesOf([H1|T1], [H1|T2]) :-
  append(T1, [H1], X),
  hasCoppiesOf([H1|T1], X, T2).


hasCoppiesOf(A, A, B) :-
  hasCoppiesOf(A, B).

hasCoppiesOf(A, [H1|T1], [H1|T2]) :-
  append(T1, [H1], X),
  hasCoppiesOf(A, X, T2).

And it gives me what I want on the second query, however, the first results in: 

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

It seems to be working fine, but that repetition of the same answers bothers me. It's, probably, a simple mistake, but is there a way to make the output prettier? And honestly, that a mystery, why Prolog treats two identical arrays as different answers. Or maybe it's just something wrong with my system?

Edit: The gentle guidance of the person in the comments helped me to solve this issue. However, if this question will be reading the person who wants to solve exactly the same problem - code not really working well, my apologies.

Upvotes: 0

Views: 172

Answers (3)

lurker
lurker

Reputation: 58224

I think you just made your predicate more complex than it needs to be, probably just overthinking it. A given solution may succeed in multiple paths through the logic.

You can do this without append/3 by aligning the front end of the lists and keep the original list to "reset" on repeats:

% Empty list base cases
dups_list([], []).
dups_list([_|_], []).

% Main predicate, calling aux predicate
dups_list(L, Ls) :-
    dups_list(L, L, Ls).

% Recursive auxiliary predicate
dups_list([], [_|_], []).
dups_list([], [X|Xs], [X|Ls]) :-
    dups_list(Xs, [X|Xs], Ls).
dups_list([X|Xs], L, [X|Ls]) :-
    dups_list(Xs, L, Ls).

Here are some results:

| ?- dups_list(X,[a,b,a,b,a,b,a,b]).

X = [a,b] ? a

X = [a,b,a,b]

X = [a,b,a,b,a,b,a,b]

no
| ?- dups_list([a,b,a,b,a,b,a,b], X).

X = [] ? ;

X = [a,b,a,b,a,b,a,b] ? ;

X = [a,b,a,b,a,b,a,b,a,b,a,b,a,b,a,b] ? ;

X = [a,b,a,b,a,b,a,b,a,b,a,b,a,b,a,b,a,b,a,b,a,b,a,b] ?
...
| ?- dups_list(A, B).

A = []
B = [] ? ;

A = [_|_]
B = [] ? ;

A = [C]
B = [C] ? ;

A = [C]
B = [C,C] ? ;

A = [C,D]
B = [C,D] ? ;

A = [C]
B = [C,C,C] ? ;

A = [C,D,E]
B = [C,D,E] ? ;
...

There may be a way to simplify the solution just a bit more, but I haven't played with it enough to determine if that's the case.

Upvotes: 2

Strange
Strange

Reputation: 1540

Okay, I got your problem, you want to eliminate the repetitions.

hasCoppiesOf(A,[]).


hasCoppiesOf([H1|T1], [H1|T2]) :-
  append(T1, [H1], X),
  hasCoppiesOf([H1|T1], X, T2).


hasCoppiesOf(A, A, B) :-
  hasCoppiesOf(A, B),!. %Change here, place a cut after the termination.

hasCoppiesOf(A, [H1|T1], [H1|T2]) :-
  append(T1, [H1], X),
  hasCoppiesOf(A, X, T2).

This is the change that you need to make.

hasCoppiesOf(A, A, B) :-
      hasCoppiesOf(A, B),!.

A Cut '!' terminates the unwanted backtracking and thereby repetitions.

Upvotes: 1

Strange
Strange

Reputation: 1540

I think this is what you're trying for... 

coppies(Z,Z,[]).
coppies(X,Z,[Y|Ys]):- \+member(Y,Z),coppies(X,[Y|Z],Ys).
coppies(X,Z,[Y|Ys]):- member(Y,Z),coppies(X,Z,Ys).


copies(M,[Y|Ys]):-coppies(M,[],[Y|Ys]).

Input:

copies(X,[1,2,1,2,1,2]).

Output:

X = [2, 1].

BTW I've used some different names instead..

Upvotes: 1

Related Questions