Замечательно, что теперь это работает с помощью декларативной арифметики!
У меня есть несколько дополнительных замечаний по поводу полученного вами решения, а именно:
count(_, [], 0) :- !.
count(El, [El|T], N) :-
count(El, T, N1),
N #= N1 + 1.
count(El, [Y|T], N) :-
El \= Y,
count(El, T, N).
check(List1, List2) :-
count(3, List1, M),
count(2, List2, N),
M #= N.
Во-первых, обратите внимание, что check/2
нигде не используется в коде, поэтому я опускаю его определение ниже.
Самый общий запрос
Когда я просматриваю код Пролога, о котором ничего не знаю, я всегда сначала пробую самый общий запрос, где все аргументы являются переменными. В идеале ответы показывают мне, как выглядят решения в целом.
Например, в вашем случае:
?- count(E, Ls, C).
Ls = [],
C = 0.
Это ошибочно предполагает, что существует только единственное решение вашего предиката! Это явно не предназначено.
Поэтому в качестве первого шага я рекомендую вам удалить !/0
и изменить этот код на:
count(_, [], 0).
count(El, [El|T], N) :-
count(El, T, N1),
N #= N1 + 1.
count(El, [Y|T], N) :-
El \= Y,
count(El, T, N).
После применения этого изменения мы получаем:
?- count(E, Ls, C).
Ls = [],
C = 0 ;
Ls = [E],
C = 1 ;
Ls = [E, E],
C = 2 ;
Ls = [E, E, E],
C = 3 .
Это выглядит намного лучше: теперь мы получили несколько правильных ответов.
Прекращение
Сколько ответов может дать этот предикат? В частности, существует ли только конечное количество ответов? Если это так, мы ожидаем, что следующий запрос будет завершен:
?- count(E, Ls, C), false.
Вы можете попробовать и убедиться, что на самом деле он не завершается (по крайней мере, не очень скоро). Это хороший знак, потому что при правильной реализации count/3
мы ожидаем незавершенности в самом общем случае!
Полнота
В идеале мы хотели бы, чтобы предикат был полным: он не должен пропускать действительные ответы.
Например:
?- count(E, [X,Y,Z], C).
E = X, X = Y, Y = Z,
C = 3 ;
false.
Это действительно все решения? Я так не думаю! Конечно, есть списки длиной 3, отличные от [E,E,E]
.
И ваша программа тоже в определенном смысле "знает" о них:
?- count(E, [1,2,3], C).
E = C, C = 1 ;
false.
Но опять же, это, конечно, не все случаи! Где ответы, в которых E
отличается от 1?
Вы столкнулись с этими проблемами, потому что используете предикат немонотонный (\=)/2
. У этого есть несколько очень сложных для понимания свойств, особенно если вы в настоящее время только начинаете изучать Пролог. Например:
?- X \= Y, X-Y = a-b.
false.
?- X-Y = a-b, X \= Y.
X = a,
Y = b.
Я рекомендую использовать dif/2
вместо этого, чтобы обозначить, что два термина разные, получив следующую версию:
count(_, [], 0).
count(El, [El|T], N) :-
count(El, T, N1),
N #= N1 + 1.
count(El, [Y|T], N) :-
dif(El, Y),
count(El, T, N).
С этой версией получаем:
?- count(E, [X,Y,Z], C).
E = X, X = Y, Y = Z,
C = 3 ;
E = X, X = Y,
C = 2,
dif(Y, Z) ;
E = X, X = Z,
C = 2,
dif(Z, Y) ;
etc.
И, в частности:
?- count(E, [1,2,3], C).
E = C, C = 1 ;
E = 2,
C = 1 ;
E = 3,
C = 1 ;
C = 0,
dif(E, 3),
dif(E, 2),
dif(E, 1).
Это покрывает все случаи, которые могут возникнуть!
Справедливый перечень
Поскольку предикат чистый и монотонный, мы можем использовать его для точного перечисления ответов с помощью итеративного углубления.
Например:
?- length(Ls, _), count(E, Ls, C).
Ls = [],
C = 0 ;
Ls = [E],
C = 1 ;
Ls = [_G588],
C = 0,
dif(E, _G588) ;
Ls = [E, E],
C = 2 ;
Ls = [E, _G597],
C = 1,
dif(E, _G597) .
C = 2 ;
etc.
Это довольно приятно и показывает, что мы можем использовать это как истинное отношение не только для подсчета, но и для генерации.
Следовательно, вы можете рассмотреть предикат имя, который более точно описывает, что этот предикат означает в целом. Я оставляю это как упражнение.
Хвостовая рекурсивная версия
Обратите внимание: поскольку вы используете чистые предикаты, вы можете свободно переупорядочивать свои цели и делать свой предикат хвостовым рекурсивным, что дает:
count(_, [], 0).
count(El, [El|T], N) :-
N #= N1 + 1,
count(El, T, N1).
count(El, [Y|T], N) :-
dif(El, Y),
count(El, T, N).
Детерминизм
В настоящее время у нас еще есть, например:
?- count(a, [a,a,a], Cs).
Cs = 3 ;
false.
Используя if_/3
, вы можете улучшить детерминизм этого предиката:
:- use_module(library(reif)).
count(_, [], 0).
count(E, [L|Ls], N) :-
if_(E=L, N #= N1 + 1, N #= N1),
count(E, Ls, N1).
Это делает ваш предикат как минимум поддающимся индексации. Улучшите ли вы детерминизм в таких случаях, зависит от механизма индексации вашей системы Prolog.
19.11.2016
:- use_module(library(clpfd)).
в начале, чтобы использовать декларативную целочисленную арифметику. 17.11.2016