7.4. Справочник комплектующих деталей

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

Организация базы данных справочника сходна с тем, что описано в гл. 3. Сборочный узел представлен в виде списка структур вида чис(X, Y), где X– это имя некоторой детали (простой детали или узла), a Y– необходимое количество таких деталей. Ниже перечислены все предикаты измененной программы с указанием их назначения:

Деталиузла(А):выдает на печать список всех простых деталей, требующихся для сборки узла А, и количество каждой детали.

Деталиузлов(N,X,P): P- это список структур чис(Дет, Кол),где Дет- это название детали, а Кол- это количество таких деталей, требующихся для сборки каждого из экземпляров узлов X. N- целое, а X– атом, представляющий название некоторой детали.

Деталировка(N,S,Р): Р- это, как и выше, список структур чис,требующихся для сборки всех узлов, представленных элементами списка S; Nзадает число экземпляров списка S, N– целое; S– список структур чис.

Собрать(Р, А): Ри А– списки структур чис. А– это список, составленный из тех же элементов, что и Р, но без повторений одной и той же детали. Причем количество каждой детали, указанное в списке А, совпадает с суммой всех повторений этой детали в списке Р. Предикат собратьмы используем для того, чтобы собрать несколько описей наборов одинаковых деталей в одну опись. Например, 3 винта, 4 шайбы и 4 винтасобираются вместе, давая 7 винтов и 4 шайбы.

Дособрать(Х,М, L,O,N): Lи О- это списки структур, чис,О – это список всех элементов списка L, в состав которых не входит деталь X; X – это атом, задающий название некоторой детали; N– это общее количество Xв списке L, сложенное с М; М– это целое число, которое используется для суммирования количеств Xв Lи передается как аргумент в каждом вызове дособрать.При выходе из рекурсии, который обеспечивается выполнением граничного условия, Мвозвращается как N.

Вывдеталейузла(Р): Р– это список структур чис,который выдается на печать по одной структуре на строке вывода. Цель put(9)выводит литеру с кодом ASCII=9, что соответствует горизонтальной табуляции. С предикатом присоединитьмы уже неоднократно встречались ранее.

Полностью Пролог-программа выглядит так:

деталиузла(Т):-деталиузлов(1,Т,Р), co6paть(P,Q), вывдеталейузла(Q).

деталиузлов(N,Х,Р):-узел(Х,S), деталировка(N,S,Р).

деталиузлов(N,Х, [чис(Х,N)]):- деталь(Х).

деталировка(_, [], []).

деталировка(N, [чис(Х, Число) |L],T):-М is N * Число, деталиузлов(М,Х,Хдетали),деталировка (N, L,Остдетали,Т),присоединить(Хдетали,Остдетали,Т).

собрать([],[]).

coбpaть([чис(X,N)|R],[чис(X,Nитог)|R2]):-дособрать(Х,N,R,O,Nитог),собрать(О,R2).

досo6paть(_,N,[],[],N).

дособрать(Х,N,[чис(Х,Число)|Oст],Прочие,Nитог):-!,М is N+Число, дособрать(Х,М,Ост,Прочие,Nитог).

дособрать(Х,N,[Друг|Ост],[Друг|Прочие],Nитог):-дособрать(Х, N, Ост, Прочие, Nитог).

вывдеталейузла([]).

