пролог: исправление нескольких ответов (используя cut?)

я подсчитываю количество экземпляров в списке...

count(_,[],N,N).
count(Elem,[Elem|List],N,M) :- !, N1 is N+1, count(Elem,List,N1,M). 
count(Elem,[_|List],N,M) :- count(Elem,List,N,M).

Итак, я написал это двумя способами в прологе, и первый работает (выше), но мне было любопытно узнать, почему второй не работает (или, скорее, даст мне несколько ответов - только первый из которых правильный), почему это?

огромное спасибо

count(Z,X,R) :- count2(Z,X,R,0).
count2(W,[H|T],L,A):- (W == H), Lnew is A+1, count2(W,T,L,Lnew).
count2(W,[H|T],L,A):- count2(W,T,L,A).
count2(W,[],A,A).

prolog
person v_a_bhatia    schedule 17.12.2009    source источник

Ответы (3)


arrow_upward
2
arrow_downward

Причина, по которой ваша вторая попытка дает несколько решений, заключается в том, что второе предложение count2 не препятствует тому, чтобы W и H принимали одинаковые значения. Таким образом, даже если первое предложение count2 выполнено успешно, оно может вернуться и снова преуспеть во втором предложении.

Вы можете исправить это, используя сокращение, как говорит Винсент Рамдхани, или, если вы предпочитаете избегать использования сокращения, вы можете просто добавить явную проверку во втором предложении, чтобы предотвратить объединение W и H, например:

count(Z,X,R) :- count2(Z,X,R,0).
count2(W,[W|T],L,A):- Lnew is A+1, count2(W,T,L,Lnew).
count2(W,[H|T],L,A):- W \= H, count2(W,T,L,A).
count2(_,[],A,A).

Также обратите внимание, что первое предложение count2 теперь использует неявную унификацию. Вместо явной проверки. Это немного короче и легче для чтения, на мой взгляд. Если, конечно, не было причины, по которой вы использовали равенство, а не унификацию.

person nedned    schedule 18.12.2009

arrow_upward
0
arrow_downward

Ваш вопрос включает в себя ответ ... порез. Разрез всегда успешен и имеет побочный эффект «отрезания» дерева вывода. По сути, вы не можете вернуться назад, чтобы пройти разрез.

Первый пример выполнит разрез, если цель согласуется со вторым правилом. В некотором смысле этот выбор становится фиксированным. Если есть сбой или откат после того, как он не отходит от разреза, что устраняет несколько ответов. Разрез полезен, когда ответы взаимоисключающие. То есть, когда вы найдете первый ответ, другие не будут иметь смысла.

person Vincent Ramdhanie    schedule 17.12.2009
comment
я попробовал второй с разрезом, так что: count(Z,X,R):- count2(Z,X,R,0). count2(W,[H|T],L,A):- !, (W == H), Lnew равно A+1, count2(W,T,L,Lnew). count2(W,[H|T],L,A):- count2(W,T,L,A). count2(W,[],A,A). но это, похоже, тоже не работает, поэтому я подумал, что, возможно, код как-то в корне ошибочен. - person v_a_bhatia; 18.12.2009

arrow_upward
-1
arrow_downward

понятно!

вот решение, которое работает:

count(Z,X,R) :- count2(Z,X,R,0).
count2(W,[H|T],L,A):- (W == H), !, Lnew is A+1, count2(W,T,L,Lnew).
count2(W,[H|T],L,A):- count2(W,T,L,A).
count2(W,[],A,A).

Спасибо, Винсент, ты заставил меня пересмотреть версию!

person v_a_bhatia    schedule 17.12.2009
comment
Решение, которое работает? Нет! Обратите внимание на пагубные последствия использования (!)/0: это повышает уверенность программистов в правильности кода, в то же время (в то же время) делая код хрупким/сломанным без возможности восстановления. - person repeat; 24.10.2015