Соединить два списка в один. Первые два аргумента предиката будут представлять соединяемые списки, а третий — результат соединения.

В качестве основы для решения этой задачи возьмем рекурсию по первому списку. Базисом рекурсии будет факт, устанавливающий, что если присоединить к списку пустой список, в результате получим исходный список. Шаг рекурсии позволит создать правило, определяющее, что для того, чтобы приписать элементы списка, состоящего из головы и хвоста, ко второму списку, нужно соединить хвост и второй список, а затем к результату приписать спереди первый элемент первого списка. Запишем решение:

conc([ ], L, L). /* при присоединении пустого списка к списку L получим список L */conc([H|T], L, [H|T1]) :–conc(T,L,T1). /* соединяем хвост и список L, получаем хвост результата */

Заметим, что этот предикат также можно применять для решения нескольких задач.

Во-первых, для соединения списков. Например, если задать вопрос

conc([1, 2, 3], [4, 5], X)

то получим в результате

X= [1, 2, 3, 4, 5]

Во-вторых, для того, чтобы проверить, получится ли при объединении двух списков третий. Например, на вопрос:

conc([1, 2, 3], [4, 5], [1, 2, 5]).

ответом будет, конечно, No.

В-третьих, можно использовать этот предикат для разбиения списка на подсписки. Например, если задать следующий вопрос:

conc([1, 2], Y, [1, 2, 3]).

то ответом будет Y=[3].

Аналогично, на вопрос

conc(X, [3], [1, 2, 3]).

получим ответ X=[1, 2].

И, наконец, можно спросить

conc(X, Y, [1, 2, 3]).

Получим четыре решения:

X=[], Y=[1, 2, 3]X=[1], Y=[2, 3]X=[1, 2], Y=[3]X=[1, 2, 3], Y=[]

В-четвертых, можно использовать этот предикат для поиска элементов, находящихся левее и правее заданного элемента. Например, если нас интересует, какие элементы находятся левее и, соответственно, правее числа 2, можно задать следующий вопрос:

conc(L, [2|R], [1, 2, 3, 2, 4]).

Получим два решения:

L=[1], R=[3, 2, 4].L=[1, 2, 3], R=[4]

В-пятых, на основе нашего предиката conc можно создать предикат, находящий последний элемент списка:

last(L,X):– conc(_,[X],L).

Справедливости ради стоит заметить, что этот предикат можно реализовать и "напрямую", без использования предиката conc:

last2([X],X). /* последний элемент одноэлементного списка — этот элемент */last2([_|L],X):– last2(L,X). /* последний элемент списка совпадает с последним элементом хвоста */

В-шестых, можно определить, используя conc, предикат, позволяющий проверить принадлежность элемента списку. При этом воспользуемся тем, что если элемент принадлежит списку, то список может быть разбит на два подсписка так, что искомый элемент является головой второго подсписка:

member4(X,L):– conc(_,[X|_],L).

В-седьмых, используя предикат, позволяющий объединить списки, можно создать предикат, проверяющий по двум значениям и списку, являются ли эти значениясоседними элементами списка. Предикат будет иметь три параметра: первые два — значения, третий — список.

Идея решения заключается в следующем. Если два элемента оказались соседними в списке, значит, этот список можно разложить на два подсписка, причем голова второго подсписка содержит два наших элемента в нужном порядке. Выглядеть это будет следующим образом:

neighbors(X,Y,L):– conc(_,[X,Y|_],L). /* список L получается путем объединения некоторого списка со списком, голову которого составляют элементы X и Y */

Обратите внимание, что этот предикат проверяет только наличие нужных значений в указанном порядке. Если нам неважен порядок, в котором два данныхзначения встречаются в некотором списке, то следует записать модификацию описанного выше предиката, которая будет проверять оба варианта размещения искомых элементов. Для этого достаточно, чтобы список раскладывался на два подсписка, причем голова второго подсписка содержала два наших элемента либо в прямом, либо в обратном порядке. Соответствующий программный код будет следующим:

neighbors2(X,Y,L):– conc(_,[X,Y|_],L); conc(_,[Y,X|_],L). /* список L получается путем объединения некоторого списка со списком, голову которого составляют элементы X и Y или элементы Y и X */

Позволяющий "обратить" список (записать его элементы в обратном порядке). Предикат будет иметь два аргумента: первый — исходный список, второй — список, получающийся в результате записи элементов первого аргумента в обратном порядке.

Для решения этой задачи воспользуемся рекурсией. Базис: если записать элементы пустого списка (которых нет) в обратном порядке — опять получим пустой список. Шаг рекурсии: для того чтобы получить "перевернутый" список, можно "перевернуть" его хвост и "приклеить" к нему первый элемент исходного списка. Запишем эти размышления.

reverse([ ],[ ]). /* обращение пустого списка дает пустой список*/reverse([X|T],Z):– reverse(T,S), conc(S,[X],Z). /* обращаем хвост и приписываем к нему справа первый элемент исходного списка*/

Обратите внимание, что вторым аргументом в предикате conc должен стоять именно одноэлементный список [X], а не элемент X. Это связано с тем, что аргументами предиката conc должны быть списки.

Можно написать данный предикат без использования предиката conc. Правда, тогда нам придется добавить дополнительный аргумент, в котором мы будем "накапливать" результат. Мы будем "отщипывать" от исходного списка по элементу и дописывать его к вспомогательному списку. Когда исходный список будет исчерпан, мы передадим "накопленный" список в третий аргумент в качестве ответа. До этого момента третий аргумент передается от шага к шагу неконкретизированным. Реализация будет выглядеть следующим образом:

rev([H|T],L1,L2):– rev(T,[H|L1],L2). /* голову первого аргумента дописываем ко второму аргументу*/rev([ ],L,L). /* если исходный список закончился, то второй аргумент — передаем в третий аргумент в качестве результата*/

Для того чтобы использовать этот предикат обычным "двухаргументным" образом, добавим еще один предикат, который будет запускать наш "основной" предикатrev, имеющий "лишний" аргумент, используемый для накопления элементов обращенного списка. В начале работы второй аргумент должен быть пустым списком.

reverse2(L1,L2):– rev (L1,[ ],L2).

Наши рекомендации