|
В языках, предназначенных для программирования задач искусственного интеллекта, важную роль играют динамические структуры данных, называемые списками. Главное достоинство списков состоит в том, что при их обработке операции вставки, замены и удаления элементов выполняются весьма просто.
Список - один из самых простых и полезных типов структур. Мы рассмотрим также некоторые программы для выполнения типовых операций над списками и, кроме того, покажем, как можно просто записывать арифметические выражения и операторы, что во многих случаях позволит улучшить «читабельность» программ. Базовый Пролог, расширенный этими тремя добавлениями, станет удобной основой для составления интересных программ. Списки ¾ структуры данных с последовательным доступом, и поэтому основным средством их обработки является рекурсия.
Все структурные объекты Пролога - это деревья. Списки не являются исключением из этого правила. Каким образом можно представить список в виде стандартного прологовского объекта? Мы должны рассмотреть два случая: пустой список и не пустой список. В первом случае список записывается как атом []. Во втором случае список следует рассматривать как структуру, состоящую из двух частей:
- первый элемент, называемый головой списка;
- остальная часть списка, называемая хвостом.
Список в языке Пролог представляет собой заключенную в квадратные скобки [] последовательность термов, разделенных запятыми:
[<терм1>,<терм2>,…<термn>]. Список¾ это составной терм или структура, главный функтор которой обозначается символом «.» (точка).
Структура Список может быть представлена в виде так называемой точечной пары .(H,T), где Н ¾ первый элемент списка, называемый головой списка, а Т ¾ все остальные элементы списка, называемые хвостом списка. Голова списка является термом, а хвост ¾списком.
В языке Пролог список, разделенный на головы и хвост, обозначается следующим образом: [H|T], например [a|[d,b,k,l]]. Возможность разделения списка на голову и хвост играет важную роль в программировании рекурсивных процедур обработки списков.
Число элементов в списке называется длиной списка. Длина списка может динамически изменяться в процессе выполнения запроса. Список, не имеющий ни одного элемента, обозначается [] и называется пустым списком. Длина пустого списка равно нулю. Пустой список нельзя разделить на голову и хвост. Голова и хвост списка могут быть заполнены константами, числами или символьными термами, например [1|[6,8,12,9]] или [a|[r,t,y,u]].
Более подробно представления списков можно посмотреть здесь.
|
