У Клоксин - ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ ПРОЛОГ

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

Деталиузлов(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).

В этом разделе мы рассмотрим некоторые основные предикаты, полезные при работе со списками. Поскольку Пролог позволяет работать с произвольными структурами данных, списки не могут играть в нем той незаменимой роли, какая им отводится в других языках программирования, таких, как Лисп и Поп-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).

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