Prolog: подсчет вхождений элемента в список, возвращающий несколько ответов

Question

У меня проблемы с чем-то. Я написал функцию, которая возвращает количество вхождений элемента в список. Вот код:

occurencesHelp(X,[],N,N). 

occurencesHelp(X,[X|T],N,Y) :- 
    N1 is N+1, 
    occurencesHelp(X,T,N1,Y). 

occurencesHelp(X,[H|T],N,Y) :- 
    occurencesHelp(X,T,N,Y). 

occurences(X,List,N) :- 
    occurencesHelp(X,List,0,N). 

Это работает отлично, первый ответ, который я получаю:

N = 5 ? 

но есть несколько ответов, таких как:

N = 4 ? ; 
N = 4 ? ; 
N = 3 ? ; 
N = 4 ? ; 
N = 3 ? ; 

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

Спасибо.

Answer 1

Когда я загружаю свой код в SWI-Prolog, я получаю следующие предупреждения:

Warning: /home/isabelle/occ.pl:1: 
    Singleton variables: [X] 
Warning: /home/isabelle/occ.pl:7: 
    Singleton variables: [H] 

Эти предупреждения важную. Синглтонские переменные очень часто являются признаком того, что вы сделали серьезную логическую ошибку. В вашем случае, давайте посмотрим на линии 7. Именно в этом пункте:

occurencesHelp(X,[H|T],N,Y) :- 
    occurencesHelp(X,T,N,Y). 

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

В предыдущем пункте говорится (процедурно): «если глава списка X, увеличивайте счетчик». И наоборот, в этом пункте следует сказать: «если глава списка неX, сохраните счетчик без изменений». Но он не говорит об этом в списке: на самом деле он ничего не говорит о H (отсюда предупреждение).

Так что вам нужно добавить цель, выражающую тот факт, что X и H должны быть неравными. Два способа выразить это: X \= H и dif(X, H). В вашем случае выбор зависит от того, что вы уже узнали в своем курсе.

(Предупреждение синглтон для линии 1 является доброкачественной в этом случае,. Вы можете просто заменить X на _X сказать Пролог, что вы явно хотите, чтобы игнорировать эту переменную)