Пролог дописывается с оператором вырезания

Какая проблема может возникнуть, когда мы используем команду append with cut?

   append2([],L,L):-!.
   append2([H|T],L,[H|TL]):-append2(T,L,TL).

Я пробовал несколько разных входов, но это всегда удается.

?- append2([1,2],[5],L).
L = [1, 2, 5].

?- append2([1,2],[1,2],L).
L = [1, 2, 1, 2].

?- append2([],[1,2],L).
L = [1, 2].

?- append2([1,2],[],L).
L = [1, 2].
Источник

4 ответа

Решение

Есть два вида порезов; зеленые порезы и красные порезы. Зеленые сокращения вставляются только для повышения эффективности и не меняют семантику программы. Красные порезы, с другой стороны, делают. По определению, зеленые порезы не вызывают никаких проблем.

Итак, есть ли способ изменить поведение, если бы не было разреза?

Посмотрим; для совпадения первого предложения L1 должен быть унифицируемым с [], L2 с L и L3 с L или, другими словами, L2 унифицируемым с L3.

Когда L1 равен [], второе предложение не может совпадать; так что разрез не имеет никакого эффекта

Когда L1 не создан: если длина L2 и L3 известна в этой точке, то они должны быть равны, иначе первое предложение не будет совпадать; таким образом, второе предложение не может совпадать, поскольку на каждом шаге длина L3 уменьшается на 1, и единственный способ завершить требует L2=L3

если длина L3 или L2 неизвестна: тогда у нас есть проблема, поскольку второе предложение может дать решения.

В самом деле:

    3 ?- append2(L1,L2,[1,2,3]).
    L1 = [],
    L2 = [1, 2, 3].

    4 ?- append2(L1,[1,2,3],L3).
    L1 = [],
    L3 = [1, 2, 3].

    5 ?- append2(L1,L2,L3).
    L1 = [],
    L2 = L3.

    6 ?- append2(L1,[E1,E2],L3).
    L1 = [],
    L2 = [E1, E2].

    7 ?- append2(L1,L2,[E1,E2]).
    L1 = [],
    L2 = [E1, E2].

пока мы ожидаем:

8 ?- append(L1,L2,[1,2,3]).
L1 = [],
L2 = [1, 2, 3] ;
L1 = [1],
L2 = [2, 3] ;
L1 = [1, 2],
L2 = [3] ;
L1 = [1, 2, 3],
L2 = [] ;
false.

9 ?- append(L1,[1,2,3],L3).
L1 = [],
L3 = [1, 2, 3] ;
L1 = [_G24],
L3 = [_G24, 1, 2, 3] ;
L1 = [_G24, _G30],
L3 = [_G24, _G30, 1, 2, 3] ;
L1 = [_G24, _G30, _G36],
L3 = [_G24, _G30, _G36, 1, 2, 3] ;
L1 = [_G24, _G30, _G36, _G42],
L3 = [_G24, _G30, _G36, _G42, 1, 2, 3] ;
...

10 ?- append(L1,L2,L3).
L1 = [],
L2 = L3 ;
L1 = [_G22],
L3 = [_G22|L2] ;
L1 = [_G22, _G28],
L3 = [_G22, _G28|L2] ;
....

11 ?- append(L1,[E1,E2],L3).
L1 = [],
L3 = [E1, E2] ;
L1 = [_G78],
L3 = [_G78, E1, E2] ;
L1 = [_G78, _G84],
L3 = [_G78, _G84, E1, E2] ;
L1 = [_G78, _G84, _G90],
L3 = [_G78, _G84, _G90, E1, E2] ;
...

12 ?- append(L1,L2,[E1,E2]).
L1 = [],
L2 = [E1, E2] ;
L1 = [E1],
L2 = [E2] ;
L1 = [E1, E2],
L2 = [] ;
false.
Источник

Иногда действительно имеет смысл вводить зеленые срезы - даже в append/3Но нужно позаботиться о том, чтобы такой срез оставался зеленым. То есть сокращение, которое действительно повышает эффективность (на определенном уровне) и не влияет на ответы.

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

Из этого эмпирического правила очень мало исключений. Например, вы можете добавить разрез после переменной свободной цели, при условии, что больше нет правила и т. Д. Это определенно хорошая тренировка, чтобы попытаться выяснить случаи, на которые влияет разрез.

Но вернемся к вашей программе append2/3, В настоящее время сокращение всегда сокращает, даже если применяется альтернативное правило, и в этом случае сокращение удаляет ответы, чего мы хотим избежать.

Так когда же первый пункт станет единственным актуальным?

Если первый аргумент []таким образом append2([], Xs, Ys). - но также, если последний аргумент [] (Есть еще больше случаев, которые являются более сложными). Давайте попробуем оба случая с оригинальным определением без вырезов:

? - добавить ([], Ys, Zs).
Ys = Zs.?- добавить (Xs, Ys, []).
Xs = Ys, Ys = [];
ложный.

Таким образом, в первом случае система смогла сразу определить, что существует единственное решение, и при этом дать ответ. Во втором случае, однако, система Пролог не была уверена, будет ли необходим другой ответ - она, так сказать, "оставила точку выбора открытой". Это жаль, поскольку довольно просто определить, что и в этом случае существует только один ответ. Сокращение было бы идеальным здесь, чтобы помочь. Но неосторожный порез приносит больше вреда, чем помогает.

Сокращение может сократить, если третий аргумент []:

append3(Xs, Ys, Zs) :-
   (  Zs == [] -> ! ; true ),
   Xs = [],
   Ys = Zs.
append3([X|Xs], Ys, [X|Zs]) :-
   append3(Xs, Ys, Zs).

Эта программа теперь более эффективна в том смысле, что она не оставляет открытой точку выбора, если известен только третий аргумент.

? - добавить (Xs,Ys,[1]).
Xs = [],
Ys = [1];
Xs = [1],
Ys = [];
ложный.?- append3(Xs,Ys,[1]).
Xs = [],
Ys = [1];
Xs = [1],
Ys = [].

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

Источник

Попробуйте, например, самый общий запрос:

?- append2(X, Y, Z).
Источник

Это не будет работать, когда первые два аргумента являются переменными:

?- append(X, Y, [1, 2, 3]).
X = [],
Y = [1, 2, 3] ;
X = [1],
Y = [2, 3] ;
X = [1, 2],
Y = [3] ;
X = [1, 2, 3],
Y = [] ;
false.

?- append2(X, Y, [1, 2, 3]).
X = [],
Y = [1, 2, 3].
Источник
Другие вопросы по тегам