Prolog

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

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

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