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?

Promise: Will put a 500-bounty for a pure version that works also for generalized queries. — false, May 17 '21 at 11:26
@false there are many questions though. Should empty lists be allowed: `list_n_reps([], 3, [])`? how about "0 repetitions": `list_n_reps(_, 0, [])`? How about the order in which you enumerate if all arguments are variables: `list_n_reps(L, N, R)`? Your solutions could be then: `L = R, R = [], N = 0 ; L = R, R = [], N = 1 ; ... `. Is that acceptable? — TA_intern, May 19 '21 at 06:55
Empty lists would imply infinitely many repetitions. Even within the empty list. So looping seems to be a justifiable answer, too. That there are different numbers of repetitions for the same lists does not make much sense to me. — false, May 19 '21 at 09:55

jf_ · Answer 1 · 2021-05-18T11:50:15.800

2

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.

edited May 18 '21 at 11:50

answered May 18 '21 at 07:54

jf_

3,099
2
13
31

`C=d, reps([a,b,C],[b,c],0).` fails. Yet, `reps([a,b,C],[b,c],0), C=d.` succeeds. Décidez-vous. – false May 18 '21 at 08:36
@false They both fail on my machine. – jf_ May 18 '21 at 09:08
Update: Fixed support of reps-Count=0. – jf_ May 18 '21 at 09:17
1

`reps([a,a,c],[a,c],1).` incorrectly fails – false May 18 '21 at 09:55
@false Yet again you are right. The *not matching* check with `dif/2` should have covered the whole pattern length. I gave it another update. – jf_ May 18 '21 at 10:47
Minor improvement (though I am still skeptical, after all there is this `findall/3`): Instead of `length(P,Len),Len>0`, say `P = [_|_]` prior to `append/3`. – false May 18 '21 at 11:33
@false I posted another answer without `findall/3`. – jf_ May 20 '21 at 16:25

gusbro · Answer 2 · 2021-05-28T04:10:39.390

2

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.

edited May 28 '21 at 04:10

answered May 19 '21 at 19:58

gusbro

22,357
35
46

Clearly impure: `reps([],[], N)` succeeds ; yet, it generalization `reps(L,[],N)` fails. – false May 19 '21 at 21:26
@false: I am using SWI prolog 8.0.2 where neither query fails. The second one: `reps(L, [], N)` yields `N = inf, freeze(L, proper_list1(L))`. Added those sample runs to the answer – gusbro May 19 '21 at 22:51
What does `proper_list(L)` say in 8.0.2? At least in 7.6.4 it fails and is defined for the sake of backward_compatibility as `is_list(L)` – false May 20 '21 at 08:35
@false: I did not know about `proper_list/1` defined in `backward_compatibility` module of SWI. In SWI 8.0.2 it takes my definition of `proper_list/1` (written in the answer) which I have now renamed to `is_proper_list/1`. The difference between `is_list/1` and `is_proper_list/1` is that the former fails for variable terms and some not fully grounded terms (for example `is_list(L)` or `is_list([A|_])` whereas is_proper_list will suspend until it can prove it being a list or not. – gusbro May 20 '21 at 12:59
1

My original procedure `proper_list` when queried `proper_list(L)` would answer `freeze(L, proper_list1(L)).` – gusbro May 20 '21 at 13:01
Ah, I was using the default-definition of SWI. – false May 20 '21 at 15:21
Ad bounty: most compact answers. – false May 27 '21 at 14:48
BTW, there is acyclic_term/1 (which is even ISO, whereas cyclic_term/1 is not). But I only considered instances of `reps(_, [_|_], _)` – false May 27 '21 at 14:50
1

Changed `\+cyclic_term(L)` to `acyclic_term(L)`, I prefer using ISO predicates when possible – gusbro May 28 '21 at 04:14
One more (that is out of scope of the question): `L=[L], is_proper_list(L).` succeeds, but `L=[L,L], is_proper_list(L).` fails. – false May 28 '21 at 07:30

score 2 · Answer 3 · answered May 20 '21 at 16:25

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.

This `inf`, isn't really a good idea (independently of the rest). — false, May 20 '21 at 17:56

jf_ · Answer 4 · 2021-05-18T07:54:02.433

1

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).

edited May 18 '21 at 07:54

answered May 17 '21 at 11:09

jf_

3,099
2
13
31

`B = b, reps([a,B],[B],0,1).` succeeds, yet its generalization `reps([a,B],[B],0,1).` fails. Not clear what you mean by declarative pattern. – false May 17 '21 at 11:24
@false Maybe the term declarative pattern was misleading, I just meant Prolog being a declarative language. I updated the text. Not sure what you are saying with your example though. – jf_ May 17 '21 at 11:31
Thank you, very useful! But I don't get why you call 2 times to reps, one with C1 and another one with C. – Alvaro Sánchez May 17 '21 at 11:48
`->` is a control expression, like if/else. In the first case (pattern found), `C` gets increased to `C1`, which is then passed to `reps`. In the second case, after `;`, `reps` gets the `C`, which is not increased. – jf_ May 17 '21 at 11:54
@jf_: From a declarative viewpoint (that is, considering the set of solutions) there cannot be failure for a generalized query. – false May 17 '21 at 12:52
@false, I added another alternative to the answer. – jf_ May 17 '21 at 22:16

slago · Answer 5 · 2021-05-18T14:19:00.753

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.

I've modified the base case of predicate ```rest/4``` to solve the problem. — slago, May 18 '21 at 14:19

slago · Answer 6 · 2021-05-18T13:09:17.110

0

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.

edited May 18 '21 at 13:09

answered May 18 '21 at 02:34

slago

5,025
2
10
23

`reps([a,b],[b],N).` fails. It should succeed with `N = 1`. – false May 18 '21 at 08:01
1

I've considered that the input list only consists of multiples copies of the pattern, as the example tgiven in the question. – slago May 18 '21 at 10:11
I've updated my answer, considering an arbitrary list. – slago May 18 '21 at 12:52
Please put your new solution into a different answer! – false May 18 '21 at 13:04
I've posted a new solution, as you asked! – slago May 18 '21 at 13:10

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

6 Answers6

Linked