вывдеталейузла([чис(Х,N)|R):-tab(4),write(N),put(9),write(X),nl, вывдеталейузла(R).

7.5. Обработка списков

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

Нахождение последнего элемента списка:Цель последний(X, L)согласуется с базой данных, если элемент Xявляется последним элементом списка L. Граничное условие выполняется, когда список Lсодержит только один элемент. Это условие проверяется первым правилом. Второе правило задает общий рекурсивный случай:

последний(Х,[Х]).

последний(Х,[_,|Y]):- последний(Х,Y).

?- последний(Х,[talk,of,the,town]).

X = town

Проверка порядка следования элементов:Цель следомза(Х, Y, L)согласуется с базой данных, если элементы Xи Yявляются последовательными элементами списка L. Особенности работы переменных допускают, чтобы или X, или Y, или обе переменные были неконкретизированы перед попыткой согласовать цель. В первом утверждении, которое проверяет граничное условие, должно быть также предусмотрено, что после Xи Yв списке могут быть другие элементы. Этим объясняется появление анонимной переменной, в которой сохраняется хвост списка:

следомза(Х,Y,[Х,Y|_]).

следомза(Х,Y,[_|Z]):- следомза(Х,Y,Z).

Объединение списков:С приводимым примером мы уже встречались ранее в разд. 3.6. Цель присоединить(X, Y, Z)согласуется с базой данных в том случае, если Z– это список, построенный путем добавления Yв конец X. Например,

?- присоединить([a,b,с],[d,e,f],Q).

Q=[a,b,c,d,e,f]

Определение предиката присоединитьвыглядит следующим образом:

присоединить([],L,L).

присоединить([Х|L1],L2,[Х|LЗ]):- присоединить(L1,L2,LЗ).

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

Заметим, что любые два аргумента присоединитьмогут быть конкретизированы, и в этом случае присоединитьконкретизирует третий аргумент соответствующим результатом. Этим свойством, которое можно было бы назвать «недетерминированным программированием», обладают многие из определяемых в данной главе предикатов. Указанная гибкость присоединитьпозволяет определить с его помощью ряд других предикатов, что мы и сделаем:

последний(Е1,Список):- присоединить(_,[Е1],Список).

следомза(Е11,Е12,Список):-

присоединить(_,[Е11,Е12|_], Список).

принадлежит(Е1,Список):- присоединить(_,[Е1|_],Список).

Обращение списка:Цель обр(L,M)согласуется с базой данных, если результат перестановки в обратном порядке элементов списка Lесть список М. В программе используется стандартный прием, когда обращенный список получается присоединением его головы к обращенному хвосту. Лучший способ обратить хвост – это использовать сам обр.Граничное условие выполняется тогда, когда первый аргумент сократился до пустого списка, в этом случае результатом также является пустой список:

обр([],[]).

обр([Н|Т],L):- обр(T,Z), присоединить(Z,[Н],L).

Заметим, что на месте второго аргумента присоединитьстоит Нв квадратных скобках. Причина в том, что Н– это голова первого аргумента, а голова списка сама не обязана быть списком. Хвост же списка по определению всегда является списком. Для более эффективной реализации обрмы можем встроить действия по объединению списков непосредственно в утверждения для обр:

o6p2(L1,L2):- обрдоп(L1,[],L2).

обрдоп([X|L],L2 _fL3):- обрдоп(L,[Х|L2],LЗ).

обрдоп([],L,L).

Второй аргумент обрдописпользуется для хранения «текущего результата». Каждый раз, когда выявляется новый фрагмент результата (X), передаваемый в остальную часть программы, «текущий результат» представляет из себя старый «текущий результат», дополненный новым фрагментом X. В самом конце последний «текущий результат» возвращается в качестве результата исходного целевого утверждения. Аналогичный прием используется в разд. 7.8 при определении предиката имя_целого.

Исключение одного элемента:Цель исключ1(Х, Y,Z)исключает первое вхождение элемента Xиз списка Y, формируя новый сокращенный список Z. Если в списке Yнет элемента X, то целевое утверждение недоказуемо. Граничное условие выполняется тогда, когда мы находим искомый элемент X, иначе осуществляется рекурсивная обработка хвоста списка Y:

исключ1(А,[А|L],L):-!.

исключ1(А,[В|L],[В|М]):- исключ1(А,L,М).

Легко добавить утверждение, которое обеспечит доказательство предиката, когда второй аргумент сократится до пустого списка. Это утверждение, реализующее новое граничное условие, есть исключ1(_,[],[])-

Исключение всех вхождений некоторого элемента;Цель исключить(Х, L1, L2)создает список L2путем удаления всех элементов Xиз списка L1. Граничное условие выполняется тогда, когда L1является пустым списком. Это означает, что мы рекурсивно исчерпали весь список. Если Xнаходится в голове списка, то результатом является хвост этого списка, из которого Xтоже удаляется. Последний случай возникает, если во втором аргументе обнаружено, что-то отличное от X. Тогда мы просто входим в новую рекурсию.

исключить(_, [],[]).

исключить(Х,[Х|L],М):-!, исключить(Х,L,М).

исключить(Х,[Y|L1],[Y|L2]):- исключить(Х,L1,L2).

Замещение:Этот предикат очень напоминает исключить,с той лишь разницей, что вместо удаления искомого элемента мы заменяем его некоторым другим элементом. Цель заменить(Х, L,A,M)строит новый список Миз элементов списка L, при этом все элементы Xзаменяются на элементы А. Здесь возможны 3 случая. Первый, связанный с граничным условием, в точности совпадает с тем, что было в исключить.Второй случай – когда в голове второго аргумента содержится элемент X, а третий – когда там содержится нечто отличное от X:

заменить(_,[],_,[]).

заменить(Х,[Х|L],А,[А|М]):-!, заменить(Х,L,А,М).

заменить(Х,[Y|L],А,[Y|М]):- заменить(Х,L,А,М).

Подсписки:Список Xявляется подсписком списка Y, если каждый элемент Xсодержится и в Yс сохранением порядка следования и без разрывов. Например, доказуемо следующее:

подсписок[[собрание, членов, клуба],[общее, собрание, членов, клуба, будет, созвано, позже]).

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

подсписок([Х|L],[Х|М]):- совпало(L,M),!.

подсписок(L,[_|М]):- подсписок(L,M).

совпало([],_).

совпало([Х|L],[Х|М]):- совпало(L,М).

Отображение:Это мощный метод, заключающийся в преобразовании одного списка в другой с применением к каждому элементу первого списка некоторой функции и использованием ее результата в качестве очередного элемента второго списка. Программа преобразования одного предложения в другое, которая рассматривалась в гл. 3, является одним из примеров отображения. Мы говорим, что «отображаем одно предложение в другое».

Отображение настолько полезно, что заслуживает отдельного раздела. Кроме того, поскольку списки в Прологе – это просто частные случаи структур, мы отложим обсуждение отображения списков до разд. 7.12. Отображение многолико. В разд. 7.11, посвященном символическому дифференцированию, описывается способ отображения одного арифметического выражения в другие.

7.6. Представление и обработка множеств

Множество- одна из наиболее важных структур данных, используемых как в математике, так и в программировании. Множество – это набор элементов, напоминающий список, но отличающийся тем, что вопрос о том, сколько раз и в каком месте что-либо входит в множество в качестве его элемента, не имеет смысла. Так, множество (1, 2, 3) – это то же самое множество, что и (1, 2, 3, 1), поскольку значение имеет только сам факт, принадлежит данный элемент множеству или нет. Элементами множеств могут также быть другие множества. Самой фундаментальной операцией над множествами является определение того, принадлежитнекоторый элемент данному множеству или нет.

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

Над множествами обычно определяется следующий набор операций (мы будем применять и общепринятые математические обозначения для тех читателей, кто к ним привык):

Принадлежность множеству: XY

Xпринадлежит некоторому множеству Y, если Xявляется одним из элементов Y.

Пример: а{с,а,t}.

Включение: X‚ Y

Множество Yвключает в себя множество X, если каждый элемент множества Xявляется также элементом Y. Множество Yможет содержать некоторые элементы, которых нет в X.

Пример: {x,r,u}‚ {p,q,r,f,t,u,v,w,x,y,z}.

Пересечение: X)Y

