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

Лабораторная работа № 4

Списки в языке Prolog

1. Задание и вывод списков

В предыдущих лабораторных работах мы познакомились с основами представления данных в языке Prolog. Это прежде всего утверждения, объектами которых являются конкретные значения (данные). Однако Prolog также поддерживает связанные объекты, называемые списками. Список — это упорядоченный набор объектов, следующих друг за другом. Составляющие списка внутренне связаны между собой, поэтому с ними можно работать и как с группой (списком в целом), и как с индивидуальными объектами (элементами списка).

Рассмотрим структуру, организацию и представление списков.

Список является набором объектов одного и того же домен­ного типа. Объектами списка могут быть целые числа, дейст­вительные числа, символы, символьные строки. Порядок расположения элементов является отличительной чертой списка; те же самые элементы, упорядоченные иным способом, представляют уже совсем другой список, посколь­ку порядок играет важную роль в процессе сопоставления.

Prolog допускает списки, элементами которых являются структуры. Если структуры принадлежат к альтернативно­му домену, то элементы списка могут иметь разный тип. Та­кие списки используются для специальных целей.

Совокупность элементов списка заключается в квадрат­ные скобки — [ ], а друг от друга элементы списка отделя­ются запятыми.

Примеры:

[1,2,3,6,9,3,4]

[3.2,4.6,1.1,2.64,100.2]

["YESTERDAY","TODAY","TOMORROW"]

 

Элементами первого списка являются целые числа, эле­ментами второго — действительные числа, а третьего — символьные строки.

Количество элементов в списке называется его длиной. Например, длина списка ["YESTERDAY","TODAY","TOMORROW"] рав­на 3, а длина списка [4.50,3.50,6.25,2.9,100.15] равна 5. Список может также содержать всего один элемент или даже не содержать элементов вовсе, например ["summer"] или [ ]. Список, не содержащий элементов, называется пус­тым, или нулевым списком.

Непустой список можно рассматривать как состоящий из двух частей: первый элемент списка — его голова (1), а осталь­ная часть списка — хвост (2). Голова является одним из эле­ментов списка, а хвост — это список сам по себе. Голова спис­ка представляет собой отдельное неделимое значение; хвост же — это список, составленный из того, что осталось от исход­ного списка в результате «усекновения головы». Если, напри­мер, список состоит из одного-единственного элемента, то его можно разделить на голову, которой будет этот самый единст­венный элемент, и хвост, являющийся пустым списком.

Список	Голова	Хвост
[1,2,3,4,5]		[2,3,4,5]
['s','k','y']	's'	['k','у']
[cat]	cat	[]
[ ]	не определена	не определен

 

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

Примеры:

num ([1,2,3,6,9,3,4])

realnum ([3.2,4.6,1.1,2.64,100.2])

time (["YESTERDAY","TODAY","TOMORROW"])

 

Введение списков в программу необходимо отразить в трех ее разделах. Домен списка должен быть описан в разде­ле domains, работающий со списком предикат — в разделе predicates и, наконец, надо задать сам список в разделе clauses или goal.

Пример 1:

Domains

bird_list = bird_name *

bird_name = symbol

number_list = integer *

Predicates

birds(bird_list)

score(number_list)

Clauses

birds(["sparrow", "robin", "mockingbird", "thunderbird"]).

score([56,87,63,89,91,62,85]).

Отличительной особенностью описания списка является наличие звездочки (*) после имени домена элементов. Так, запись bird name * указывает, что это домен списка, эле­ментами которого являются bird name, т. е. запись bird_ name * следует понимать как список, состоящий из элемен­тов домена bird_name.

Примеры внешних целей:

birds(All).

birds([В,_,_,_]).

birds([В1,В2,_,_]).

score(All).

score([F,S,T,_,_,_,_]).

 

Рис. 1

