Чтение онлайн

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

9. 1. 1. Замечания в некоторых альтернативных способах представления списков

В главе 3 была введена специальная система обозначений для списков (специальная прологовская нотация), которую мы и использовали в последующем изложении. Разумеется, это был всего лишь один из способов представления списков на Прологе. Список– это, в самом общем смысле, структура, которая либо

пуста,

либо

состоит из головы и хвоста, причем хвост должен быть сам списком.

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

ничего_не_делать

в качестве символа, обозначающего пустой список, и атом

затем

в качестве инфиксного оператора для построения списка по заданным голове и хвосту. Этот оператор мы можем объявить в программе, например, так:

:- ор( 500, xfy, затем).

Список

[ войти, сесть, поужинать]

можно было бы тогда записать как

войти затем сесть затем поужинать

затем ничего_не_делать

Важно заметить, что на соответствующем уровне абстракции специальная прологовская нотация и всевозможные альтернативные способы обозначения списков сводятся, фактически, к одному и тому же представлению. В связи с этим типовые операции над списками, такие как

принадлежит ( X, L)

конк( L1, L2, L3)

удалить( X, L1, L2)

запрограммированные нами в специальной прологовской нотации, легко поддаются перепрограммированию в различные системы обозначений, выбранные пользователем. Например, отношение конк транслируется на язык "затем - ничего_не_делать" следующим образом. Определение, которое мы использовали до сих пор, имеет вид

конк( [ ], L, L).

конк( [X | L1], L2, [X | L3] ) :-

конк( L1, L2, L3).

В новой системе обозначений оно превращается в

конк( ничего_не_делать, L, L).

конк( Х затем L1, L2, Х затем L3) :-

конк(L1, L2, L3).

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

выражений также можно трактовать как своего рода списки. Например, для конъюнктов в исчислении высказываний подошло бы следующее спископодобное представление:

истина соответствует пустому списку,

&– оператор для соединения головы с хвостом, определяемый, например, как

:- ор( 300, xfy, &)

Конъюнкция членов а, b, и с выглядела бы тогда как

а & b & с & истина

Все приведенные примеры базируются, по существу, на одной и той же структуре, представляющей список. Однако в гл. 8 мы рассмотрели существенно другой способ, влияющий на эффективность вычислений. Уловка состояла в том, что список представлялся в виде пары списков, являясь их "разностью". Было показано, что такое представление приводит к очень эффективной реализации отношения конкатенации.

Материал настоящего раздела проливает свет и на то различие, которое существует между применением операторов в математике и применением их в Прологе. В математике с каждым оператором всегда связано некоторое действие, в то время как в Прологе операторы используются просто для представления структур. Упражнения

9. 1. Определите отношение

список( Объект)

для распознавания случаев, когда Объект является стандартным прологовским списком.

Посмотреть ответ

9. 2. Определите отношение принадлежности к списку, используя систему обозначений, введенную в этой разделе: "затем - ничего_не_делать".

Посмотреть ответ

9. 3. Определите отношение

преобр( СтандСпис, Спис)

для преобразования списков из стандартного представления в систему "затем-ничего_не_делать". Например:

преобр( [а, b], а затем b затем ничего_не_делать)

Посмотреть ответ

9. 4. Обобщите отношение преобр на случай произвольного альтернативного представления списков. Конкретное представление задается символом, обозначающим пустой список, и функтором для соединения головы с хвостом. В отношении преобр придется добавить два новых аргумента:

преобр( СтандСпис, Спис, Функтор, ПустСпис)

Примеры применения этого отношения:

?- пpeoбp( [а, b], L, затем, ничего_не_делать).

L = а затем b затем ничего_не_делать

?- преобр( [а, b, с], L, +, 0).

L = а+(b+(с+0) )

Посмотреть ответ

9. 1. 2. Сортировка списков

Сортировка применяется очень часто. Список можно отсортировать (упорядочить), если между его элементами определено отношение порядка. Для удобства изложения мы будем использовать отношение порядка

больше( X, Y)