На практике часто встречаются задачи, связанные с перечислением объектов. В некоторых случаях при решении задач важно сохранять информацию об уже сделанных шагах решения, чтобы их не повторять. Такую операцию удобно реализовывать помощью списков.
Список — это простая структура данных, широко используется в нечисловом программировании. Список представляет собой последовательность, составленную из произвольного числа элементов.
Например, перечисление объектов: Мери, Джон, Том, Анн можно записать так:
["Мери", "Джон", "Том", "Анн"]
Элементами списка могут быть любые структуры.
Первый элемент называется головой списка, остальная часть — хвостом. Например, для списка
[a, b, c, d, e]
a — это голова, а хвостом является список [b, c, d, e]. Для представления пустого списка используется [].
На практике часто бывает удобным трактовать хвост списка как самостоятельный объект, используется вертикальная черта, отделяющую голову от хвоста:
L=[a|[b, с]]=[a, b|[c]]=[a, b, c|[]]
Можно определить список рекурсивно.
Список — это структура данных, определяемая следующим образом:
- список является пустым,
- либо состоящим из двух компонентов, называемых головой и хвостом списка. Головой списка может быть элемент любого типа, а хвост должен быть, в свою очередь, списком.
Определение списка через его голову и хвост в сочетании с рекурсией лежит в основе большого числа программ, оперирующих со списками. Эти программы состоят:
- из факта, ограничивающего рекурсию и описывающего операцию для пустого списка;
- из рекурсивного правила, определяющего операцию над списком, состоящим из головы и хвоста (в голове правила), через операцию над хвостом (в подцели).
Перед использованием списка в программе его необходимо описать.
domains element= integer % тип данных элементов списка list= element*
Для того чтобы использовать предикат к спискам различного типа, необходимо описать один и тот же предикат для всех типов списков.
domains list1=integer* list2=string* predicates member (integer, list1) member (string, list2)
Предположим, что есть база данных с фактами о разных людях, и каждый факт связывает имя человека и его массу. Если необходимо объединить данные о массе всех людей в единой списковой переменной L, то используется стандартный предикат findall.
domains list=integer* predicates person(string,integer) clauses person(dan,70). person(ann,80). person(ben,77). goal findall (X, person(_,X), L), write(L). [70,80,77] L=[70,80,77] 1 Solution
Пример 1. Принадлежность элемента списку.
Составление программы для отношения принадлежности может быть основано на следующих соображениях:
а) X есть голова L, либо
б) X принадлежит хвосту L
predicates member (type, list) clauses member (H,[H|T]). member (H,[Y|T]):- member (H,T).
Применять member можно в двух направлениях
goal member (1,[2,3,1,2]). yes goal member (X,[1,2,3]). X=1 X=2 X=3 3 Solutions
Пример 2. Соединение двух списков.
Для написания программы удобно воспользоваться графическим представлением.
Необходимо рассмотреть два случая:
- присоединение пустого списка [] к другому списку L есть тот же самый список L.
- присоединение к списку [H|T] списка P есть присоединение хвоста T к списку P и к результату добавить голову H.
predicates append (list, list, list) clauses append ([],L,L). append ([H|T],P,[H|Y]): - append (T,P,Y). goal append ([1,2],[3,4],X). X=[1,2,3,4] goal append (X,[3|Y],[1,2,3,4,5]). X=[1,2] Y=[4,5] goal append (_,[X,3,Y|_],[1,2,3,4,5,6]). X=2 Y=4 goal append (X,[3,4,5|_],[1,2,3,4,5,6,7]). X=[1,2]
Пример 3. Удаление элемента из списка.
predicates delete(type, list, list)
Отношение delete можно определить аналогично принадлежности:
- если Х является головой списка, тогда результатом удаления будет хвост этого списка;
- если Х находится в хвосте списка, тогда его нужно удалить оттуда.
clauses delete (X,[X|T],T). delete (X,[Y|T],[Y|T1]): - delete (X,T,T1).
Отношение delete недетерминированно.
goal delete (1,[1,2,1,1],L). L=[2,1,1] L=[1,2,1] L=[1,2,1] 3 Solutions
Пример 4. Перестановки.
Иногда бывает полезно построить все перестановки некоторого заданного списка. Для решения удобно воспользоваться графическим представлением:
predicates reverse (list, list) insert (type, list, list) clauses reverse ([],[]). reverse ([X|L],P): - reverse (L,L1), insert (X,L1,P). insert (X,List,Biglist): - delete (X,Biglist,List). goal reverse ([1,2,3],L). L=[1,2,3] L=[1,3,2] L=[2,1,3] L=[2,3,1] L=[3,1,2] L=[3,2,1] 6 Solutions
Пример 5. Печать элементов списка.
predicates write_list (list) clauses write_list ([]). write_list ([H|T]): - write (H), nl, write_list (T).
Контрольные вопросы и задания
- Дайте определение списку.
- Что означает запись:
domains k=integer p=k* r=p* - Поясните работу предиката findall.
- Напишите программу, сортирующий список по методу пузырька.
- Дайте определение операции отсечения головы списку.
- Каким образом решить задачу, если необходимо в списке объединять разнородные объекты?
- Промоделировать массив 3*10 с помощью списка.
- Прочитайте декларативно и процедурно определение предиката member.
- Как будет описан в domains список, состоящий из букв и чисел?
- Определите список через двоичное дерево.
- Сравните описание списка в Prolog и Pascal.
- Сформулируйте алгоритм решения задачи со списками.
- Выделите в рекурсивном определении списка граничное условие, общее условие.
- Напишите программу, преобразующую список целых чисел в двоичное дерево.