Материал: Терёхин В. В. Turbo Prolog

Если правило find_it(Head,[Head|_]) неуспешно, то происходит откат, и делается попытка со вторым вариантом find_it.

На этом втором вхождении предиката find_it Турбо-Пролог унифицирует имеющиеся термы с заголовком правила find_it([Head,[_,Rest]). Заметим, что при этом первый элемент списка ставится в соответствие анонимной переменной. Так делается вследствие того, что значение первого элемента не представляет для нас интереса; данное правило не было бы задействовано, если бы этот элемент совпадал с объектом поиска при попытке с find_it(Head,[Head,_]). Теперь мы хотим присвоить переменной хвост списка (не голову !), чтобы Турбо-Пролог попытался установить соответствие между объектом поиска и головой списка хвоста. Попытка удовлетворить рекурсивное правило find_it(Head,Rest) заставляет Турбо-Пролог представить хвост текущего как новый самостоятельный список. Опять присвоенный переменной Rest список разделяется на голову и хвост при посредстве утверждения find_it(Head, [Head|_]). Процесс повторяется до тех пор, пока это утверждение дает либо успех в случае установления соответствия на очередной рекурсии, либо неуспех в случае исчерпания списка.

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

____________________________________________________________

Листинг 5.3

/* Программа: Элементы Файл: PROG0503.PRO */ /* Назначение: Поиск нужного элемента в списке. */

domains

number_list = number * number = integer

member_list = member * member = symbol

predicates

find_it(number, number_list) find_it(member, member_list)

clauses

find_it(Head, [Head|_]). find_it(Head, [_|Tail]) :-

find_it(Head, Tail).

/***** конец программы *****/

____________________________________________________________

Если задать цель find_it(3,[1,2,3,4,5])

то первый вариант правила пытается установить соответствие между головой списка, 1, и объектом поиска, 3. Вследствие неравенства 1 и 3 результа-

106

том применения этого правила является неуспех. Процесс установления соответствия продолжается со следующей головой списка (уже усеченного), 2, и снова неуспешно. При следующей попытке голова списка, а вместе с ней и объект поиска, равны 3 - успешное завершение процесса. На экране появляется True, что как раз указывает на успешное завершение процесса установления соответствия, то есть на присутствие числа 3 в списке.

Цель

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

дает неуспех, так как элемент 1 в списке отсутствует. Цель find_it("Alice",["Diana","Peter","Paul","Mary","Alice"]).

дает успех, так как список содержит элемент Alice. Цель find_it("Toledo",["Cleveland","Dayton","Chardon",

"Youngstown","Cincinnati"]).

очевидно, также неуспешна.

*Упражнение

5.11.Нарисуйте диаграмму поиска для следующей внешней цели: find_it(44,[11,22,33,44,11,22,33,44,11,22,33,44,55]).

В скольких случаях будет достигнут успех ?

5.5.2 Деление списков

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

Для пояснения сказанного рассмотрим предикат split, аргументами которого являются элемент данных и три списка:

split(Middle,L,L1,L2).

Элемент Мiddle здесь является компаратором, L - это исходный список, а L1 и L2 - подсписки, получающиеся в результате деления списка L. Если элемент исходного списка меньше или равен Middle, то он помещается в список L1; если больше, то в список L2.

Предположим, что вначале значением переменной Мiddle является число 40, переменной L присвоен список [30,50,20, 25,65,95], а переменные L1 и L2 не инициализированы.

split(40,[30,50,20,25,65,95],L1,L2).

Правило для разделения списка должно быть написано таким образом, чтобы элементы исходного списка, меньшие либо равные 40, помещались в список L1, а большие 40 - в список L2.

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

107

В результате применения правила к списку [30,50,20,25, 65,95] значениями списков L1 и L2 станут соответственно [30, 20,25] и [50,65,95].

Само правило для разделения списка записывается в Турбо-Прологе следующим образом:

split(Middle,[Head|Tail],[Head|L1],L2) :-

Head <= Middle, split(Middle,Tail,L1,L2).

split(Middle,[Head|Tail],L1,[Head|L2]) :- split(Middle,Tail,L1,L2), Head > Middle.

split(_,[],[],[]).

Отметим, что метод деления списка на голову и хвост используется в данном правиле как для разделения исходного списка, так и для формирования выходных списков.

Приведенное правило годится для любых допустимых в Турбо-Прологе типов данных. Если список состоит из целых чисел, то тогда нужно элементы списка и компаратор описать как целые. Если же Вы имеете дело со списком символических имен, то элементы списка и компаратор должны относиться к типу symbol.

Программа "Деление списка" (листинг 5.4) включает в себя только что приведенное правило. Попробуйте ввести такое целевое утверждение:

split(40,[30,50,20,25,65,95],L1,L2).

____________________________________________________________

clauses

split(Middle,[Head|Tail],[Head|L1],L2) :- Head <= Middle, split(Middle,Tail,L1,L2).

split(Middle,[Head|Tail],L1,[Head|L2]) :- split(Middle,Tail,L1,L2), Head > Middle.

split(_,[],[],[]).

/***** конец программы *****/

_____________________________________________________________

108

*Упражнение

5.12.Для программы "Деление списка" а) задайте внешнюю цель

