Как использовать разностные списки в интерпретаторе Prolog

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

Я тестировал это на SWI-Prolog, а также на SICStus. Я проверил обозначение, так как это описано в Bratko Prolog Programming for AI, стр. 210, но, судя по всему, объединение невозможно. Почему это? Разве эти обозначения не имеют того же декларативного значения?

Ответы

Ответ 1

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

L=-( |(a, |(b, |(c, |(d, |(e, []))))), |(d, |(e, [] )))

где -/2 и |/2 являются функторами, а a, b, c, d, e и [] являются константами.

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

Скажите, что вы хотите append/3 два списка. Вы можете сделать это следующим образом:

%append(A,B,C).
append([],L,L).
append([H|T],L,[H|B]) :-
    append(T,L,B).

Но это выполняется в O (n): сначала нужно выполнить итерацию по всему первому списку. Если этот список содержит тысячи элементов, это займет много времени.

Теперь вы можете определить самостоятельно контракт, в котором вы отправите append_diff/3 не только список, но кортеж -(List,Tail), где List является ссылкой на начало списка, и Tail является ссылкой на конец не унифицированного списка. Примерами структур, удовлетворяющих этому требованию, являются Tail-Tail, [a|Tail]-Tail, [1,4,2,5|Tail]-Tail.

Теперь вы можете эффективно append_diff/3 в O (1) с помощью:

append_diff(H1-T1,T1-T2,H1-T2).

Почему? Потому что вы объедините ununified хвост первого списка со вторым списком. Теперь необработанный хвост вторых списков становится хвостом окончательного списка. Так возьмите, например:

append_diff([a|T1]-T1,[1,4,2,5|T2]-T2,L).

Если вы вызываете предикат, как вы видите выше, T1 объединяется с [1,4,2,5|T2], так что теперь первый список сбрасывается до [a|[1,4,2,5|T2]] или короче [a,1,4,2,5|T2], так как мы также имеем ссылку на T2, мы можем "вернуть" (в Prolog ничего не возвращается), [a,1,4,2,5|T2]-T2: новый список различий с открытым хвостом T2. Но это только потому, что вы даете - особое значение: для Prolog - просто -, это не минус, он не вычисляет разницу и т.д. Prolog does не прикреплять семантику к функторам. Если бы вы использовали + вместо -, это не имело бы малейшей разницы.

Итак, вернемся к вашему вопросу: вы просто указываете Prolog, что L = -([a,b,c,d,e],[d,e]) и позже укажите L = [a,b,c]. Теперь ясно, что эти два выражения не могут быть унифицированы. Итак, Prolog говорит false.