Разница между "открытыми списками" и "списками различий"
В чем разница между "открытыми списками" и "списками различий"?
3 ответа
Оба понятия кажутся списками, но на самом деле это не так. Один - конкретный термин, другой - скорее конвенция.
Открытые списки, частичные списки
Открытые списки - это термины, которые не являются списками, но могут быть созданы так, что они становятся списками. В стандартном жаргоне они называются частичными списками. Вот частичные списки: X, [a|X], [X|X] все частичные списки.
Понятие открытых списков предполагает определенное использование таких списков для имитации некоторого открытого состояния. Подумайте о словаре, который может быть представлен открытым списком. Каждый раз, когда вы добавляете новый элемент, переменная "в конце частичного списка" создается для нового элемента. Хотя эта техника программирования вполне возможна в Прологе, у нее есть один большой недостаток: программы будут сильно зависеть от процедурной интерпретации. И во многих ситуациях вообще невозможно иметь декларативное толкование.
Списки различий
Списки различий фактически являются не списками как таковыми, а определенным образом, как списки используются таким образом, что предполагаемый список представляется двумя переменными: одна для начала и одна для конца списка. По этой причине было бы очень полезно говорить о различиях в списках, а не в списках различий.
Рассматривать:
el(E, [E|L],L).
Здесь последние два аргумента можно рассматривать как формирующие разницу: список, содержащий единственный элемент [E], Теперь вы можете создавать более сложные списки из более простых, если вы соблюдаете определенные соглашения, которые, по сути, заключаются в том, что второй аргумент только передается дальше. Различия как таковые никогда не сравниваются друг с другом!
el2(E, F, L0,L) :-
el(E, L0,L1),
el(F, L1,L).
Обратите внимание, что это просто соглашение. Списки не применяются. Думать о:
?- el2(E, F, L, nonlist).
L = [E,F|nonlist].
Этот метод также используется для кодирования DCG.
Как описано на http://homepages.inf.ed.ac.uk/pbrna/prologbook/node180.html, открытый список - это инструмент, используемый для реализации списка различий.
Открытый список - это любой список, в котором у вас есть неназначенная переменная в некоторой точке списка, например: [a,b,c|X], Вы можете использовать открытый список для реализации структуры данных, называемой списком различий, которая формально задает структуру из двух терминов, указывающих на первый элемент и на открытый конец, традиционно определяемых как: [a,b,c|X]-X, чтобы сделать работу с такими списками проще.
Например, если у вас есть только открытый список, добавление элемента в конец возможно, но вам нужно перебрать все элементы. В списке различий вы можете просто использовать переменную конца списка (называемую Hole на странице выше), чтобы пропустить итерацию и выполнить операцию в постоянное время.