split(12,[96,32,8,16,55,12],L1,L2).

Как будут выглядеть списки L1 и L2 ?

б) нарисуйте диаграмму изменения значений списков в процессе работы программы.

5.5.3 Присоединение списка

Слияние двух списков и получение таким образом третьего принадлежит к числу наиболее полезных при работе со списками операций. Этот процесс обычно называют присоединением одного списка к другому. Метод, представленный в данном разделе, особенно часто используется в таких приложениях, каковыми являются системы управления базами данных и разработка интерфейсов пользователя. В сущности, Вы, вероятно, найдете его необходимым для большинства программ Турбо-Пролога, требующих преобразования списков.

В качестве примера рассмотрим две переменные, L1 и L2, представляющие списки. Переменные имеют значения [1,2,3] и [4,5]. Назовем их входными списками. Предикат, присоединяющий L2 к L1 и создающий выходной список L3, в который он должен переслать все элементы L1 и L2. Весь процесс можно представить себе в виде такой совокупности действий:

1.Список L3 вначале пуст.

2.Элементы списка L1 пересылаются в L3, теперь значением

L3 будет [1,2,3].

3.Элементы списка L2 пересылаются в L3, в результате чего тот принимает значение [1,2,3,4,5].

Структура правила для выполнения этих действий достаточна проста: append([],L,L).

append([N|L1],L2,[N|L3]) :- append(L1,L2,L3).

Поясним теперь, как будет функционировать это правило, если на вход подать списки L1=[1,2,3] и L2=[4,5].

Сначала Турбо-Пролог пытается удовлетворить первый вариант пра-

вила:

append([],L,L).

Для того чтобы удовлетворить это правило, первый объект предиката append нужно сделать пустым списком. Вначале же предикат append имеет форму

append([1,2,3],[4,5],_).

Отметим, что третий, выходной список в этой форме пока еще не определен. Внутренний процесс унификации Турбо-Пролога, пытаясь удовлетворить второе правило append, раскручивает цепочку рекурсий до тех пор, пока не обнуляет первый список. Элементы списка при этом последовательно

109

пересылаются в стек. Стек, логическая структура данных в памяти компьютера, обеспечивает временное хранение этих элементов.

Когда первый объект предиката append окажется пустым списком, становится возможным применение первого варианта правила. Третий список при этом инициализируется вторым. Такой процесс можно пояснить при помощи двух состояний append, до и после применения первого варианта правила:

append([],[4,5],_). append([],[4,5],[4,5]).

В данный момент процедуры унификации Турбо-Пролога полностью удовлетворили это правило, и Турбо-Пролог начинает сворачивать рекурсивные вызовы второго правила:

append([N|L1], L2, [N|L3]) :-

append(L1,L2,L3).

Извлекаемые при этом из стека элементы помещаются один за другим в качестве головы к первому и третьему спискам. Следует особо отметить, что элементы извлекаются в обратном порядке (это стек !), и что значение извлеченного из стека элемента присваивается переменной N одновремен-

но в [N|L1] и [N|L3].

Шаги данного процесса можно представить так: append([],[4,5],[4,5]) append([3],[4,5],[3,4,5]) append([2,3],[4,5],[2,3,4,5]) append([1,2,3],[4,5],[1,2,3,4,5])

Присвоение элементов стека происходит рекурсивно до тех пор, пока стек не будет исчерпан. В результате список L3 будет содержать элементы обоих входных списков - [1,2,3,4,5].

Программа "Присоединение списка" (листинг 5.5) демонстрирует применение данного метода. В этой программе n_list является доменом списков целых чисел. Описание предиката для присоединения одного списка к другому записано в виде

append(n_list,n_list,n_list)

Раздел clauses содержит уже приведенные описания правил append. Внешней целью для программы может служить, скажем, ранее разобранный пример:

append([1,2,3],[4,5],L).

_____________________________________________________________

110