Пересечением множеств Xи Yявляется множество, содержащее те элементы, которые одновременно принадлежат Xи Y.

Пример: {r,a,p,i,d})  {p,i,c,t,u,r,e}= {r,i,p}.

Объединение: X*  Y

Объединением множеств Xи Yявляется множество, содержащее все элементы, принадлежащие Xили Yили одновременно им обоим.

Пример: {a,b,c}*  {с,d,е} = {a,b,c,d,e}.

Это – основные операции, которые обычно используются при работе с множествами. Теперь мы можем приступить к написанию Пролог-программ, реализующих каждую из них. Первая основная операция 'принадлежность' реализуется тем же самым предикатом принадлежит, с которым мы уже встречались несколько раз. Однако в нашем определении принадлежитв граничном случае нет символа «отсечения», поэтому мы можем создавать последовательные элементы списка, используя возвратный ход:

принадлежит(Х,[Х|_]).

принадлежит(Х,[_|Y]):- принадлежит(Х,Y).

Следующая операция 'включение' реализуется предикатом включает, причем включает(Х, Y)завершается успешно, если Xявляется подмножеством Y, т. е. Yвключает X. Второе утверждение в его определении опирается на математическое соглашение о том, что пустое множество является подмножеством любого множества. В Прологе это соглашение дает способ проверки граничного условия для первого аргумента, поскольку запрограммирована рекурсивная обработка его хвоста:

включает([А|Х],Y):- принадлежит(А,Y), включает(Х,Y).

включает([],Y).

Следом идет самый сложный случай, реализация пересечения. Целевое утверждение пересечение(Х, Y,Z) доказуемо, если пересечением Xи Yявляется Z. Это как раз тот случай, когда используется предположение, что данные списки не содержат повторяющихся элементов:

