Domains. element = i(integer); c(char); s(string)

element = i(integer); c(char); s(string)

listE = element*

Такое описание списка позволит иметь дело со списками вида:

[ i(–15), s("Мама"), c('A'), s("мыла"), c('+'), s("раму"), i(48), c('!') ]

Рекурсивное определение списка: список — это структура данных, определяемая следующим образом:

- пустой список ([ ]) является списком;

- структура вида [H|T] является списком, если H — первый элемент списка (или несколько первых элементов списка, перечисленных через запятую), а T — список, состоящий из оставшихся элементов исходного списка.

Принято называть Hголовой списка, а T — хвостом списка. Фактически операция " | " позволяет разделить список на хвост и голову или, наоборот, присоединить объект (объекты) к началу списка.

Данное определение позволяет организовывать рекурсивную обработку списков, разделяя непустой список на голову и хвост. Хвост, в свою очередь, также является списком, содержащим меньшее количество элементов, чем исходный список. Например, в списке [1, 2, 3] элемент 1 является головой, а список [2, 3] — хвостом, т.е. [1, 2, 3] = [ 1 | [2, 3] ].

В этом же списке можно выделить два первых элемента и хвост из третьего элемента [1,2 | [3] ]. И, наконец, возможен вариант разбиения на голову из трех первых элементов и пустой хвост : [1, 2, 3 | [] ].

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

Пример. Создать предикат, позволяющий вычислить длину списка, т.е. количество элементов в списке.

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

length([ ], 0). /* в пустом списке элементов нет */

length([_|T], L):– length(T, L_T), L = L_T + 1.

/* L_T — кол-во элементов в хвосте */

/* L — кол-во элементов исх. списка */

Соответствующий запрос может быть таким:

Goal: length([1,2,3], X).

Ввод и вывод списка

Ввод списка осуществляется с помощью предиката readterm(<тип списка>, Х). Для выводасписка используется оператор write(Х), при этом список Х рассматривается как один терм

Пример 1. Организовать ввод списка из целых чисел.

Domains

list=integer*

Goal

write("Введите список "), readterm(list,X), nl,

write("список L = "), write(X), nl.

Пример 2: Организовать поэлементный ввод списка.

Domains

list=integer*

Predicates

Readlist(list)

Goal

write("Введите список "), readlist(L),nl,

write("список L = ",L).