Конкатенация

Для конкатенации списков определим следующее отношение:

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]) :-СОПС С Ll_f 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(LV₁[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.