пересечение([], X, []).

пересечение([X|R],Y,[X|Z]):-принадлежит(Х, Y),!,пересечение(R, Y,Z).

пересечение([Х|R],Y,Z):- пересечение(R, Y,Z).

Наконец, объединение. Целевое утверждение объединение (X,Y,Z)доказуемо, если объединением Xи Yявляется Z. Заметим, что реализация предиката объединениесконструирована на основе определений предикатов пересечениеи присоединить:

объединение([],Х,Х).

объединение([Х|R],Y,Z):- принадлежит(Х,Y),!,

объединение(R,Y,Z). объединение([X |R],Y,[X|Z]):- объединение(R,Y,Z).

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

7.7. Сортировка

Иногда полезно упорядочить список элементов в соответствии с заданным порядком их следования. Если элементами списка являются целые числа, то для того чтобы определить соблюден ли порядок следования, можно использовать предикат '‹'. Список (1, 2, 3) упорядочен, поскольку любая пара соседних целых чисел этого списка удовлетворяет предикату '‹'. Если элементами списка являются атомы, то мы можем воспользоваться предикатом меньше,о чем уже говорилось в гл. 3. Список [alpha,beta,gamma]упорядочен в алфавитном порядке, поскольку каждая пара соседних атомов этого списка удовлетворяет предикату меньше.

Специалисты по информатике разработали много методов сортировки списков, когда задан некоторый предикат, который говорит нам о том, находятся ли соседние элементы списка в требуемом порядке следования. Мы рассмотрим Пролог-программы для четырех таких методов: наивная сортировка, сортировка включением (вставками), сортировка методом пузырька и быстрая сортировка. В каждой программе используется предикат упорядочено, который может быть определен через '‹' меньшеили любой другой предикат по вашему усмотрению, в зависимости от того, какого рода структуры вы сортируете. При этом предполагается, что целевое утверждение упорядочено(Х, Y)доказуемо, если объекты Xи Yудовлетворяют требуемому порядку следования, т. е. если Xв некотором смысле меньше чем Y.

Один из способов сортировки чисел в порядке возрастания состоит в следующем: вначале создается некоторая перестановка чисел, затем проверяется расположен ли полученный список в порядке возрастания. Если это не так, то создается новая перестановка чисел. Этот метод известен под названием наивная сортировка:

наивсорт(L1,L2):- перестановка(L1,L2),отсортировано(L2),!.

перестановка(L,[H|T]):-присоединить(V,[Н|U],L), присоединить(V,U,W), перестановка(W,Т).

перестановка([],[]).

отсортировано(L):- отсортировано(0,L).

отсортировано(_,[]).

отсортировано(N,[H|T]):- упорядочено(N,Н),отсортировано(Н,T).

Используемый здесь предикат присоединитьмногократна определялся ранее. В этой программе предикаты имеют следующий смысл:

Наивсорт(L1, L2)означает, что L2– это список, являющийся упорядоченной версией списка L1;

Перестановка(L1, L2)означает, что L2- это список, содержащий все элементы списка L1в одном из многих возможных порядков их следования; в терминологии разд. 4.3 – это генератор.

Предикат отсортировано(L)означает, что числа в списке Lупорядочены в порядке возрастания; это – 'контролер'.

Процесс поиска упорядоченной версии списка заключается в создании некоторой перестановки элементов и проверки ее упорядоченности. Если это так, то единственный ответ найден. Иначе мы вынуждены продолжать создание перестановок. Это не очень эффективный метод сортировки списка.

При сортировке включениемкаждый элемент списка рассматривается отдельно и включается в новый список на соответствующее место. Этот метод используется, например, при игре в карты, когда игрок сортирует имеющиеся на руках карты, вынимая и переставляя по одной карте за раз. Целевое утверждение вклюсорт(X, Y)доказуемо тогда, когда список Yявляется упорядоченной версией списка X. Каждый элемент удаляется из головы списка и передается предикату вклюсорт2, который включает этот элемент в список и возвращает измененный список.

вклюсорт([],[]).

вклюсорт([Х|L],М):- вклюсорт(L,N), вклюсорт2(Х,N,М).

вклюсорт2(Х,[А|L],[А|М]):- упорядочено(А,Х),!,вклюсорт2(Х,L,М).

вклюсорт2(Х,L,[Х |L]).

