Пролог, что такое Аккумуляторы и функция \ + member - PullRequest
Новая
       37

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

1 голос
/ 14 января 2012

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

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

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

\+member

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

Большое спасибо за любую помощь по этим двум вопросам.

1 Ответ

8 голосов
/ 14 января 2012

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

?- 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.Если это неясно, просто сделайте след обоих!

...