Шумихин / Шумихин / Шумихин - лекция 8

вторник около четырёх
пятница около четырёх
суббота около десяти
если понадобится Шумихин очно

ЛЕКЦИЯ 8
26.10.12

Списки в Прологе

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

Списки в Прологе представляют собой перечень элементов, разделённых запятыми и обрамлённых в квадратные скобки:
[e1, e2, ..., en]
Элементов может быть любое количество.

Специальный список, не содержащий элементов:
[]

Определяются в секции domains следующими правилами:

domains
list = element*
element = ... (какой-либо допустимый в прологе домен)

Признаком того, что домен -- список, является звёздочка.

ПРИМЕР
Список целых
domains
list_i = integer*

Допускаются записи такого типа:
list_i = element*
elemnt = list_i

[[1, 2, 3, [2, 3, 4], []]

Список состоит из двух частей:
- голова списка
- хвост списка

Голова списка -- первый элемент списка.
Хвост -- список оставшихся его элементов.

[1, 2, 3, 4]
Голова: 1
Хвост: [2, 3, 4]

Голова списка от хвоста отделяется с помощью вертикальной черты:
[H|T]

Для записанного выше примера:
H=1
T=[2, 3, 4]

Пустой список разбить на голову и хвост нельзя.

Т.о. определение списка является рекурсивным. Список -- один из представителей рекурсивных типов данных.
Пролог сначала обрабатывает голову списка, а затем рекурсивно -- хвост списка. Выход из такой рекурсии -- обнаружение пустого списка.

Любая версия пролога поддерживает альтернативные варианты объявления домена -- т.н. составные домены. Т.о. элементами одного списка могут быть данные совершенно разных типов. Но об этом чуть позже.

ПРИМЕР 1
Поэлементно распечатать список.

В качестве аргумента предиката write() может выступать список. В таком случае любой Пролог выдаст на экран сразу полный список. Но в данном случае нас интересует не это.

domains
list = integer*

predicates
write_list(list)

clauses
write_list([]).
write_list([H|T]) :- write(H), nl, write_list(T).

goal
write_list([1, 2, 3]).

В ДЗ ИСПОЛЬЗОВАТЬ ТАКОЙ ПРЕДИКАТ ДЛЯ ВЫВОДА СПИСКА, ПИСАТЬ ЕГО РУКАМИ!!!

ПРИМЕР 2
Подсчитать длину списка.

length(list, integer)
Есть почти во всех версиях пролога.
Если мы объявляем предикат с именем встроенного предиката, обычно предпочтение отдаётся нашему предикату.

Длиной списка называется:
0, если список пустой


domains
list = integer*

predicates
length(list, integer)

clauses
length([], 0) :- !.
length([_|T], X) :- length(T, Y), X = 1 + Y.

goal
length([1, 2, 3], X).

С хвостовой рекурсией:
domains
list = integer*

predicates
length(list, integer, integer)

clauses
length([], C, C) :- !.
length([_|T], C, R) :- NewC = C + 1, length(T, NewC, R).

goal
length([1, 2, 3], 0, R).

ПРИМЕР 2
Программа, которая меняет список. К каждому элементу списка L прибавляется 1.

domains
list = integer*

predicates
add1(list, list)

clauses
add1([], []) :- !.
add1([H|T], [H1|T1]) :- H1 = H + 1, add1(T, T1).

goal
add1([1,2,3], L1).
______________________________________________________