При задании целей во втором, третьем и пятом примерах требовалось точное знание количества элементов списка, яв­ляющегося объектом предиката birds, что не всегда воз­можно (с точки зрения пользователя). Но вспомним, что Prolog позволяет отделять от списка первый элемент и обра­батывать его отдельно. Данный метод работает вне зависи­мости от длины списка до тех пор, пока список не будет ис­черпан. Этот метод доступа к голове списка называется ме­тодом разделения списка на голову и хвост.

Операция деления списка на голову и хвост обозначается при помощи вертикальной черты (|):

[Head|Tail].

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

Пример.Правило печати элементов списка [ 4, - 9, 5, 3 ]:

print_list ([]):-!.

print_list ([Head|Tail]):-

write (Head),nl,

print_list (Tail).

 

Когда это правило пытается удовлетворить цель print_ list([4,-9,5,3]), то первый вариант правила — print_ list [ ] — дает неуспех, так как его объект является пустым списком. Напротив, введенный список соответствует объекту второго варианта предиката — print__list ( [Head | Tail] ).

Переменной Head, следовательно, присваивается значение первого элемента в списке: 4, в то время как переменной Tail ставится в соответствие оставшаяся часть списка: [-9,5,3]. Теперь, когда выделен первый элемент списка, с ним можно обращаться так же, как и с любым простым объектом: write (Head) , nl. Далее, так как хвост списка есть список сам по себе, то значение переменной Tail может быть использовано в качестве объекта рекурсивного вызова print_list: print_list (Tail). Когда испытывается дан­ное подправило, Tail имеет значение [-9,5,3]. Снова пер­вый вариант не проходит и соответствие устанавливается при помощи второго. Переменной Head присваивается зна­чение -9, которое затем печатается на экране, а процесс повторяется со списком [5,3]. В итоге, когда переменная Head принимает значение 3, переменной Tail присваива­ется пустой список. Теперь при рекурсивном вызове print_list (Tail) значение Tail соответствует объекту пра­вила print_list ([]). Поскольку этот вариант не имеет ре­курсивных вызовов, цель считается удовлетворенной, и вы­рабатывается условие окончания рекурсии print_list. Тем самым первый вариант позволяет print_list завершиться успехом, когда рекурсивные вызовы опустошат весь список.

Пример 2:

domains

bird_list = symbol *

predicates

birds(bird_list)

print_list(bird_list)

clauses

birds(["sparrow", "robin", "mockingbird", "thunderbird"]).

print_list ([]):-!.

print_list ([Head|Tail]):-

write (Head),nl,

print_list (Tail).

goal

birds(X),

print_list(X).

Рис. 2

 

 

2. Операции над списками

Поиск элемента в спискепредставляет собой просмотр спис­ка для выявления соответствия между элементом данных и элементом просматриваемого списка. Если такое соответст­вие найдено, то поиск заканчивается успехом; в противном случае поиск заканчивается неуспехом. Для сопоставления объекта поиска с элементами просматриваемого списка не­обходим предикат, объектами которого являются эти объект поиска и список:

find_it(3, [1,2,3,4,5]) .

Первый из объектов утверждения — 3 — есть объект поис­ка. Второй — это список [1,2,3,4,5]. Для выделения эле­мента из списка и его сравнения с объектом поиска можно применить метод разделения списка на голову и хвост. Стра­тегия поиска при этом будет состоять в рекурсивном выделе­нии головы списка и ее сравнении с элементом поиска.

Правило поиска может сравнивать объект поиска и голо­ву текущего списка. Саму операцию сравнения можно запи­сать в виде:

find_it(Head,[Head|_]).

Этот вариант правила предполагает наличие соответствия между объектом поиска и головой списка. В данном случае поскольку осуществляется попытка найти соответствие между объектом поиска и головой списка, то нет необходи­мости заботиться о том, что происходит с хвостом. Если объ­ект поиска и голова списка действительно соответствуют друг другу, то результатом сравнения явится успех; если же нет, то неуспех. Но если эти два элемента данных различны, то попытка сопоставления считается неуспешной, происхо­дит откат и поиск другого правила или факта, с которыми можно снова попытаться найти соответствие. Для случая несовпадения объекта поиска и головы списка необходимо предусмотреть правило, которое выделяло бы из списка сле­дующий по порядку элемент и делало бы его доступным для сравнения:

