Рекурсивная обработка списков в Prolog

Цель работы: Приобрести практические навыки организации списков на Prolog. Научиться реализовывать рекурсивную обработку списков.

Задание

1) Записать на языке Prolog программу для отношений, выполняющих рекурсивную обработку списков. Предусмотреть возможность обработки списков различных типов. Для запросов использовать внешние цели.

2) Привести варианты запросов для данных всех типов, допустимых в программе. Для одного из простых запросов построить дерево вывода.

3) Оценить сложность полученной логической Prolog-программы в зависимости от параметров исходных данных (длин обрабатываемых списков): найти размер цели в доказательстве запроса, использованного для построения дерева вывода, а также количество вершин дерева вывода.

Вариант 9

Отношение ПОДСТАНОВКА, в котором новый список L2 получается из исходного

списка L1 путем подстановки Y вместо всех вхождений X. Например,

?- ПОДСТАНОВКА( а, х, [b, а, с], [ b, х, с]) → истинно, а

?- ПОДСТАНОВКА(а, х, [b,а,с, а], [b,а,c,х]) → нет.