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

Question

Я изучаю пролог и хочу посчитать конкретный элемент в списке.

Так вот код -

count(_, [], _) := !.

count(El, [El|T], N) :-
    N1 is N + 1,
    count(El, T, N1).

count(El, [_|T], N) :-
    count(El, T, N).

check(List1, List2) :-
    count(3, List1, M),
    count(2, List2, N),
    M is N.

так что в основном я хотел бы перейти к проверке консоли ([3,4,3], [2,3,4,5,2]), и она должна возвращать true, потому что вхождения 3 в list1 совпадают с вхождениями 2 в списке2. Но вместо этого это бросает меня -

Arguments are not sufficiently instantiated. 
Exception: (10) _G1383 is _L155+1 ? creep
Exception: (9) count(3, [3, 4, 2], _G1385) ? creep
Exception: (8) count(3, [2, 3, 4, 2], _G1385) ? creep
Exception: (7) check([2, 3, 4, 2], [2, 3, 4]) ? creep 

В чем причина этого и как я могу ее решить? Я проверил все вокруг форума, и везде написано, что это должно работать. Это что-то вроде версии, или я что-то здесь упускаю?

РЕДАКТИРОВАТЬ: Использование SWI-Пролог.

EDIT2:

Работай, спасибо!

Код:

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.

Answer 1

Вы используете предикаты, которые называются модовыми, потому что они могут использоваться только в очень специфических ситуациях. Особенно, (is)/2 не может использоваться как отношение, как вам нужно здесь.

Один из способов решить эту проблему - использовать более общие предикаты. Например, при рассуждении над целыми числами рассмотрите возможность использования ограничений CLP(FD) вашей системы Prolog, которые работают во всех направлениях.

