Какая разница в исполнении, если вырезать "!" настоящее?

Question

counter([],[]).
counter([H|T],[[H,C1]|R]) :- counter(T,[[H,C]|R]),!, C1 is C+1.
counter([H|T],[[H,1]|R]) :- counter(T,R).

Каков эффект от "!" как я получаю один и тот же вывод для ввода кода выше и ниже?

 counter([],[]).
 counter([H|T],[[H,C1]|R]) :- counter(T,[[H,C]|R]),C1 is C+1.
 counter([H|T],[[H,1]|R]) :- counter(T,R).

Я новичок в Прологе.

Answer 1

Каков эффект от "!"

Разрез сокращает пространство поиска. То есть в остальной чистой и монотонной программе сокращение удалит некоторые решения или ответы. Пока это излишне, это нормально. Звучит так невинно и полезно, не так ли? Давайте посмотрим!

^{_{И чтобы я не забыл, используя}} [E,Nr] ^{_{обозначать пары довольно необычно, лучше использовать пару}} E-Nr ^_,

Теперь будем сравнивать counter_cut/2 а также counter_sans/2,

| ?- counter_cut([a,a],Xs).
     Xs = [[a,2]].

| ?- counter_sans([a,a],Xs).
     Xs = [[a, 2]]
  ;  Xs = [[a, 1], [a, 1]].     % <<< surprise !!!

Таким образом, у сокращенной версии есть меньше решений. Кажется решение counter_cut/2 сохранен является правильным. В этом очень частном случае. Будет ли это всегда правильно? Я попробую минимально более общий запрос:

| ?- counter_cut([a,B],Xs).
     B = a,
     Xs = [[a, 2]].

| ?- counter_sans([a,B],Xs).
     B = a,
     Xs = [[a, 2]]
  ;  Xs = [[a, 1], [B, 1]].

Снова, _sans болтливее, и на этот раз даже немного правее; для последнего ответа включает в себя B = b, Другими словами,

| ?- counter_cut([a,B], Xs), B = b.
     fails.              % incomplete !

| ?- counter_sans([a,B], Xs), B = b.
     B = b,
     Xs = [[a,1],[b,1]].

Так что иногда _cut версия лучше, а иногда _sans, Или, если говорить более прямо: оба они как-то не правы, но _sans -версия как минимум включает в себя все решения.

Вот "очищенная" версия, которая просто переписывает последнее правило в два разных случая: один для конца списка, а другой для другого элемента.

counter_pure([],[]).
counter_pure([H|T],[[H,C1]|R]) :- counter_pure(T,[[H,C]|R]), C1 is C+1.
counter_pure([H],[[H,1]]).
counter_pure([H,D|T],[[H,1]|R]) :- dif(H,D), counter_pure([D|T],R).

С точки зрения эффективности, которая не слишком известна.

Вот тестовый пример эффективности для системы с рациональной унификацией деревьев:

?- Es = [e|Es], counter(Es, Dict).
resource_error(stack).

Вместо этого реализация должна проходить плавно, по крайней мере, до конца этой вселенной. Строго говоря, этот запрос должен вызвать ошибку ресурса, но только после того, как он подсчитал число, намного большее, чем 10^100000000,

Answer 2

Вот мое чистое и, надеюсь, эффективное решение:

counter([X|L], C):- counter(L, X, 1, C).

counter([],X, Cnt, [[X,Cnt]]).
counter([Y|L], X, Cnt, [[X,Cnt]|C]):-
  dif(X, Y),
  counter(L, Y, 1, C).
counter([X|L],X, Cnt, [[X,XCnt]|C]):-
  Cnt1 #= Cnt+1,
  Cnt1 #=< XCnt,
  counter(L, X, Cnt1, [[X,XCnt]|C]).

---

С помощью if_3 как предложено @false:

counter([X|L], C):- counter(L, X, 1, C).

counter([],X, Cnt, [[X,Cnt]]).
counter([Y|L], X, Cnt, [[X,XCnt]|C]):-
  if_(X=Y,
    (
      Cnt1 #= Cnt+1,
      Cnt1 #=< XCnt,
      counter(L, X, Cnt1, [[X,XCnt]|C])
    ),
    (
      XCnt=Cnt,
      counter(L, Y, 1, C)
    )
  ).

Answer 3

Вот моя попытка использования if_/3:

counter([], []).
counter([H|T], [[H,C]|OutT] ):-
         if_( 
               T=[], 
               (C = 1,OutT=[]), 
               (
                 [H|T] = [H,H1|T2],
                 if_(
                       H=H1, 
                       (counter([H1|T2], [[H1,C1]|OutT]), C is C1+1),
                       (C = 1, counter([H1|T2], OutT))
                     )
               )  
            ).  

Answer 4

Режущий оператор ! фиксирует текущий путь деривации, обрезая все точки выбора. Учитывая некоторые факты

fact(a).
fact(b).

Вы можете сравнить ответы с и без разреза:

?- fact(X).
X = a ;
X = b.

?- fact(X), !.
X = a.

Как видите, общий запрос теперь сообщает только о своем первом успехе. Тем не менее, запрос

?- fact(b), !.
true.

преуспевает. Это значит, что крой нарушает интерпретацию , как логическое соединение:

?- X = b, fact(X), !.
X = b.

?- fact(X), !, X=b.
false.

но из нашего понимания соединения A unction B должно выполняться именно тогда, когда B exactly A выполняется. Так зачем вообще это делать?

• Эффективность: сокращения могут использоваться таким образом, что они изменяют только свойства выполнения, но не ответы предиката. Эти так называемые зеленые срезы описаны, например, в книге Ричарда О'Кифа " Craft of Prolog". Как показано выше, поддерживать правильность предиката с сокращением гораздо сложнее, чем без предиката, но, очевидно, правильность должна быть выше эффективности.

  Похоже, что ваша проблема была зеленой, но я не уверен на 100%, нет ли изменений в ответах.

• Отрицание: логическое отрицание в соответствии с предположением о замкнутом мире выражается вырезкой. Вы можете определить neg(X) как:

  neg(X) :-
    call(X),
    !,
    false.
  neg(_) :-
    true.
  

  Так что если call(X) успешно, мы отсекаем точку выбора для второго правила и получаем ложное. В противном случае ничего не вырезано, и мы получаем истину. Пожалуйста, имейте в виду, что это не отрицание в классической логике и что оно страдает от нелогических эффектов сокращения. Предположим, вы определили предикат land/1 быть одним из континентов:

  land(africa).
  land(america).
  land(antarctica).
  land(asia).
  land(australia).
  land(europe).
  

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

  water(X) :-
    neg(land(X)).
  

  тогда вы можете правильно получить:

  ?- water(pacific).
  true.
  
  ?- water(africa).
  false.
  

  Но вы также можете получить:

  ?- water(space).
  true.
  

  который не должен держать. В частности, в классической логике:

  land(africa) ∧
  land(america) ∧
  land(antarctica) ∧
  land(asia) ∧
  land(australia) ∧
  land(europe) → ¬ land(space).
  

  не является действительным. Опять же, вы должны хорошо знать, что вы делаете, если вы используете отрицание в Прологе.