Собрать(Р, А): Р и А – списки структур чис. А – это список, составленный из тех же элементов, что и Р, но без повторений одной и той же детали. Причем количество каждой детали, указанное в списке А, совпадает с суммой всех повторений этой детали в списке Р. Предикат собрать мы используем для того, чтобы собрать несколько описей наборов одинаковых деталей в одну опись. Например, 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: