7 Списки

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

Рассмотрим пример:

[Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday]

[]-пустой список

listI = integer* /* список, элементы которого —

целые числа */

listR = real* /* список, состоящий из вещественных

чисел */

listC = char* /* список символов */

lists = string* /* список, состоящий из строк */

listL = listI* /* список, элементами которого являются

списки целых чисел */

Дадим рекурсивное определение списка.

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

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

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

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

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

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

length([_|T], L) :–

length(T, L_T), /* L_T — количество

элементов в хвосте */

L = L_T + 1. /* L — количество элементов

исходного списка */

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

member(X,[X|_]). /* X — первый элемент списка */

member(X,[_|T]) :–

member(X,T). /* X принадлежит хвосту T*/

GOAL

member(2, [1, 2, 3]).

Результат:

X=1

X=2

X=3

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

conc([ ], L, L). /* при присоединении пустого списка

к списку L получим список L */

conc([H|T], L, [H|T1]) :–

conc(T,L,T1). /* соединяем хвост и список L, получаем

хвост результата */

GOAL

сonc([1,2,3],[4,5],X)

Результат:

X= [1, 2, 3, 4, 5]

Пример. Разработаем предикат, позволяющий "обратить" список (записать его элементы в обратном порядке). Предикат будет иметь два аргумента: первый — исходный список, второй — список, получающийся в результате записи элементов первого аргумента в обратном порядке.

reverse([ ],[ ]). /* обращение пустого списка дает пустой

список*/

reverse([X|T],Z):–

reverse(T,S), conc(S,[X],Z).

/* обращаем хвост и приписываем к нему

справа первый элемент исходного

списка*/

Пример. Создадим предикат, который позволит проверить, является ли список палиндромом. Палиндромом называется список, который совпадает со своим обращением. Соответственно, у данного предиката будет всего один аргумент (список, который проверяем на "палиндромность").

palindrom(L):–

reverse (L,L).

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

n_element([X|_],1,X).

n_element([_|L],N,Y):–

N1=N–1,

n_element(L,N1,Y).

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

delete_all(_,[],[]).

delete_all(X,[X|L],L1):–

delete_all (X,L,L1).

delete_all (X,[Y|L],[Y|L1]):–

X<>Y,

delete_all (X,L,L1).