Проверьте, не превышает ли частота какого-либо элемента предел

Используйте clpfd!

:- use_module(library(clpfd)).

Если мы строим вспомогательный предикат list_counts/2, мы можем определить frequency/2 следующим образом:

frequency(Es, M) :-
   list_counts(Es, Xss),
   maplist(arg(2), Xss, Zs),
   maplist(#>=(M), Zs).

Примеры запросов:

?- frequency([1,2,2,2,5], 3).
true.

?- frequency([1,2,2,2,2,5], 3).
false.

Благодаря clpfd мы можем задавать довольно общие вопросы. вопросы и получать логически обоснованные ответы!

?- frequency([A,B,C], 2).
       A=B ,           dif(B,C)
;                A=C , dif(B,C)
;            dif(A,C),     B=C
;  dif(A,B), dif(A,C), dif(B,C).

Вы можете сначала попытаться подумать о наиболее «дешевом» (с точки зрения написания) способе решения такой проблемы. Обычно я пытаюсь понять, как бы я это сделал со стандартными инструментами командной строки. Например, чтобы найти вхождение всех строк в текстовый файл с именем foo, нужно написать (в Bash):

sort foo | uniq --count

Вы можете прочитать руководства, но вот один пример запуска:

$ cat foo
a
b
b
b
c
d
d
a
b
d
c
$ sort foo | uniq --count
      2 a
      4 b
      2 c
      3 d

Теперь один из способов спросить: «Есть ли какая-нибудь строка со счетом выше 3?» использовать awk следующим образом:

sort foo | uniq --count | awk '{ if ($1 > 3) exit(1) }'

(Я уверен, что есть и более умные способы.)

С вышеуказанным файлом вы получаете:

$ sort foo | uniq --count | awk '{ if ($1 > 3) exit(1) }'
$ echo $?
1
$ sort foo | uniq --count | awk '{ if ($1 > 4) exit(1) }'
$ echo $?
0

Хорошо, а как это поможет вам с Прологом? Что ж, один простой способ эмулировать такой конвейер:

foo | bar | baz # etc

состоит в том, чтобы написать на Прологе такую ​​конъюнкцию:

foo(In, X0), bar(X0, X1), baz(X1, X2) % etc

Вернемся к вашей проблеме: вы можете использовать msort/2 (или, тем не менее, в используемой вами реализации вызывается предикат стабильной сортировки). Затем вам нужно подсчитать прогоны одного и того же элемента. В SWI-Prolog по крайней мере у вас есть group_pairs_by_key/2. Вы можете использовать его, например, следующим образом (вместе с другими предикатами в той же библиотеке вы можете увидеть код по той же ссылке):

pairs_keys_values(Pairs, Sorted, Sorted),
group_pairs_by_key(Pairs, Grouped),
pairs_values(Grouped, Runs),
maplist(length, Runs, Counts)

В этот момент у вас есть количество вхождений каждого элемента в Sorted в Counts (по общему признанию, немного более подробное, чем uniq --count), и вам просто нужно проверить, не превышает ли какой-либо из них ваш предел. Чтобы сделать что-то очень похожее на вызов awk выше в Прологе:

maplist(=<(3), Counts)

Отказ от ответственности: это всего лишь один из способов решения проблемы. Я решил напечатать это, потому что это показывает, что вам редко нужно писать много кода самостоятельно, если вы знаете, какие инструменты уже доступны вам.

Редактировать

Конечно, нет необходимости использовать group_pairs_by_key/2; однако знать об этом очень полезно, поэтому я привязал реализацию. Для этой проблемы было бы достаточно выполнить стабильную сортировку, за которой следует предикат, который просто подсчитывает количество последовательных вхождений одного и того же элемента, и добивается успеха только в том случае, если все такие запуски не длиннее предела. Базовая структура предиката, который делает это, такая же, как group_pairs_by_key/2.

Что с этим кодом...

frequency(L,N):-getall(L,L1), max_member(A,L1),A=<N.

getall([],[]).
getall(L,N):-append([],[X1|T],L),count(X1,L,N1),getall(T,N2),append([N1],N2,N).