Например, с помощью GNU Prolog вы можете устранить ошибку, если просто замените (is)/2 от (#=)/2:

считать (_, [], _).

рассчитывать (El, [El|T], N):-
    N1 #= N + 1,
    считать (El, T, N1).

рассчитывать (El, [_|T], N):-
    считать (El, T, N).

проверить (List1, List2):-
    считать (3, List1, M),
    count(2, List2, N),
    М # = Н.

Теперь мы получаем:

? - считать (3, [3, 4, 2], С).
С +1#=_1204; 
 правда; 
 ложь

(или, в зависимости от вашей системы Prolog, эквивалентный ответ).

Почему? Очевидно, что программа немного ошибочна.

Я оставляю поиск ошибки в качестве упражнения. Подсказка: M #= N выглядит подозрительно: это правда, если M равно N...

Answer 2

Здорово, что теперь вы работаете, используя декларативную арифметику!

У меня есть несколько небольших дополнительных комментариев о решении, которое вы получили, а именно:

считать (_, [], 0):-!.

рассчитывать (El, [El|T], N):-
    рассчитывать (El, T, N1),
    N #= N1 + 1.

рассчитывать (El, [Y|T], N):-
    El \= Y,
    считать (El, T, N).

проверить (List1, List2):-
    считать (3, List1, M),
    count(2, List2, N),
    М # = Н.

Во-первых, обратите внимание, что check/2 в коде нигде не используется, поэтому я опущу его определение в следующем.

Самый общий запрос

Когда я просматриваю код Prolog, о котором ничего не знаю, я всегда сначала пробую самый общий запрос, где все аргументы являются переменными. В идеале ответы показывают, как выглядят решения в целом.

Например, в вашем случае:

? - считать (E, Ls, C).
Ls = [], 
 С = 0.

Это - ошибочно - предполагает, что существует только одно решение вашего предиката! Это явно не предназначено.

Поэтому в качестве первого шага я рекомендую вам удалить !/0 и измените этот код на:

считать (_, [], 0).

рассчитывать (El, [El|T], N):-
    рассчитывать (El, T, N1),
    N #= N1 + 1.

рассчитывать (El, [Y|T], N):-
    El \= Y,
    считать (El, T, N).

С этим изменением мы получаем:

? - считать (E, Ls, C).
Ls = [], 
 С = 0; 
 Ls = [E], 
 С = 1; 
 Ls = [E, E], 
 С = 2; 
 Ls = [E, E, E], 
 С = 3.

Это выглядит намного лучше: теперь мы получаем несколько правильных ответов.

прекращение

Сколько ответов может дать этот предикат? В частности, есть только конечное число ответов? Если это так, мы ожидаем, что следующий запрос завершится:

? - считать (E, Ls, C), ложь.

Вы можете попробовать это, и увидите, что это на самом деле не заканчивается (по крайней мере, не очень скоро). Это хороший знак, потому что от правильной реализации count/3 Мы ожидаем нетерминации в самом общем случае!

завершенность

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

Например:

? - считать (E, [X, Y, Z], C).
E = X, X = Y, Y = Z, 
 С = 3;
ложный.

Это действительно все решения? Я так не думаю! Конечно, есть списки длиной 3, которые отличаются от [E,E,E],

И фактически ваша программа также "знает" о них в некотором смысле:

? - считать (E, [1,2,3], C).
E = C, C = 1;
ложный.

Но опять же, это, конечно, не все случаи! Где ответы, в которых E отличается от 1?

Вы сталкиваетесь с этими проблемами, потому что вы используете немонотонный (\=)/2 сказуемое. У этого есть несколько очень трудных для понимания свойств, особенно если вы в настоящее время только начинаете изучать Пролог. Например:

?- X \ = Y, XY = ab.
ложь?- XY = ab, X \= Y.
Х = а, 
 Y = б.

Я рекомендую использовать dif/2 вместо этого, чтобы обозначить, что два условия различны, получая следующую версию:

считать (_, [], 0).

рассчитывать (El, [El|T], N):-
    рассчитывать (El, T, N1),
    N #= N1 + 1.

рассчитывать (El, [Y | T], N): -
    диф (Эл, Y),
    считать (El, T, N).

С этой версией мы получаем:

? - считать (E, [X, Y, Z], C).
E = X, X = Y, Y = Z, 
 С = 3; 
 E = X, X = Y, 
 С = 2, 
 диф (Y, Z); 
 E = X, X = Z, 
 С = 2, 
 диф (Z, Y);
и т.п.

И, в частности:

? - считать (E, [1,2,3], C).
E = C, C = 1; 
 Е = 2, 
 С = 1; 
 Е = 3, 
 С = 1; 
 С = 0, 
 диф (Е, 3), 
 диф (Е, 2), 
 диф (Е, 1).

Это охватывает все случаи, которые могут возникнуть!

Справедливое перечисление

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

Например:

? - длина (Ls, _), отсчет (E, Ls, C).
Ls = [], 
 С = 0; 
 Ls = [E], 
 С = 1; 
 Ls = [_G588], 
 С = 0, 
 диф (E, _G588); 
 Ls = [E, E], 
 С = 2; 
 Ls = [E, _G597], 
 С = 1, 
 диф (E, _G597) . 
 С = 2;
и т.п.

Это довольно хорошо, и показывает, что мы можем использовать это как истинное отношение, не только для подсчета, но и для генерации.

Следовательно, вы можете рассмотреть имя предиката, которое более уместно описывает, что этот предикат означает в целом. Я оставляю это как упражнение.

Хвост рекурсивная версия

Обратите внимание, что, поскольку вы используете чистые предикаты, вы можете свободно изменять порядок своих целей и делать свой хвост предиката рекурсивным, получая:

считать (_, [], 0).
рассчитывать (El, [El|T], N):-
    N #= N1 + 1,
    считать (El, T, N1).
рассчитывать (El, [Y | T], N): -
    диф (Эл, Y),
    считать (El, T, N).

Детерминизм

В настоящее время у нас еще есть, например:

? - считать (a, [a, a, a], Cs).
Cs = 3 ;
ложь

С помощью if_/3 Вы можете улучшить детерминизм этого предиката:

: - use_module ( библиотека (reif)). считать (_, [], 0). count (E, [L | Ls], N): - if_ (E = L, N # = N1 + 1, N # = N1), count (E, Ls, N1). 

Это делает ваш предикат как минимум поддающимся индексации. Улучшите ли вы детерминизм в таких случаях, зависит от механизма индексации вашей системы Prolog.