Конкатенация
Для конкатенации списков определим следующее отношение:
conc( LI, L2, L3)
где L1 и L2 — два списка, a L3 — их конкатенация. Например:
cone ( la,b], tc,d], [a,b,c,d]}
является истинным, но
conc( (a,b), [c,d], [a,b,a,c,d]>
является ложным. При определении отношения cone снова необходимо рассмотреть
два описанных ниже случая, в зависимости от первого параметра, L1.
1. Если первый параметр является пустым списком, то второй и третий парамет
ры должны представлять собой одинаковые списки (назовем их L); это выра
жается следующим фактом Prolog:
cone([ ], L, L) .
2. Если первый параметр cone — непустой список, то он имеет голову и хвост и
должен выглядеть примерно так:
[XI L1]
На рис. 3.2 иллюстрируется операция конкатенации списка [X | L1] и некоторого списка L2. Результатом конкатенации становится список [X I L3], где L3 — конкатенация L1 и L2. В языке Prolog этот результат можно записать следующим образом:
сопс[ fX | LI}, L2, [X [ L3]) :-СОПС С Llf L2, L3) .
Теперь эта программа может использоваться для конкатенации заданных списков, например:
?- conct [a,b,c], [1,2,3], h) . L = [a,b,с,1,2,3]
?- conc([a,[b,c],d] , [a,[],b] , L). L = [a, [b,c],d, a, [),b]
Глава З. Списки, операции,арифметические выражения
[X]L1]
Li
L2
L3
L3
[X | L3] Рис. 3.2. Конкатенация списков
Хотя программа cone выглядит довольно простой, она допускает разностороннее использование с помощью многих других способов. Например, cone можно заставить работать в обратном направлении, для декомпозиции заданного списка на два отдельных списка, как показано ниже.
?- conc( LI, L2, (а,Ь,с] ) . L1 = []
| L2 L1 L2 1-L2 L1 L2 ПС |
[a,b,c);
[a]
[Ь,с];
[a,b]
[c];
[a,b,c]
= Не-
Возможны четыре варианта декомпозиции списка [а, Ь, с], и все они были найдены программой с one с помощью перебора с возвратами.
Кроме того, эту программу можно использовать для поиска определенного элемента в списке. Например, с ее помощью можно найти все месяцы, которые предшествуют, и месяцы, которые следуют за указанным месяцем, как показывает приведенная ниже цель. ?- conc( Before, [may | After],
[ jan, feb,mar,apr, may, jun, jul, aug, sep, oct, nov, dec] ) . Before = [ jan, feb, mar, apr] After— [jun.jul, aug, sep, oct, nov,dec] .
Кроме того, можно найти месяцы, которые непосредственно предшествуют н непосредственного следуют, допустим, за маем месяцем, введя следующий вопрос:
7- cone! , [Monthl,may,Month2 ! ),
[лап, fsb,mar, apr, may, jun, jul, aug, sep, oct, nov, dec] } . Monthl = apr Month2 - jun
Более того, с ее помощью можно, например, удалить из некоторого списка L1 все, что следует за тремя последовательными вхождениями элементов z в списке L1, наряду с этими тремя г, например:
?- LI - [a,b,z, г, с, г, z, г,о\е),
conct L2, [z,z,z| _] , L1) .
L1 - [а,Ь, z, z, с, г, z, z, б, e]
L2 = [а,Ь,2, z,c]
Выше уже было запрограммировано отношение для проверки принадлежности к списку. Но такое же отношение можно более изящно запрограммировать с помощью программы сспс, введя следующее предложение:
member 1 ( X, L) :-
conc( L1, [X | L2], L) .
Часть I. Язык Prolog
Это предложение фактически говорит о следующем: X входит в состав списка L, если L можно разложить на два списка таким образом, что X является головой второго из них. Безусловно, member! определяет такое же отношение, что и member. Другое имя этому отношению было присвоено лишь для того, чтобы можно было отличить друг от друга эти две реализации. Обратите внимание на то, что приведенное выше предложение можно записать с использованием анонимных переменных следующим образом:
тезпЬег! [ X, Ь) :-
соде [_, [X | _} , L! .
Любопытно сравнить между собой обе реализации отношения проверки принадлежности, тяпЬег и member 1. Первая из них имеет довольно простое процедурное значение, которое состоит в следующем: Для проверки тпг'с, входит ли некоторый элемент X в состав некоторого списка L:
1) вначале следует проверить, не равна ли элементу X голова списка L, а затем
2) проверить, не входит пи элемент X в состав хвоста списка L.
С другой стороны, декларативное прочтение отношения memberl является простым, но его процедурное значение не столь очевидно. Один из любопытных экспериментов состоит в том, чтобы определить, как фактически отношение memberl применяется при вычислении ответа на некоторый вопрос. Определенное представление об этом можно получить на примере трассировки выполнения; рассмотрим следующий вопрос: •?- теггЪег1( Ъ, [а,Ь,с]).
Соответствующая трассировка приведена на рис. 3.3, На основании этой Трассировки можно сделать вывод, что отношение memberl действует аналогично отношению member. Оно сканирует список элемент за элементом до тех пор, пока не будет найден искомый элемент или исчерпан список.
memberl (Ь, 1«,Ъ,с])
-------------- 7Z---------------
conc(L1, [b[LZ],[а.Ь.с])
1 -е предложение cone
Ссклаооаание:
и = и
[b|L2] = [«,b,c]неудача, поскольку b* а
2-е предложение с one
Согласование: L1=[XiL1'] [b|L2]=L2' [■,b,c] = [X[L3]Это вызывает: X=a,L3=[b,c]
conc(LV1[b|L2][[b,c])
1-е предложение cone
Согласование:
L1=[J
[b|L2] = [b,c]
Это вызывает:
L2= [c]
yes
Рис. 3.3, Пример того, что процедура memberl находит элемент а банном списке путем последовательного поиска в этом списке
Глава 3.СПИСКИ, операции, арифметические выражения
Упражнения
3.1. С помощью программы cone выполните приведенные ниже задания.
а) Составьте цель для удаления последних трех элементов из списка L и соз
дания другого списка, L1. Подсказка: I представляет собой конкатенацию
L1 и трехэлементного списка.
б) Составьте цель для удаления первых трех и последних трех элементов из
списка L и создания списка L2.
3.2. Определите отношение
last[ Item, List)
таким образом, чтобы Item был последним элементом списка List. Разработайте две версии: а) с использованием отношения cone; б) без использования отношения cone.