Работа со списками

Важным и часто используемым типом данных является список.

Список - это упорядоченный набор объектов, следующих друг за другом. Составляющие списка внутренне связаны между собой, поэтому с ними можно работать и как с группой (списком в целом), так и как с индивидуальными объектами (элементами списка).

Список является набором объектов одного и того же типа.

Объектами списка могут быть целые числа, действительные числа, символы, символьные строки и сложные объекты. Порядок расположения элементов является отличительной чертой списка; те же самые элементы, упорядоченные иным способом, представляют другой список.

Совокупность элементов списка заключается в квадратные скобки [], а друг от друга элементы отделяются запятыми.

Примерами списков могут служить:

[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).