Списки
Список представляет собой основную структуру данных на Прологе.
Список-последовательность из произвольного числа элементов некоторого типа без ограничения на длину списка. Тип данных Список объявляется.
Domins
Списковый_тип=тип*
*Говорит, что перем. – список.
Тип_тип элементолв списка (стандартный, заданный пользователем в domains).
Domins
Int_list=integer*
Predictes
Nonderterm numbers(int_list)
Аргумент предиката-список целых чисел. Ввод списков с клавиатуры выполняется стандартным предикатом readtern.
Domains
Int_list=integer*
Predicates
Nonderterm dal (int_li nt, integer, int_list)
Nondeterm оbvab
Goal
Obvab.
….
В Прологе введены понятия головы и хвоста списка. Голова 1-й элемент списка, хвост-остальная часть списка. Хвост сам является спискам.
Пустой список [ ], список из одного элемента [x]
Пусть имеется список Z=[6,8], М и N – свободные переменные. Тогда передает 2 [M/N] доказательство успешно, M связывается с 6, а N- со списком из одного элемента.
Y=M+1 допустима
X=N+1 не допустима
| Предикат1 | Предикат2 | Результат |
| Obrab(l) L=[1,2,3] Obrab(l) L=[1,2,3] Obrab(L) L=[2] Obrab(L) L=[2] Obrab(L) L=[] Obrab(L) L=(1,2,3) | Obrab(x) x-свободная переменная Obrab[H/T] H,T-свободный Obrab[H/T] H,T-свободный Obrab(X)X-свободная переменная Obrab[] Obrab[] | Успешное сопоставление X=[1,2,3] Успешное сопоставление H=1,T=[2,3] Успешное сопоставление H=2, T=[] Успешное сопоставление X=2/x-целочисленная переменная, а не список Успешное сопоставление, т.к. аргументы предикатов равны(оба-пустые символы) Успешное сопоставление Неудача, т.к. аргументы не равны |
Общие рекомендации по составлению программ со списками:
1. В операциях со списками всегда есть рекурсия.
2. Предикаты для реализаций операций со списками обычно имеют несколько клозов. 1-ый из них относится к простейшему случаю, последующие клозы относятся к более общим случаям и имеют следующее назначение.
Если список не соответствует простейшему случаю, то следует уменьшить на 1 элемент и применить рекурсию к укороченному списку.
3. Предикаты, предназначенные для получения одного списка из другого всегда имеют не меньше 2-х аргументов. Исходный список, список-результат.
К числу основных операций со списком можно отнести:
- проверка принадлежащему списку;
Добавление элемента в список;
- удаление элемента из списка;
- присоединение списка у другому;
- вывод элементов списка на экран.
Примеры предикатов обработки списков
1. Добавление элемента в конец списка.
Если исходный список пуст, формируется список из одного элемента. В противном случае нужно отделить от исходного списка голову, добавить предикат dobav и объявляется новый.
Dobav [x,[],[x]):-!
Dlina(x,List,Lres):-List=[H/T1],dobav
(x,T,T1),Lres=[H/T1].
2. Определение длины списка
Если список пуст, длина равна нулю, иначе длина хвоста +1.
Dlina([],0):-!
Dlina(List,N):-List=[ /T],dlina (T,N1),
N=N1+1.
3. Проверка принадлежащего элемента к списку.
Переместим х-элемент, принадл. Кот. следует определить к списку L,
L-список.
prinadl (X,L):-L=[X|_],!.
prinadl (X,L):-L=[_|T], prinadl (X,T).
1-й предикат проверяет, совпадает ли элемент с головой списка, если нет, проверяется принадлежащие к хвосту.
4. Поиск max элемента списка.
Если список пуст max=0. Если список из одного элемента, равен этому элементу.
max_elem([ ],Max):-Max=0,!.
max_elem([X],Max):-Max=X,!.
max_elem([H|T],Max):-max_elem (T,M),max1 (T,H,Max).
max1(x1,x2,Max):-x1>=x2,Max=x1,!.
Max1(_,x2,Max):-Max=x2.
5. Выделение части из списка.
Podspisok (L,1,1,Res):-L=[H|_],Res=[H],!.
Podspisok (L,1,N1,Res):-L=[H|T],N21=N2-1,
Podspisok(T,1,N21,Res1),Res=[H|Res1],!.
Podspisok(L,N1,N2,Res):-L=[ |T],N11=N1-1,
N21=N2-1,PODSPISOK(T,N11,N21,Res).
Пример
Predicates
%nondeterm vyvod
nondeterm poisk(string,intrger)
nondeterm rabota(string,integer)
nondeterm proekt(string,string,integer)
goal
poisk(“Ivanov”,500).
/*vyvod.*/
clauses
/*vyvod:-write(“Familia:”),readln(F)
write(“Stoimost:”), readln (St),
poisk(F,S).*/
poisk(Fam,St):-rabota (Fam,Shift),
proekt(Shifr,Zak,Stiom),
stoim>=St
write(Shifr,” “, Zak),fail.
domains
spisok=string+
predicates
nondeterm rabota (string,spisok)
nondeterm proekt (string,string,integer)
nondeterm prinadl (string, spisok)
nondeterm poisk (string)
% nondeterm start(string)
goal
poisk (“Rubin”).
clauses
% stsrt (KK):-poisk(Zak).
poisk (Zak):-proekt (Shifr,Zak,_),
write (Shifr),nl,
rabota (Fam,Spis_Shifr),
prinadl (Shifr,Spis_shifr),
write (Fam), nl, fail.
poisk().
prinadl (X,L):-L=[X|_],!.
prinadl (X,L):-L=[_|T],
prinadl (X,T).
rabota (“Antonov”, [“P20”]),
rabota (“Ivanov”, [“P70”,”P100”,”P120”]).
rabota (“Petrov”, [“P100]”).
rabota (“Vasiliev”, [“P70”,”P120”]).
proekt (“P20”,”Rubin”,700).
proekt (“P100”,”Rubin”,1400).
proekt (“P70”,”Gorizont”,500).
proekt (“P120”,”Kristall”,1100).
После ввода “Rubin” выполняется проверка poisk. Это предикат-правило, и требуется доказать все предикаты, входящие в него.
В proekt Zak связывается с “Rubin” и обращается к proekt. Не связывающая переменная Shifr, определяет что может быть любое значение.
Проект сопоставляется успешно Shifr получает значение “P20”, оно выводится на экран. Доказательство следующего предиката rabota. Для этого выполняется сопоставление “Antonov” и Shift состоит из одного элемента – “P20”.
Он связывается и доказывается prinadl. Shift должен определить на принадлежность списка шифров rabota Антонова.
Rabota сопоставляется с “Ivanov”. Неудача, возврат к предыдущей.
По “P20” удачно завершилось одно сопоставление.
Основные типы данных
База данных на Прологе