Ћекции.ќрг


ѕоиск:




 атегории:

јстрономи€
Ѕиологи€
√еографи€
ƒругие €зыки
»нтернет
»нформатика
»стори€
 ультура
Ћитература
Ћогика
ћатематика
ћедицина
ћеханика
ќхрана труда
ѕедагогика
ѕолитика
ѕраво
ѕсихологи€
–елиги€
–иторика
—оциологи€
—порт
—троительство
“ехнологи€
“ранспорт
‘изика
‘илософи€
‘инансы
’ими€
Ёкологи€
Ёкономика
Ёлектроника

 

 

 

 


–абота со списками. —писки €вл€ютс€ одной из основных структур данных ѕролога




—писки €вл€ютс€ одной из основных структур данных ѕролога. —писок €вл€етс€ в некотором смысле аналогом массива в алгоритмических €зыках программировани€. ќднако здесь есть существенные отличи€. ќсновным механизмом работы со списками €вл€етс€ рекурси€, позвол€юща€ компактно описывать алгоритмы. ƒл€ рекурсии не требуетс€ знани€ точного числа элементов списка, достаточно определени€, как правило, головного элемента списка и услови€ окончани€ работы рекурсии. ѕоэтому элементы списков не индексируютс€, соответственно, количество элементов списка не фиксируетс€.

ћожно также провести аналогию списков ѕролога и динамических однонаправленных списковых структур €зыка ѕаскаль. ќт последних их выгодно отличает отсутствие необходимости работать с адресной частью списков.

ƒл€ удобства обработки списков в ѕрологе введены два пон€ти€: голова и хвост. ѕервый элемент списка (или несколько первых элементов) €вл€ютс€ головой списка, а оставшиес€ Ц его хвостом. “огда список Ц это структура данных, определ€ема€ следующим образом:

Ц список €вл€етс€ либо пустым,

Ц либо состо€щим из головы и хвоста; головой списка может быть элемент любого типа, а хвост должен быть, в свою очередь, списком.

ƒл€ обозначени€ списка используютс€ квадратные скобки, а дл€ отделени€ головы списка от его хвоста Ц символ "|". Ќапример, дл€ списка [1|2,3] элемент 1 €вл€етс€ головой, а список [2, 3] хвостом. ѕустой список обозначаетс€ [ ]. ≈сли список не раздел€етс€ на голову и хвост, квадратные скобки можно опустить.

–ассмотрим некоторые предикаты дл€ обработки списков.

11. ƒобавление элемента в список. Ётот предикат должен иметь три аргумента: добавл€емый элемент, список и результирующий список. Ќаиболее простой способ добавить элемент в список Ц это вставить его в самое начало так, чтобы он стал новой головой. ≈сли X Ц это новый элемент, который добавл€ют в список L, то предикат добавлени€ элемента в список можно записать таким образом:

add(X,L, [X|L]).

12. ”даление элемента. ”даление элемента X из списка L можно определить в виде отношени€

away(X,L,L1),

где L1 Ц это список L, из которого удален элемент X.

ќтношение away можно определить следующим рекурсивным образом: если X €вл€етс€ головой списка, тогда результатом удалени€ будет хвост этого списка. ≈сли X находитс€ в хвосте списка, тогда его нужно оттуда удалить:

away(X, [X|T],T).

away(X, [Y|T], [Y|T1]):Ц away(X,T,T1).

13. ѕроверка принадлежности элемента списку. “ребуетс€ определить предикат:

member(X,L).

«десь L Ц некоторый список, ’ Ц объект того же типа, что и элементы списка L. —оставление предиката может быть основано на следующих соображени€х: X есть либо голова списка L, либо X принадлежит хвосту. Ёто может быть записано в виде двух предложений, первое из которых есть простой факт, ограничивающий вычислени€, а второй Ц рекурсивное правило:

member(X, [X| _ ]).

member(X, [ _ | T ]):Ц member(X,T).

Ќапомним, что знаком подчерка здесь обозначена анонимна€ переменна€, значение которой в данном предложении неважно.

≈сли окажетс€ пустой список, тогда предикат завершаетс€ ложно, так как дл€ пустого списка нет своего правила.

14. —цепление (конкатенаци€) списков.

conc(L1,L2,L3).

ќбъедин€емые списки задаютс€ первыми двум€ аргументами L1 и L2. —писок L3 представл€ет собой конкатенацию этих списков.

ƒл€ определени€ отношени€ конкатенаци€ отделим два случа€:

(1) ≈сли первый список пуст, то второй и третий представл€ют собой один и тот же список:

ñonc([ ],L,L).

(2) ≈сли первый аргумент не пуст, то он имеет голову и хвост, т.е. [X|L1]. ≈го сцепление со списком L2 Ц список [X|L3], где список L3 получен после сцеплени€ списков L1 и L2, т.е.

conc([X|L1],L2,[X|L3]):Цconc(L1,L2,L3).

15. ”даление из списка повтор€ющихс€ элементов. јргументами предиката unik €вл€ютс€ два списка: исходный и результирующий. —мысл алгоритма прост: если элемент присутствует в списке (провер€етс€ предикатом member), то он не записываетс€ в результирующий список, иначе добавл€етс€ в качестве головного элемента.

unik([ ],[ ]).

unik([H|T], L):Ц member(H,T), unik(T,L).

unik([H|T], [H|L]):Ц unik(T,L).

