Method that counts the number of occurs in one list in Prolog

Question

I have to write a method that can count the number of occurrences of one list from another list given. For example:

?-reps([a,b,c,a,b,c],[a,b,c],0,R). 
R = 2 ? ;
no

I was trying to code it:

incr(X, X1) :-
   X1 is X+1.

reps([],[],C,D):-
   incr(C,D).
reps(_,[],C,D):-
   incr(C,D),
   !.
reps([X|A],[X|B],C,D):-
   reps(A,B,C,D),
   reps(A,B,C,D).

My main problem is that, I can compare the first time, but the second time my "comparation list" is now empty and I can't compare the rest of the list. Is there a way to make a global variable that can store the "comparation list" to call it after?

Answer 1

My solution, assumes empty template implies infinitely many repetitions:

reps(L, [], inf):-
  is_proper_list(L).
reps(L, Template, N):-
  dif(Template, []),
  reps(L, Template, 0, N).
  
reps([], _, N, N).
reps(L, Template, N, N2):-
  starts_with(Template, L, L1),
  dif(N, N2),
  succ(N, N1),
  reps(L1, Template, N1, N2).
reps([A|L], Template, N, N1):-
  split_l(Template, [A|L], H, C),
  reps1(C, L, Template, H, N, N1).

reps1(y, L, Template, H, N, N1):-
  dif(Template, H),
  reps(L, Template, N, N1).
reps1(n, _, _, _, N, N).

starts_with([], L, L).
starts_with([A|T], [A|L], L1):-
  starts_with(T, L, L1).
  
split_l([], _, [], y).
split_l([_|_], [], [], n).
split_l([_|T], [A|L], [A|L1], C):-
  split_l(T, L, L1, C).
  
is_proper_list(L):-
  freeze(L, is_proper_list1(L)).

is_proper_list1([]).
is_proper_list1([_|L]):- acyclic_term(L), is_proper_list(L).

With some sample runs:

?- reps([a,b,c,a,b,c],[a,b,c],N). 
N = 2 ;
false.

?- reps([a,b,c,a,b,c],X,2).
X = [a] ;
X = [a, b] ;
X = [a, b, c] ;
X = [b] ;
X = [c] ;
X = [b, c] ;
false.

?- reps([a,B],[B],N).
B = a,
N = 2 ;
N = 1,
dif(B, a) ;
;
false.

?- reps([A,B,C],[D,E],N).
A = D,
B = E,
N = 1 ;
B = D,
C = E,
N = 1,
dif(f(D, E), f(A, D)) ;
;
N = 0,
dif(f(D, E), f(A, B)),
dif(f(D, C), f(B, E)) ;
;
false.


?- reps(L,T,N).
T = [],
N = inf,
freeze(L, is_proper_list1(L)) ;
;
L = [],
N = 0,
dif(T, []) ;
;
L = T, T = [_1740],
N = 1 ;
L = [_1740, _1740],
T = [_1740],
N = 2 ;
L = [_1740, _1740, _1740],
T = [_1740],
N = 3 .
 ...

Some more samples:

?- reps([], [], N).
N = inf ;
false.

?- reps(L, [], N).
N = inf,
freeze(L, is_proper_list1(L)) ;
;
false.

?- reps(L, [], N), L=[].
L = [],
N = inf ;
false.

Answer 2

As pointed out in comments in my other attempt at a pure solution that also supports generalized queries, the use of findall/3 is questionable as to the purity. This answer works without findall/3. It assumes that the pattern to look for is a non-empty list, otherwise the result is inf.

reps/3 checks if P is a pattern in L, and if so, counts its occurrences using reps/4. A special case is with the pattern count 0. To avoid negating pattern, the predicate nopattern checks if the pattern is contained exactly one in a list where it is appended first.

pattern([A],[A]).
pattern([H|T],P) :- append(P,_,[H|T]);pattern(T,P).

noPattern(L,P) :- append(P,L,PL),reps(PL,P,0,1).

startNoMatch([],[_]):- true.
startNoMatch(_,[]):- false.
startNoMatch([X1|T1],[X2|T2]) :- dif(X1,X2); startNoMatch(T1,T2).

reps(L,P,C,C) :- length(L,L1), length(P,L2), L1 < L2.
reps(L,P,C,D):- append(P,R,L),C1 is C+1, reps(R,P,C1,D).
reps([H|T],P,C,D):- startNoMatch([H|T],P),reps(T,P,C,D).

reps(_,[],inf).
reps(L,P,0) :- P=[_|_],noPattern(L,P).
reps(L,P,C) :- P=[_|_],pattern(L,P),reps(L,P,0,C),C>0.

Answer 3

Considering that list is an arbitrary list, a possible solution is:

reps(L, P, N) :-
   star(P, L, 0, N).

star(_, [], A, A).
star([X|P], [Y|L], A, N) :-
   rest([X|P], [Y|L], RP, RL),
   (   RP = [],                % skip pattern
       A1 is A + 1,
       star([X|P], RL, A1, N)
   ;   dif(RP, []),            % skip first item
       star([X|P], L, A, N) ).

% rest(P, L, RP, RL)

