Пролог, что такое аккумуляторы и функция \+member

Я искал учебники о том, что такое аккумуляторы и что они делают, однако все объяснения кажутся очень сложными и на самом деле не дают мне достаточно четкого представления о том, как они работают, чтобы я мог их использовать. Кажется, я понимаю, что аккумуляторы удерживают что-то вроде числа, которое затем может быть вызвано другими фрагментами кода и изменено. Проблема в том, что хотя я понимаю, что такое аккумулятор, и знаю, когда он мне нужен, я не слишком уверен, как его использовать.

Я имею в виду из руководств, которые я видел, иногда аккумулятор кажется пустым списком, а иногда он кажется «0», оставляя меня в недоумении, что именно можно считать аккумулятором, а что нет. Может кто-нибудь объяснить мне простыми словами, как именно можно использовать аккумулятор?

Также во второй части моего вопроса я, кажется, заметил, что люди часто используют это в своих кодах пролога:

\+member

Мне удалось сделать вывод, что это как-то связано со списками, поскольку я всегда вижу, что оно используется внутри строки кода, которая что-то делает со списком, однако после поиска я обнаружил, что на самом деле \+member означает отрицание как отказ, а не доказуемо, хотя я действительно не понимаю, что это значит, и даже если этот человек был прав. Опять же, может кто-нибудь объяснить мне, что именно делает \+member и для чего его можно использовать, пытаясь сохранить простоту объяснения, большие слова меня смущают.


member rules accumulator prolog negation
person Arun22    schedule 14.01.2012    source источник

Ответы (1)


arrow_upward
8
arrow_downward

Во-первых, \+ — это отрицание цели. Он преуспевает, когда цель, следующая за ним, терпит неудачу. Например:

?- member(3, [1,2,3]). # 3 is a member of the List
true.

?- member(4, [1,2,3]). # 4 is not a member
false.

?- \+member(4, [1,2,3]). # succeeds, because 'member' fails
true.

?- \+member(3, [1,2,3]).
false.

?- atom_chars('hi', C).
C = [h, i].

?- atom_chars('hi', [h, i]).
true.

?- atom_chars('hello', [h, i]).
false.

?- \+atom_chars('hello', [h, i]).
true.

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

Рассмотрим эти два эквивалентных способа вычисления факториала:

?- [user].
|: fact_simple(0, 1).
|: fact_simple(N, F) :- 
         N1 is N-1, 
         fact_simple(N1, F1), 
         F is N*F1.
|: % user://2 compiled 0.00 sec, 440 bytes
true.

?- fact_simple(6, F).
F = 720 .

[user].
|: fact_acc(N, F) :- fact_acc(N, 1, F).
|: fact_acc(0, Acc, Acc).
|: fact_acc(N, Acc0, F) :- 
         N1 is N-1, 
         Acc is Acc0 * N, 
         fact_acc(N1, Acc, F).
|: % user://4 compiled 0.00 sec, 1,912 bytes
true.

?- fact_acc(6, F).
F = 720 .

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

Во второй версии вместо этого используется аккумулятор (Acc). Обратите внимание, что 1 — это не аккумулятор, а начальное значение. После этого каждый вызов предиката умножает его N-значение на аккумулятор, и когда рекурсия достигает своего базового случая, значение аккумулятора уже является окончательным значением.

На самом деле вопрос не в том, «каким может быть аккумулятор?». (0 или пустой список или что-то еще). Это просто способ накапливать значения «по ходу» и никогда не возвращаться к предикату вызова. Таким образом, системе Prolog не нужно создавать постоянно растущий стек вызовов.

Обратите внимание, однако, что в этом примере порядок умножения, естественно, обратный. Это не имеет значения для умножения, но для других значений (например, списков) нужно позаботиться об этом.

fact_simple сделал умножение как 1 * 2 * 3 * 4 * 5 * 6, а fact_acc как 1 * 6 * 5 * 4 * 3 * 2. Если это неясно, просто сделайте след обоих!

person firefrorefiddle    schedule 14.01.2012
comment
Пожалуйста. Я просто хотел бы добавить, что «шаблон» аккумулятора не является специфичным для пролога, а скорее является элементом функционального программирования. - person firefrorefiddle; 15.01.2012