На этом шаге мы рассмотрим использование списков.

Список является рекурсивной составной структурой данных, поэтому нужны алгоритмы для его обработки. Главный способ обработки списка - это просмотр и обработка каждого его элемента, пока не будет достигнут конец.

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

Печать списков

Если нужно напечатать элементы списка, это делается так, как показано ниже.

   domains
      list  =  integer* % Или любой тип, какой вы хотите
   predicates 
      write_a_list(list)
   clauses
      write_a_list([]). % Если список пустой - ничего не делать
      write_a_list([H |T]):- % Присвоить Н-голова,Т-хвост, затем...
      write(H),nl, 
      write_a_list(T).
   goal
      write_a_list([1,2,3]).

Текст этой программы можно взять здесь.

Результат работы программы можно посмотреть на рис.1

Рис.1. Результат работы программы pro44_1.pro

Вот два целевых утверждения write_a_list, описанные на обычном языке:

    Печатать пустой список - значит ничего не делать.
    Иначе, печатать список - означает печатать его голову (которая является одним элементом),
       затем печатать его хвост (список).

При первом просмотре целевое утверждение таково:

   write_a_list([1,2,3]).

Оно удовлетворяет второму предложению при H=1 и T=[2,3]. Компьютер напечатает 1 и вызовет рекурсивно

   write_a_list:-
      write_a_list([2,3]). % Это write_a_list(T)

Этот рекурсивный вызов удовлетворяет второму предложению. На этот раз H=2 и T=[3], так что компьютер печатает 2 и снова рекурсивно вызывает write_a_list с целевым утверждением

   write_a_list([3]).

Итак, какому предложению подходит это целевое утверждение? Вспомним, что, хотя список [3] имеет всего один элемент, у него есть голова 3 и хвост [ ]. Следовательно, целевое утверждение снова подходит под второе предложение с H=3 и T=[ ]. Программа печатает 3 и делает рекурсивный вызов:

   write_a_list([ ]).

Теперь видно, что этому целевому утверждению подходит первое предложение. Второе предложение не подходит, т. к. [ ] нельзя разделить на голову и хвост. Так что, если бы не было первого предложения, целевое утверждение было бы невыполнимым. Но первое предложение подходит, и целевое утверждение выполняется без дальнейших действий.

Подсчет элементов списка

Рассмотрим, как можно определить число элементов в списке. Что такое длина списка? Вот простое логическое определение:

   Длина [ ] - 0.
   Длина любого другого списка - 1 плюс длина его хвоста.

Можно ли применить это? В Прологе - да. Для этого нужны два предложения.

   domains
      list = integer* % или любой другой тип
   predicates
      length_of(list,integer)
   clauses
      length_of([],0).
      length_of([_|T],L):-
         length_of(T,TailLength),
         L=TailLength + 1.

Текст этой программы можно взять здесь.

Посмотрим сначала на второе предложение. Действительно, [_ |T] можно сопоставить любому непустому списку, с присвоением T хвоста списка. Значение головы не важно, главное, что оно есть, и компьютер может посчитать его за один элемент.

Таким образом, целевое утверждение

   length_of([1,2,3],L).

подходит второму предложению при T=[2,3]. Следующим шагом будет подсчет длины T. Когда это будет сделано (не важно как), TailLength будет иметь значение 2, и компьютер добавит к нему 1 и затем присвоит L значение 3. Итак, как компьютер выполнит промежуточный шаг? Это шаг, в котором определяется длина [2,3] при выполнении целевого утверждения

   length_of([2,3],TailLength).

Другими словами, length_of вызывает сама себя рекурсивно. Это целевое утверждение подходит второму предложению с присвоением:

[3] из целевого утверждения присваивается T в предложении;
TailLength из целевого утверждения присваивается L в предложении.

Напомним, что TailLength в целевом утверждении не совпадает с TailLength в предложении, потому что каждый рекурсивный вызов в правиле имеет свой собственный набор переменных.

Итак, целевое утверждение состоит в том, чтобы найти длину [3], т.е. 1, а затем добавить 1 к длине [2,3], т.е. к 2, и т. д.

Таким образом, length_of вызывает сама себя рекурсивно, чтобы получить длину списка [3]. Хвост [3] - [ ], так что T будет присвоен [ ], а целевое утверждение будет состоять в том, чтобы найти длину [ ] и, добавив к ней 1, получить длину [3].

На сей раз все просто. Целевое утверждение

   length_of([],TailLength)

удовлетворяет первому предложению, которое присвоит 0 переменной TailLength. Пролог добавит к нему 1 и получит длину [3], затем вернется к вызывающему предложению. Оно в свою очередь снова добавит 1, получит длину [2,3] и вернется в вызывающее его предложение. Это начальное предложение снова добавит 1 и получит длину [1,2,3].

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

   length_of([1,2,3],L1).
   length_of([2,3],L2).
   length_of([3],L3).
   length_of([],0).
   L3=0+1=1.
   L2=L3+1=2.
   L1=L2+1=3.

Со следующего шага мы начнем рассматривать хвостовую рекурсию.

Предыдущий шаг Содержание Следующий шаг