10. Слияние списков

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

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

conc([ ], L, L).

conc([H|T], L, [H|T1]) :– conc(T, L, T1).

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

Во-первых, для соединения списков.

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

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

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

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

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

В-шестых, можно определить, используя 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 */

.

.