Назад | Содержание| Вперёд Глава 3 СПИСКИ, ОПЕРАТОР...

Глава 3

СПИСКИ, ОПЕРАТОРЫ, АРИФМЕТИКА

В этой главе мы будем изучать специальныеспособы представления списков. Список- один из самых простых и полезных типов структур.Мы рассмотрим также некоторые программы длявыполнения типовых операций над списками и,кроме того, покажем, как можно просто записыватьарифметические выражения и операторы, что вомногих случаях позволит улучшить"читабельность" программ. Базовый Пролог(глава 2), расширенный этими тремя добавлениями,станет удобной основой для составленияинтересных программ.

3. 1.    Представление списков

Список - это простая структура данных,широко используемая в нечисловомпрограммировании. Список - этопоследовательность, составленная изпроизвольного числа элементов, например энн,теннис, том, лыжи. На Прологе этозаписывается так:

        [ энн, теннис,том, лыжи ]

Однако таково лишь внешнее представлениесписков. Как мы уже видели в гл. 2, все структурныеобъекты Пролога - это деревья. Списки не являютсяисключением из этого правила.

Каким образом можно представить список в видестандартного прологовского объекта? Мы должнырассмотреть два случая: пустой список и не пустойсписок. В первом случае список записывается какатом  [ ].  Во втором случае список следуетрассматривать как структуру состоящую из двухчастей:

(1)    первый элемент, называемый головойсписка;

(2)    остальная часть списка, называемая хвостом.

Например, для списка

        [ энн, теннис,том, лыжи ]

энн - это голова, а хвостом являетсясписок

        [ теннис, том,лыжи ]

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

        .( Голова,Хвост)

Поскольку Хвост - это список, он либопуст, либо имеет свои собственную голову и хвост.Таким образом, выбранного способа представлениясписков достаточно для представления списковлюбой длины. Наш список представляется следующимобразом:

        .( энн, .(теннис, .( том, .( лыжи, [ ] ) ) ) )

На рис. 3.1 изображена соответствующаядревовидная структура. Заметим, что показанныйвыше пример содержит пустой список [ ]. Дело в том,что самый последний хвост являетсяодноэлементным списком:

        [ лыжи ]

Хвост этого списка пуст

        [ лыжи ] = .(лыжи, [ ] )

Рассмотренный пример показывает, как общийпринцип структуризации объектов данных можноприменить к спискам любой длины. Из нашегопримера также видно, что такой примитивныйспособ представления в случае большой глубинывложенности подэлементов в хвостовой частисписка может привести к довольно запутаннымвыражениям. Вот почему в Прологепредусматривается более лаконичный способизображения списков, при котором онизаписываются как последовательности элементов,заключенные в квадратные скобки. Программистможет использовать оба способа, но представлениес квадратными скобками, конечно, в большинствеслучаев пользуется предпочтением. Мы, однако,всегда будем помнить, что это всего лишькосметическое улучшение и что во внутреннемпредставлении наши списки выглядят как деревья.При выводе же они автоматически преобразуются вболее лаконичную форму представления. Так,например, возможен следующий диалог:

        ?-  Список1 = [а, b,с],