16. ќбращение списка. ќпределим предикат

reverse(L1,L2).

јргументы L1 и L2 Ц два списка, из которых список L2 содержит элементы списка L1, записанные в обратном пор€дке.

reverse(L1,L2):Цreverse1(L1,[],L2).

reverse1([],L,L).

reverse1([H|T],L1,L2):Цreverse1(T,[H|L1],L2).

ѕредикат reverse в данном случае €вл€етс€ интерфейсным, он запускает в работу основной рабочий предикат reverse1, имеющий дополнительный второй аргумент Ц список, который вначале пуст, и используетс€ собственно дл€ обращени€ списка. Ќа каждом шаге рекурсии один элемент исходного списка становитс€ головой промежуточного списка. “ретий аргумент передаетс€ от шага к шагу и конкретизируетс€ в момент достижени€ базового состо€ни€ предиката reverse1.  огда первый список исчерпан, второй уже содержит элементы, записанные в обратном пор€дке. ќтметим, что наличие третьего аргумента, фиксирующего результат, об€зательно, т.к. после обратного прохождени€ рекурсии все конкретизированные переменные принимают свои первоначальные значени€.

17. ¬ычисление суммы элементов списка. ћожно выполнить предикатом

sum(L,S).

«десь S Ц сумма элементов списка L. «апрограммировать этот предикат можно двум€ способами. –ассмотрим сначала более очевидный:

sum([ ],0).

sum([H|T], S1):Ц

sum(T,S2),S1=S2+H.

ƒекларативный смысл этого алгоритма: если список пуст, то сумма его элементов равна нулю, иначе список можно разделить на голову H и хвост T; сумма элементов такого списка S1, при этом сумма элементов хвоста T есть S2 и S1=S2+H. ќбратим внимание, что это рекурси€ нехвостова€: в рекурсивном правиле предиката sum рекурсивное условие записано не последним. Ќехвостова€ рекурси€ при последовательных вызовах генерирует промежуточные переменные, которые конкретизируютс€ при обратном прохождении рекурсии.

–ассмотрим работу этого предиката на примере. ѕусть требуетс€ найти сумму элементов списка [3,6,1]. ѕоследовательность вызовов следующа€:

sum([3|6,1],S) âûçûâàåò sum([6,1],S1) è S=S1

sum([6|1],S1) âûçûâàåò sum([1],S11) è S1=S11+6.

sum([1],S11) âûçûâàåò sum([],S111) è S11=S111+1.

sum([ ],S111) удовлетвор€етс€, если S111 конкретизируетс€ 0.

sum([1],S11) удовлетвор€етс€, если S11 конкретизируетс€ 1.

sum([6,1],S1) удовлетвор€етс€, если S1 конкретизируетс€ 7.

sum([3,6,1],S) удовлетвор€етс€, если S конкретизируетс€ 10.

ƒругой алгоритм вычислени€ суммы не так нагл€ден, но он позвол€ет отменить нехвостовую рекурсию.

sum(L,S):Цsum1(L,0,S).

sum1([ ],S,S). % базовое правило, список пуст, сумма накоплена

sum1([H|T],S1,S):Ц

S2=S1+H,

sum1(T,S2,S).

«десь используем тот же прием, что и в предикате обращени€ списка: используем более общий предикат sum1, имеющий дополнительный аргумент S, в котором зафиксируетс€ результат. ƒекларативный смысл базового правила: если список исчерпан, то сумма накоплена, при этом конкретизируетс€ третий аргумент.

“от же пример:

sum1([3|6,1], 0, S) âûçûâàåò sum1([6,1], 3, S).

sum1([6|1], 3, S) âûçûâàåò sum1([1], 9, S).

sum1([1],9, S) âûçûâàåò sum1([], 10, S).

sum([ ], 10, S) удовлетвор€етс€, если S конкретизируетс€ 10.

ѕоследовательность возвратов следующа€:

sum1([1], 9,1 0)

sum1([6,1], 3,1 0)

sum1([3,6,1], 0, 10)

18. Ќахождение максимального элемента списка «десь нам понадобитс€ вспомогательный предикат max, выбирающий максимальное значение из двух элементов:

max(X,Y,X):Ц X>=Y.

max(X,Y,Y):Ц X<Y.

–езультативный предикат maxlist(LIST,MAX), где MAX Ц наибольший элемент списка LIST, выгл€дит следующим образом:

maxlist([X],X).

maxlist([X,Y|TAIL],MAX):Ц

maxlist([Y|TAIL],MAXTAIL),

max(X,MAXTAIL,MAX).

—мысл базового правила: максимальный элемент одноэлементного списка равен самому этому элементу. »наче, если в списке есть хот€ бы два элемента X и Y, выбираетс€ максимальный элемент хвоста MAXTAIL и при этом MAX равен наибольшему из X и MAXTAIL. –екурси€ здесь нехвостова€, чтобы обеспечить конкретизацию переменных X и MAXTAIL.





ѕоделитьс€ с друзь€ми:


ƒата добавлени€: 2015-10-01; ћы поможем в написании ваших работ!; просмотров: 575 | Ќарушение авторских прав


ѕоиск на сайте:

Ћучшие изречени€:

¬елико ли, мало ли дело, его надо делать. © Ќеизвестно
==> читать все изречени€...

1556 - | 1238 -


© 2015-2024 lektsii.org -  онтакты - ѕоследнее добавление

√ен: 0.02 с.