Важным и часто используемым типом данных является список.
Список - это упорядоченный набор объектов, следующих друг за другом. Составляющие списка внутренне связаны между собой, поэтому с ними можно работать и как с группой (списком в целом), так и как с индивидуальными объектами (элементами списка).
Список является набором объектов одного и того же типа.
Объектами списка могут быть целые числа, действительные числа, символы, символьные строки и сложные объекты. Порядок расположения элементов является отличительной чертой списка; те же самые элементы, упорядоченные иным способом, представляют другой список.
Совокупность элементов списка заключается в квадратные скобки [], а друг от друга элементы отделяются запятыми.
Примерами списков могут служить:
[1,2,3,6,9,3,4]
[3.2,4.6,1.1,2.64,100.2]
["Вчера","Сегодня","Завтра"]
Количество элементов в списке называется его длиной.
Список, не содержащий элементов, называется пустым или нулевым списком и обозначается так: [].
|
|
Непустой список можно рассматривать как состоящий из двух частей: первый элемент списка - его голова, и остальная часть списка - хвост. Голова является элементом списка, хвост есть список сам по себе.
Отличительной особенностью описания списка является наличие звездочки (*) после имени списка элементов.
/* Программа: П т и ц ы. Работа со списками. */
domains
bird_name = symbol
bird_list = bird_name*
predicates
birds(bird_list)
clauses
birds(["ласточка","синица","чиж","воробей"]).
Выполним программу со следующими внешними запросами:
birds(All).
birds([_,_,_,B]).
birds([B1,B2,_,_]).
В программе "Птицы" для получения доступа к элементам списков были использованы внешние целевые утверждения. Задание цели в виде birds(All) обеспечивало присваивание переменной All всего списка вцелом. Напротив, цель birds([_,_,_,B]) позволила извлечь из списка лишь один элемент. В этом случае, требовалось точное знание числа элементов списка.
Для работы со списками, длина которых заранее неизвестна используется метод разделения списка на
голову и хвост. Данный метод работает вне зависимости от длины списка, до тех пор, пока список не будет исчерпан.
Операция деления списка на голову и хвост обозначается при помощи вертикальной черты (|):
[Head|Tail].
Head является переменной для обозначения головы списка, переменная Tail обозначает хвост списка.
Вывод элементов списка:
print_list([]).
print_list([Head|Tail]):- write(Head), nl, print_list(Tail).
Поиск элемента в списке:
find_it(Head,[Head|_]).
find_it(Head,[_|Tail]):- find_it(Head,Tail).
Деление списков.
При работе со списками достаточно часто требуется разделить список на несколько частей.
/* Программа: " Деление списка" */
|
|
Domains
middle = integer
list = integer*
Predicates
split(middle,list,list,list)
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(_, [], [], []).
Goal split(12,[96,32,8,16,55,12],L1,L2), write(“L1=”, L1, “, L2=”, L2).
Элемент Мiddle здесь является критерием, по которому происходит деление списков, L - это исходный список, а L1 и L2 - подсписки, получающиеся в результате деления списка L. Если элемент исходного списка меньше или равен Middle, то он помещается в список L1; если больше, то в список L2.
Правило устроено следующим образом: очередной элемент извлекается из списка при помощи метода разделения списка на голову и хвост, а потом сравнивается с разделителем Middle и помещается в один из списков.
Опpеделение количества элементов в списке.
Одной из самых распространенных задач является задача определения количества элементов некоторого списка. Данная задача легко может быть решена при помощи метода разделения списка на голову и хвост следующим образом: Отделяем от списка голову до тех пор пока не останется пустой список, при этом каждый раз при отделении увеличиваем счетчик элементов списка на единицу.
/* Программа: " Подсчет количества элементов списка". */
domains
number = integer
list = integer*
predicates
sum_list(list,number)
clauses
sum_list([], 0).
sum_list([H | T], Sum):- sum_list(T, Sum1), Sum = 1 + Sum1.
Присоединение списка.
Слияние двух списков и получение таким образом третьего принадлежит к числу наиболее полезных при работе со списками операций. Этот процесс обычно называют присоединением одного списка к другому.
/* Программа: "Присоединение списка" */
domains
n_list = integer *
predicates
append(n_list,n_list,n_list)
clauses
append([],L,L).
append([N|L1],L2,[N|L3]):- append(L1,L2,L3).
Goal append([9,15,3,60,55],[15,2,21],L).