Prolog – count repetitions in list

by

This answer shows a logically pure way to do it. The following is based on clpfd.

:- use_module(library(clpfd)).

We define meta-predicate tcount/3 similarly to tfilter/3!

:- meta_predicate tcount(2,?,?).
tcount(P_2,Xs,N) :-
   N #>= 0,
   list_pred_tcount_(Xs,P_2,0,N).

:- meta_predicate list_pred_tcount_(?,2,?,?).
list_pred_tcount_([]    , _ ,N ,N).
list_pred_tcount_([X|Xs],P_2,N0,N) :-
   if_(call(P_2,X), (N1 is N0+1, N1 #=< N), N1 = N0),
   list_pred_tcount_(Xs,P_2,N1,N).

Now let’s use tcount/3 in combination with (=)/3:

?- tcount(=(yes),[yes,and,yes,and,no],Count).
Count = 2.

Unlike the code presented by all other answers to this question, the code presented in this answer is monotone and remains logically sound even when using it with non-ground terms:

?- tcount(=(yes),[A,B,C,D],2).
      A=yes ,     B=yes , dif(C,yes), dif(D,yes)
;     A=yes , dif(B,yes),     C=yes , dif(D,yes)
;     A=yes , dif(B,yes), dif(C,yes),     D=yes
; dif(A,yes),     B=yes ,     C=yes , dif(D,yes)
; dif(A,yes),     B=yes , dif(C,yes),     D=yes
; dif(A,yes), dif(B,yes),     C=yes ,     D=yes
; false.

Let’s try something even more general:

?- tcount(=(yes),[A,B,C,D],Count).
      A=yes ,     B=yes ,     C=yes ,     D=yes , Count = 4
;     A=yes ,     B=yes ,     C=yes , dif(D,yes), Count = 3
;     A=yes ,     B=yes , dif(C,yes),     D=yes , Count = 3
;     A=yes ,     B=yes , dif(C,yes), dif(D,yes), Count = 2
;     A=yes , dif(B,yes),     C=yes ,     D=yes , Count = 3
;     A=yes , dif(B,yes),     C=yes , dif(D,yes), Count = 2
;     A=yes , dif(B,yes), dif(C,yes),     D=yes , Count = 2
;     A=yes , dif(B,yes), dif(C,yes), dif(D,yes), Count = 1
; dif(A,yes),     B=yes ,     C=yes ,     D=yes , Count = 3
; dif(A,yes),     B=yes ,     C=yes , dif(D,yes), Count = 2
; dif(A,yes),     B=yes , dif(C,yes),     D=yes , Count = 2
; dif(A,yes),     B=yes , dif(C,yes), dif(D,yes), Count = 1
; dif(A,yes), dif(B,yes),     C=yes ,     D=yes , Count = 2
; dif(A,yes), dif(B,yes),     C=yes , dif(D,yes), Count = 1
; dif(A,yes), dif(B,yes), dif(C,yes),     D=yes , Count = 1
; dif(A,yes), dif(B,yes), dif(C,yes), dif(D,yes), Count = 0.

What about the following corner case?

?- tcount(_,_,-1).
false.

And how about utilizing tcount/3 as an alternative to length/2?

?- N in 1..3, length(Xs,N).
  N = 1, Xs = [_A]
; N = 2, Xs = [_A,_B]
; N = 3, Xs = [_A,_B,_C]
...                                      % does not terminate

?- use_module(library(lambda)).
true.

?- N in 1..3, tcount(\_^ =(true),Xs,N).
  N = 1, Xs = [_A]
; N = 2, Xs = [_A,_B]
; N = 3, Xs = [_A,_B,_C]
; false.                                 % terminates universally

More Related Contents:

  1. prolog change show answer to print into list
  2. Prolog union for A U B U C
  3. Prolog removing unique elements only
  4. Find powers of 2 in a list Prolog
  5. Flatten a list in Prolog
  6. How do I append lists in Prolog?
  7. Prolog: Filtering a list?
  8. Remove duplicates in list (Prolog)
  9. Subsets in Prolog
  10. Get elements from list of lists
  11. Lazy lists in Prolog?
  12. Segregating Lists in Prolog
  13. Splitting a list of integers into a list of positive integers and a list of negative integers
  14. How to count number of element occurrences in a list in Prolog
  15. Intersection and union of 2 lists
  16. Prolog: First duplicate value
  17. Implementing “last” in Prolog
  18. Recursive Prolog predicate for reverse / palindrome
  19. Prolog, find minimum in a list
  20. Concatenating two lists – difference between ‘+=’ and extend()
  21. Convert a matrix to a list of column-vectors
  22. Search for an item in a Lua list
  23. Java 8: sort list of objects by attribute without custom comparator
  24. How to clone or copy a list in kotlin
  25. Difference between a Seq and a List in Scala
  26. XPath 1.0 to find if an element’s value is in a list of values
  27. How can I read the contents of a file into a list in Lisp?
  28. R: Print list to a text file
  29. Add or remove an entry from a List type attribute in a DynamoDB table item
  30. What are the differences between vector and list data types in R?

Leave a Comment