rest([], L, [], L) :- dif(L, []).
rest(P, [], P, []).
rest([X|P], [X|L], RP, RL) :- rest(P, L, RP, RL).
rest([X|P], [Y|L], [X|P], [Y|L]) :- dif(X,Y).

Examples:

?- reps([a,b,a], [a,b], N).
N = 1 ;
false.

?- reps([a,a,c], [a,c], N).
N = 1 ;
false.

?- reps([x,a,b,c,y,z,a,b,c], [a,b,c], N).
N = 2 ;
false.

?- reps([a,B], [B], N).
B = a,
N = 2 ;
N = 1,
dif(B, a) ;
false.

?- reps([a,B], P, N).
B = a,
P = [a],
N = 2 ;
P = [a],
N = 1,
dif(B, a) ;
P = [a, B],
N = 1 ;
B = a,
P = [a, a|_20298],
N = 0,
dif(_20298, []) ;
P = [a, B|_22326],
N = 0,
dif(B, a),
dif(_22326, []) ;
B = a,
P = [a, _24256|_24258],
N = 0,
dif(_24256, a) ;
P = [a, _26278|_26280],
N = 0,
dif(B, a),
dif(_26278, B) ;
P = [B],
N = 1,
dif(B, a) ;
P = [B|_29880],
N = 0,
dif(B, a),
dif(_29880, []) ;
P = [_412|_414],
N = 0,
dif(_412, B),
dif(_412, a) ;
false.

Answer 4

Considering that list is only a repetition of pattern, a possible solution is:

reps(List, [P|Ps], N) :-
   star([P|Ps], List, 0, N).

star(_, [], Acc, Acc).
star([X|Xs], L, Acc, N) :-
   append([X|Xs], R, L),
   Acc1 is Acc + 1,
   star([X|Xs], R, Acc1, N).

Here are some examples:

?- reps([1,2,3,1,2,3], [1,2,3], R).
R = 2 ;
false.

?- reps([a,b,a,b,a,b], [a,b], R).
R = 3 ;
false.

?- reps([a,B], [B], N).
B = a,
N = 2 ;
false.

?- reps([a,B], P, N).
B = a,
P = [a],
N = 2 ;
P = [a, B],
N = 1 ;
false.

?- reps(L, [a,b], N).
L = [],
N = 0 ;
L = [a, b],
N = 1 ;
L = [a, b, a, b],
N = 2 ;
L = [a, b, a, b, a, b],
N = 3.

Answer 5

As suggested by @false in comments in my other answer, a pure solution that accepts general queries as well, would be desirable. The following solution also allows finding all repeating patterns for a certain length, or other more general patterns: findPatterns collects all possible patterns to search for in the input list. reps/5, as before, finds the number of matches for a pattern in an input string. This version, however, can cope with any content not part of the pattern as well. reps/3, finally, checks if P is one of the patterns to be found in L and, if so, retrieves its count.

findPatterns([],[]).
findPatterns([H|T],L) :- findall(P, (P=[_|_],append(P,_,[H|T])),Patterns), 
                         findPatterns(T,L1), 
                         append(Patterns, L1,L).

startNoMatch(_,[]):- false.
startNoMatch([X1|T1],[X2|T2]) :- dif(X1,X2); startNoMatch(T1,T2).

reps(L,P,C,C) :- length(L,L1), length(P,L2), L1 < L2.
reps(L,P,C,D):- append(P,R,L),C1 is C+1, reps(R,P,C1,D).
reps([H|T],P,C,D):- startNoMatch([H|T],P),reps(T,P,C,D).

reps(L,P,C) :- findPatterns(L,Patterns), 
               list_to_set(Patterns,PSet), 
               (member(P,PSet), reps(L,P,0,C); \+ member(P,PSet), C=0).

Queries:

?- reps([a,b,c,a,b,c],[a,b,c],R).
R = 2 ; false.

?- reps([a,b,c,a,b,c],X,2).
X = [a] ;
X = [a, b] ;
...

?- reps([a,B],[B],2).
B = a ; false.

?- reps([a,B],[B],1).
dif(B, a) ; false.

As can be seen in the last query, dif/2 delays the goal, so that further parts of a query may succeed for Bs that are different from a.

Answer 6

You cannot really set global variables in a predicate. Instead, you can just pass the constant value as an extra parameter to reset the work list once it is consumed. Assuming the input list only consists of multiples of the pattern list as in your example, you could do that as follows (Full pattern parameter is the third):

reps([],[],_,C,D):-
   incr(C,D).
reps([H|T],[],P, C,D):-
   incr(C,C1),reps([H|T], P, P, C1,D).
reps([X|A],[X|B],P,C,D):- reps(A,B,P,C,D).

Call with:

?- reps([a,b,c,a,b,c],[a,b,c],[a,b,c],0,R).
R = 2 ;

If there are other characters in between or incomplete patterns, I would instead work with an additional predicate that checks if the start of the list matches the pattern at every position. If it does, the counter is increased.

incr(X, X1) :-
X1 is X+1.

reps([],_,C,C).
reps([H|T],Pattern,C,D):- (startMatches([H|T],Pattern) -> 
                               incr(C,C1), reps(T,Pattern,C1,D); 
                               reps(T,Pattern,C,D)).

startMatches(_,[]).
startMatches([X|T1],[X|T2]) :- startMatches(T1,T2).