Пролог: избегайте избыточных точек выбора (без детерминизма) с оператором cut и без него

Question

Во-первых, я прочитал все другие сообщения о SO относительно использования разрезов в Prolog и определенно вижу проблемы, связанные с их использованием. Тем не менее, для меня все еще есть какая-то несклонность, и я хотел бы разобраться в этом раз и навсегда.

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

base([]). 
base([_]). 
base([_,H|T]) :- H =:= 1, base(T). 

При выполнении:

?- time(base([1])). 
    % 0 inferences, 0.000 CPU in 0.000 seconds (74% CPU, 0 Lips) 
    true ; 
    % 2 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 99502 Lips) 
    false. 

?- time(base([3,1,3])). 
    % 2 inferences, 0.000 CPU in 0.000 seconds (79% CPU, 304044 Lips) 
    true ; 
    % 2 inferences, 0.000 CPU in 0.000 seconds (84% CPU, 122632 Lips) 
    false. 

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

base([]). 
base([_]) :- !. 
base([_,H|T]) :- H =:= 1, base(T). 

Теперь мы получаем:

?- time(base([1])). 
    % 1 inferences, 0.000 CPU in 0.000 seconds (81% CPU, 49419 Lips) 
    true. 

?- time(base([3,1,3])). 
    % 3 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 388500 Lips) 
    true. 

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

Переходя однако, можно было бы изменить положение дела следующим образом:

base([_,H|T]) :- H =:= 1, base(T). 
base([_]). 
base([]). 

который также покончит с резервированием точки выбора без разреза, но, конечно, мы бы просто сдвигать точку выбора для запросов со списками с четным количеством цифр, как показано ниже:

?- time(base([3,1])). 
% 2 inferences, 0.000 CPU in 0.000 seconds (82% CPU, 99157 Lips) 
true ; 
% 2 inferences, 0.000 CPU in 0.000 seconds (85% CPU, 96632 Lips) 
false. 

Таким образом, это также не является решением. Однако мы могли бы адаптировать этот порядок правил с разрезом, как показано ниже:

, поскольку на самом деле не оставлять никаких точек выбора. Глядя на некоторых запросах:

?- time(base([3])). 
% 1 inferences, 0.000 CPU in 0.000 seconds (81% CPU, 157679 Lips) 
true. 

?- time(base([3,1])). 
% 3 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 138447 Lips) 
true. 

?- time(base([3,1,3])). 
% 3 inferences, 0.000 CPU in 0.000 seconds (82% CPU, 393649 Lips) 
true. 

Однако, опять же, поведение этого отруба работает корректно только из-за упорядочение правил. Если кто-то переставить базовые случаи назад к первоначальной форме, как показано ниже:

base([]). 
base([_]). 
base([_,H|T]) :- H =:= 1, base(T), !. 

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

?- time(base([1])). 
    % 0 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 0 Lips) 
    true ; 
    % 2 inferences, 0.000 CPU in 0.000 seconds (84% CPU, 119546 Lips) 
    false. 

В этих рода сценариев, я всегда использовал один разрез во втором базовом случае, поскольку я единственный, кто когда-либо просматривал мой код, и я привык к нему. Тем не менее, мне сказали в одном из моих ответов на другом сообщении SO, что это не рекомендуется использовать оператора cut и я должен стараться избегать его как можно больше.

Это подводит меня к двудольному вопросу:

• Если разрез, независимо от положения правила, в которых он присутствует, но изменяет поведения, но не решения (как в приведенных выше примерах), по-прежнему считается плохой практикой?

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

Заранее благодарен!

Answer 1

Всегда стараться избегать !/0. Почти всегда !/0 полностью уничтожает декларативную семантику вашей программы.

Все, что может быть выражен шаблоном должны быть выраженно сопоставлением с образцом. В вашем примере:

 
every_second([]). 
every_second([_|Ls]) :- 
     every_second_(Ls). 

every_second_([]). 
every_second_([1|Rest]) :- every_second(Rest). 

Как в вашей нечистой версии, нет выбора точек вообще не останутся на примеры вы вывешенные:

 
?- every_second([1]). 
true. 

?- every_second([3,1]). 
true. 

?- every_second([3,1,3]). 
true. 

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

 
?- every_second(Ls). 
Ls = [] ; 
Ls = [_G774] ; 
Ls = [_G774, 1] ; 
Ls = [_G774, 1, _G780] ; 
Ls = [_G774, 1, _G780, 1] . 

Ни одна из версий вы вывешенные может сделать это, из-за нечистым или неиспользованию -декларативные предикаты (!/0, (=:=)/2) вы используете!

Когда вы рассуждаете о списках, вы можете почти всегда использовать сопоставление образцов, чтобы различать случаи. Если это невозможно, используйте, например, if_/3 для логической чистоты, сохраняя при этом приемлемую производительность.

Answer 2

Хитрость заключается в «Выделка» над числом unbounds в правиле:

base([]). 
base([_|Q]) :- base2(Q). 

base2([]). 
base2([H|Q]) :- H =:= 1, base(Q). 

Однако, это плохое правило сказать, порезы плохо. На самом деле, мой любимый будет:

base([]) :- !. 
base([_]) :- !. 
base([_,H|Q]) :- !, H =:= 1, base(Q). 

Вещь об этом примере primes(++):

primes([5]). 
primes([7]). 
primes([11]). 

против

primes([5]) :- !. 
primes([7]) :- !. 
primes([11]) :- !.