find_it(Head, [Head|_]):-!.

find_it(Head, [_,Tail]):-

find_it(Head, Tail).

 

Если правило find_it (Head, [Head|_]) неуспешно, то происходит откат и делается попытка со вторым вариантом. При этом опять-таки присвоенный переменной Tail список разделяется на голову и хвост, и процесс повторяется, по­ка данное утверждение не даст либо успех (в случае установ­ления соответствия на очередной рекурсии), либо неуспех (в случае исчерпания списка).

Пример 3:

domains

bird_list = symbol *

predicates

birds(bird_list)

find_it(symbol,bird_list)

clauses

birds(["sparrow", "robin", "mockingbird", "thunderbird"]).

find_it(Head, [Head|_]):-

write("I found it!"), !.

find_it(Head, [_|Tail]):-

find_it(Head, Tail).

goal

birds(X),

find_it("robin",X).

Рис.3

Присоединение списка

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

В качестве примера рассмотрим две переменные L1 и L2, представляющие списки и имеющие значения [1,2,3] и [4,5] соответственно. Тогда весь процесс слияния можно представить в виде такой совокупности действий:

· список L3 (результирующий) вначале пуст;

· элементы списка L2 пересылаются в L3; теперь значе­нием L3 будет [4,5];

· элементы списка L1 пересылаются в L3; в результате он принимает значение [1,2,3,4,5].

Структура правила для выполнения этих действий следу­ющая:

append([],L,L):-!.

append([N|LI],L2,[N|L3]):-

append(LI,L2,L3).

 

Если на его вход подать списки Ll= [1,2,3] и L2= [4, 5], то сначала Prolog пытается удовлетворить первый вариант правила:

append([],L,L) .

Чтобы сделать это, первый объект предиката должен быть пустым списком. Однако это не так. Внутренний про­цесс унификации Prolog, пытаясь удовлетворить второе пра­вило append, раскручивает цепочку рекурсий до тех пор, пока не обнулит первый список. Элементы списка при этом последовательно пересылаются в стек. Когда первый объект предиката append окажется пустым списком, становится возможным применение первого варианта правила. Третий список при этом инициализируется вторым:

append([],[4,5],_).

append([], [4,5], [4,5]) .

Теперь Prolog начинает сворачивать рекурсивные вызовы второго правила. Извлекаемые при этом из стека элементы помещаются один за другим в качестве головы к первому и третьему спискам. Следует особо отметить, что элементы из­влекаются в обратном порядке (ведь это стек!), и что значе­ние извлеченного из стека элемента присваивается перемен­ной N одновременно в [N|L1] и [N|L3].

Шаги данного процесса можно представить так:

append([], [4,5], [4,5])

append([3], [4,5], [3,4,5])

append([2,3], [4,5], [2,3,4,5])

append([1,2,3], [4,5], [1,2,3,4,5])

Пример 4:

domains

type=integer

list=type*

predicates

append(list,list,list)

clauses

append([],L,L):-!.

append([H|T],P,[H|Y]):-append(T,P,Y).

goal

append([1,2,3],[4,5],X),

write(X).

 

Рис. 4

 

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

Количество элементов пустого списка равно 0, в противном случае, нужно определить количество элементов в хвосте и найденное значение увеличить на единицу.

Пример 5:

domains

list = integer*

predicates

length(list, integer)

clauses

length([], 0):-!.

length([_|T], N) :-

length(T, N1),

N = N1 + 1.

goal

length ([2, 12, 45], X),

write(X).

Рис. 5

3. Задание.

1. Написать программы, аналогичные приведённым в примерах 2,3,4, но для других предикатов.

2. Написать программу, которая будет находить сумму элементов в списке из целых чисел (программа будет очень похожа на пример 5).