Prolog: searching if 2 elements in a list occur equally

Question

I am new to Prolog and not a native speaker, so if you do not understand me, I am sorry.

My question is how can I find if a and b from a list appears equally?

For example, [a,a,b,b] should give me true but if either one appears more than the other it should give false. ex: [a,a,a,b,b].

Can anyone help me please? This is what I have so far and I know it is wrong but I am trying.

count(N,[],0).
count(N,[N|T],U) :-
   !,
   count(N,T,U1),
   U is U1+1.
count(N,[H|T],U) :-
   count(N,T,U).

occurrences([],[]).
occurrences([H|T],[[H,X]|Y]) :-
   count(H,[H|T],X),
   occurrences(T1,Y).

By *appear equally* do you also mean *consecutively*? In other words, does `[a,b,a,b]` succeed? — lurker, Nov 15 '17 at 17:49

score 2 · Answer 1 · answered Nov 15 '17 at 18:40

Here's a more compact version of occurrences/5 with if_/3 and =/3:

occurrences([],_A,_B,N,N).
occurrences([H|T],A,B,N0,M0) :-
   elem_x_count_(H,A,N1,N0),
   elem_x_count_(H,B,M1,M0),
   occurrences(T,A,B,N1,M1).

elem_x_count_(E,X,New,Old) :-
   if_(E=X, New is Old+1, New=Old).

In this version there is only one recursive rule that uses elem_x_count_/4 to increment the corresponding counter arguments if the head of the list matches A and B respectively or to leave them unchanged otherwise. The calling predicates remain unchanged:

occurrences(List,A,B) :-
   dif(A,B),
   occurrences(List,A,B,0,0).

or

occurrences(List) :-
   occurrences(List,a,b,0,0).

This way the predicate succeeds deterministically if all three arguments are ground (no need to press ; after true since there are no choicepoints left open). Here's the example query from the older version with occurrences/3:

?- occurrences([a,a,b,b],a,b).
true.

Another difference is that the number of dif/2 constraints is lower. For example:

?- occurrences([a,a,b,b,c,c,d],X,Y).
X = a,
Y = b ;
X = a,
Y = c ;
X = b,
Y = a ;
X = c,
Y = a ;
X = b,
Y = c ;
X = c,
Y = b ;
dif(X, d),
dif(X, c),
dif(X, b),
dif(X, a),
dif(X, Y),
dif(Y, d),
dif(Y, c),
dif(Y, b),
dif(Y, a).

Only the last solution of this query differs from my previous version. It describes the same result but all the difs that appeared twice in the other version now only appear once. The other example queries yield the same answers.

score 1 · Answer 2 · answered Nov 14 '17 at 23:13

You could write a predicate occurrences/5 that is true if the second and third arguments occur equally often in the list that is the first argument. The 4th and 5th arguments are the corresponding counters. Then the predicate occurrences/1 is the calling predicate:

occurrences(List) :-
   occurrences(List,a,b,0,0).

occurrences([],_A,_B,N,N).       
occurrences([A|Xs],A,B,N0,M) :-  
   N1 is N0+1,                   
   occurrences(Xs,A,B,N1,M).     
occurrences([B|Xs],A,B,N,M0) :-
   M1 is M0+1,
   occurrences(Xs,A,B,N,M1).
occurrences([X|Xs],A,B,N,M) :-
   dif(A,X),
   dif(B,X),
   occurrences(Xs,A,B,N,M).

You start with the counters at 0 and depending on the head of the list being equal to A or B the corresponding counter is incremented or no counter is incremented if the head differs from both. Now let's see the results for your given examples:

?- occurrences([a,a,b,b]).
true ;
false.

?- occurrences([a,a,a,b,b]).
false.

However, I think a predicate occurrences/3 that lets you specify the two elements would be more useful:

occurrences(List,A,B) :-
   dif(A,B),                     
   occurrences(List,A,B,0,0).

Then your example queries would look like this:

?- occurrences([a,a,b,b],a,b).
true ;
false.

?- occurrences([a,a,a,b,b],a,b).
false.

You could also ask which elements occur equally often:

?- occurrences([a,a,b,b,c,c,d],X,Y).
X = a,
Y = b ;
X = a,
Y = c ;
X = b,
Y = a ;
X = c,
Y = a ;
X = b,
Y = c ;
X = c,
Y = b ;
dif(X, d),
dif(X, c),
dif(X, c),
dif(X, b),
dif(X, b),
dif(X, a),
dif(X, a),
dif(X, Y),
dif(Y, d),
dif(Y, c),
dif(Y, c),
dif(Y, b),
dif(Y, b),
dif(Y, a),
dif(Y, a).

The last solution corresponds to two elements that do not appear in the list at all, since they both appear equally often, namely 0 times. If you want to use the predicate in the other direction, that is, to ask which lists there are such that two given elements appear equally often, you have to prefix a goal that is limiting the length of the list at the time of the predicate call, e.g.:

?- length(L,_),occurrences(L,a,b).
L = [] ;
L = [_G150],
dif(_G150, b),
dif(_G150, a) ;
L = [a, b] ;
L = [b, a] ;
L = [_G116, _G119],
dif(_G116, b),
dif(_G116, a),
dif(_G119, b),
dif(_G119, a) ;
L = [a, b, _G162],
dif(_G162, b),
dif(_G162, a) ;
L = [a, _G159, b],
dif(_G159, b),
dif(_G159, a) ;
L = [b, a, _G162],
dif(_G162, b),
dif(_G162, a) ;
.
.
.

Thank you so much It is really helpful and I really appreciate it. — Nona, Nov 14 '17 at 23:43
@false: I added one [here](https://stackoverflow.com/a/47314926/6101159). — tas, Nov 15 '17 at 18:41

CapelliC · Answer 3 · 2017-11-15T18:48:35.270

0

Instead of counting, you could pick a matching element from list' tail - it must exist - while visiting.

The recursion base case will be the simplest you can think of... and select/3 is the built in that will enable a really compact solution to your problem.

edit

well, the code is easy...

occurrences([],[]).
occurrences([H|T],R) :- select(H,T,U), occurrences(U,R).

note: on success, R will be the empty list

edited Nov 15 '17 at 18:48

answered Nov 14 '17 at 23:04

CapelliC

59,646
5
47
90

@LuaiGhunim: thanks, I misread the question. Will edit my answer, since the strategy (select/3 usage) would apply equally well to one list – CapelliC Nov 14 '17 at 23:08
lol i deleted my comment thought may be there were two lists. – Luai Ghunim Nov 14 '17 at 23:08

score 0 · Answer 4 · answered Nov 14 '17 at 23:10

0

You have only one list so at first your pattern matching will fail btw i will try like this and i'm not adding any explaination so that you can self figure it out how it works.

count(List):-
  count(List,0,0).

count([],L,L).


count([H|T],L,R):-
  (   
   H == 'a' ->
      NewL is L + 1,
      count(T,NewL,R)
    )
     ;
   (
     H == 'b' ->
       NewRight is R + 1,
       count(T,L,NewRight)
    ).

answered Nov 14 '17 at 23:10

Luai Ghunim

976
7
14

Thank you so much, I really appreciate it. I was thinking of the same idea but I did not know how to choose a list that consists of just a's and b's and make them equal. – Nona Nov 14 '17 at 23:52

Prolog: searching if 2 elements in a list occur equally

4 Answers4