Клонирование, Копирование списка прологов - PullRequest
Новая
       42

Клонирование, Копирование списка прологов

3 голосов
/ 23 декабря 2019

Я нашел этот фрагмент кода везде для копирования списка или его клонирования.

Код, найденный везде: 

clone([],[]).
clone([H|T],[H|Z]):- clone(T,Z).

?-clone([1,2,3],Z).
  Z=[1,2,3]

?-clone(2,Z).
  false

Это не копирует ничего, кроме lists. Временная сложность приведенного выше кода составляет O(n).

Но Пролог пытается объединить право и поднять сторону, верно? Это можно записать гораздо проще, верно?

Как и clone1(Z,Z).: 

clone1(Z,Z).

?-clone1([1,2,3],Z).
  Z=[1,2,3]
?-clone1(1,Z).
  Z=1
?-clone1(!,Z).
  Z =!
?-clone1(@,Z).
  Z=(@)

Я чувствую, что clone1(X, X). гораздо более универсален и клонирует почти все, что ему передано. Он не клонировал %, (, ), (). clone1(%,Z) не удалось с сообщением % - used for commenting. Сложность времени clone1 составляет O(1) Я могу ошибаться. В каждом аспекте clone1 намного лучше, чем clone.

Почему этот клон / копия написан не так, например, clone(X, X). Чего мне не хватает? Пожалуйста, объясните мне разницу между обоими кодами, которые я предоставил выше. Если оба делают то же самое, почему clone1(X, X). не используется, и никто не написал об этом.

Ответы [ 2 ]

5 голосов
/ 23 декабря 2019

Нужно иметь в виду, что именно вы подразумеваете под «клоном» или «копией». Что происходит с переменными?

Например, если вы используете унификацию для клонирования, то: 

| ?- L1 = [1,2,X], L2 = L1.

L1 = [1,2,X]
L2 = [1,2,X]

yes
| ?- L1 = [1,2,X], L2 = L1, X = a.

L1 = [1,2,a]
L2 = [1,2,a]
X = a

yes
| ?-

Другими словами, с унификацией, любые соответствующие переменные, которые «копируются» или «клонируются»«таким образом, оставайтесь унифицированными (поскольку термины унифицированы).

Если вы хотите новые переменные, когда вы« клонируете »или« копируете », вы захотите использовать пролог copy_term/2: 

| ?-  L1 = [1,2,X], copy_term(L1, L2), X = a.

L1 = [1,2,a]
L2 = [1,2,_]
X = a

yes
| ?-

Так что теперь L2 является копией L1 с собственной переменной на 3-й позиции в списке.

2 голосов
/ 23 декабря 2019

Вызов clone1(Z,Z2) - это то же самое, что Z = Z2. Что еще более просто.

Разница в том, что, как вы сами отметили, clone/2 работает только для списков, а =/2 - для всех допустимых терминов Пролога.

Еще одно замечание к коду - узнать об обработке списков в Прологе;чтобы он послужил основой для других рекурсивных задач по обработке списков, которые вы, возможно, захотите написать. Как отображение, фильтрация, подсчет и т. Д.

Книга Стерлинга и Шапиро называет такой код скелетный код для определенного типа данных.

...