Чтобы сделать предикат сортировки включением более универсальным, удобно задавать предикат проверки порядка следования в качестве аргумента предиката вклюсорт.Используем для этого предикат ' =..', который рассматривался в гл. 6:

вклюсорт([],[],_).

вклюсорт([Х|L],М,О):- вклюсорт(L,N,О),вклюсорт2(Х,N,М,О).

вклюсорт2(Х,[А|L],[А|М],0):-Р=..[O,А,Х], call(P),! ,вклюсорт2(Х,L,М,O).

вклюсорт2(Х,L,[Х|L],О).

Теперь мы можем использовать такие цели как вклюсорт(А,В,'‹') и вклюсорт(А,В,меньше),т. е. отпадает необходимость в предикате упорядочено.Этот метод может быть распространен.и на другие алгоритмы сортировки данного раздела.

При сортировке методом пузырькав списке ищется пара соседних элементов, расположенных не по порядку следования. Если такие элементы находятся, то они меняются местами. Этот процесс продолжается до тех пор, пока перестановки станут ненужными. Если при сортировке включением выбранный элемент как бы «тонет», попадая на нужное место, то сортировка методом пузырька названа так потому, что здесь элементы, подобно пузырькам воздуха, постепенно «всплывают», занимая соответствующее место.

пусорт(L,S):-присоединить(Х,[А,В|Y],L),упорядочено(В,А),присоединить(Х, [В, А|Y],M),пусорт(M,S).

пусорт(L,L).

присоединить([],L,L).

присоединить([Н|Т],L[Н|V]):- присоединить(Т,L,V).

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

Быстрая сортировка- это более сложный метод сортировки, предложенный Хоором и применимый для сортировки больших списков. Для реализации быстрой сортировки на Прологе мы должны сначала разделить список, состоящий из головы Ни хвоста Т, на два списка Lи Мтакие, что:

• все элементы Lменьше или равны Н;

• все элементы Мбольше чем Н;

• порядок следования элементов в Lи Мтакой же как в [Н |Т].

После того, как мы разделили список, применяем быструю сортировку к каждому из полученных списков (это рекурсивная часть), и присоединяем Мк LЦель разбить(H,T,L,M)разделяет список [Н |Т]на списки Lи М, как сказано выше:

paзбить(H,[A|X],[A|Y],Z):- А=‹ Н, разбить(Н,Х,Y,Z).

разбить(Н,[А|Х],Y,[А|Z]):- А › Н, разбить(Н,Х,Y,Z).

разбить(_,[], [],[]).

Тогда программа быстрой сортировки примет вид:

бысорт([],[]).

бысорт([H|T],S):-разбить(Н,Т,А,В),бысорт(А,А1),бысорт(В,В1), присоединить(А1, [H|B1],S).

Предикат присоединитьможно встроить внутрь программы сортировки. Тогда получается другой предикат

бысорт2 ([H|T], S,X):-разбить(Н,T,А,В), бысорт2(А,S,[Н|Y]), бысорт2(B,Y,X).

бысорт2([],Х,Х).

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

Более подробные сведения о методах сортировки можно найти в книге D. Knuth, The Art of Computer Programming,v. 3 (Sort and Searching), Addison-Wesley, 1973 (Имеется перевод: Кнут Д. Искусство программирования для ЭВМ, т. 3 (Сортировка и поиск). М.: Мир, 1978.- Перев.)Метод быстрой сортировки Хоора описан в его статье в Computer Journal n. 5 (1962), стр. 10-15.

Упражнение 7.5.Проверьте, что предикат перестановка (L1, L2)строит все перестановки заданного списка L1(причем каждую по одному разу) и выдает их как альтернативные значения списка L2. В каком порядке строятся эти решения?

Упражнение 7.6.Быстрая сортировка лучше всего работает ка больших списках, поскольку там она обеспечивает более быструю сходимость к решению. В то же время объем работы, выполняемой на каждом уровне рекурсии быстрой сортировки, превышает то, что делается в других методах, из-за использования разбить. Поэтому, при сортировке небольших списков рекурсивные вызовы бысорт,видимо, можно заменить обращениями к другим методам сортировки, например, к сортировке включением. Разработайте «гибридную» программу, которая использует быструю сортировку для обработки больших подсписков (списков, полученных с помощью предиката разбить),но переключается на другой метод (сортировка включением) при значительном уменьшении длины подсписка. Подсказка: поскольку разбитьдолжен просмотреть все элементы списка, то он может заодно подсчитать и длину списка.