Некоторые операции над списками

Среди множества операций (действий) над списками рассмотрим наиболее важные.

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

Требуется определить предикат: member(X, List). Здесь List – произвольный список, X – объект того же типа, что и элементы списка List. Составление предиката основывается на следующих соображениях: X есть либо голова списка List, либо X принадлежит хвосту. Это может быть записано с помощью двух предложений, первое из которых есть простой факт (граничное условие или условие выхода из рекурсии), а второе – рекурсивное правило:

member(X, [X|_]).

member(X, [_|Tail]): -member(X, Tail).

Знаком подчеркивания здесь обозначена анонимная переменная, значение которой в данном предложении не существенно.

Работу предиката можно объяснить следующим образом: при каждом рекурсивном вызове список будет короче, так.как. аргументом заголовка является структура [_, Tail], а в рекурсивном вызове – список Tail. Рекурсивные вызовы продолжаются до тех пор, пока искомый элемент X не совпадет с «очередной» головой списка Tail, или список не окажется пустым. В этом случае предикат завершится ложно, поскольку для пустого списка нет своего правила.

Чаще всего этот предикат используют в двух случаях:

1. Переменная X не конкретизирована, а список List – конкретизирован. В этом случае в результате работы предиката переменная X конкретизируется значением элемента списка List. Используя механизм возвратов переменной X можно придать значения всех элементов списка List.

2. Переменная X и список List – конкретизированы. Значением предиката будет истина, если X совпадает с одним из элементов списка List, т. е. принадлежит этому списку. Если совпадений не обнаружено, предикат завершится ложью.

Сцепление (конкатенация, объединение) списков

Предикат для объединения двух списков определяется отношением conc(L1, L2, L3), где L1 и L2 – объединяемые списки, а L3 – результат. Графически объединение двух списков представлено на рис. 2. Следует отметить, что голова первого списка становится головой результирующего списка.

H1	L1
H2	L2
H1	L3

Рис. 2. Объединение двух списков

Для определения отношения выделим два случая:

1) если первый список пуст, то второй и третий список представляет один и тот же список, т. е.

conc([], L, L);

2) если первый аргумент не пуст, то он имеет голову и хвост, т. е. [H1|L1]. Его сцепление со вторым списком – список [H1|L], где список T получен после сцепления L1 и L2, т. е.

conc([H1|L1], L2, [H1, L]): -conc(L1, L2, L3).

Пример использования этого предиката в среде Strawberry Prolog:

conc([], L, L).

conc([H1|T1], L2, [H1|T]): - conc(T1, L2, T ).

? -conc([a, s, d], [q, w, e], X), write(X), nl.

Compiling the file:

C: \VIP\VPI\EXAMPLES\and_\and_

0 errors, 0 warnings.

[a, s, d, q, w, e]

Yes.

Этот же предикат можно использовать в противоположном «направлении», т. е. не для объединения, а разъединения списка, как это показано в следующем фрагменте:

conc([], L, L).

conc([H1|T1], L2, [H1|T]): - conc(T1, L2, T ).

? -conc([a, s, d], X, [a, s, d, e, r, t]), write(X), nl.

Выполите этот фрагмент и оцените ответ Пролог-системы.

Добавление элемента в список

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

add(X, L, [X|L]).

Удаление элемента из списка

Удаление элемента X из списка L можно определить в виде отношения away(X, L, L1), где L1 – это список L, из которого удалили X. Отношение строится на том соображении, что если X – голова списка, то результат отношения – хвост списка. Если X не голова списка, то его необходимо удалить из хвоста.

away(X, [X|T], T).

away(X, [Y|T], [Y|T1]): -away(X, T, T1).

Индивидуальные задания. Выполнить следующие индивидуальные задания согласно варианту.

1. Создайте предикат, заменяющий в исходном списке первое вхождение заданного элемента другим. Создайте предикат, заменяющий в исходном списке все вхождения заданного элемента другим.

2. Создайте предикат, порождающий по заданному натуральному числу N список, состоящий из натуральных чисел от 1 до N (по возрастанию). Создайте предикат, порождающий по заданному натуральному числу N список, состоящий из натуральных чисел от N до 1 (по убыванию).

3. Создайте предикат, порождающий по заданному натуральному числу N список, состоящий из N случайных чисел от 1 до 100. Создайте предикат, порождающий по заданным числам N, M, K список, состоящий из N натуральных чисел из промежутка от M до К

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

5. Создайте предикат, который увеличивает элементы числового списка на единицу. Создайте предикат, переводящий список цифр от 0 до 9 в список соответствующих им названий (строк).

6. Создайте предикат, переводящий список чисел в список соответствующих им названий. Создайте предикат, переводящий список чисел от 0 до 9 в список соответствующих им римских чисел.

7. Создайте предикат, переводящий список арабских чисел в список соответствующих им римских чисел. Создайте предикат, переводящий список римских чисел в список соответствующих им арабских чисел.

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

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

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

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

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

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

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

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

16. Создайте предикат, осуществляющий циклический сдвиг элементов влево (вправо). Создайте предикат, осуществляющий циклический сдвиг элементов списка на заданное количество шагов.

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

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

19. Создайте предикат, определяющий первую позицию подсписка в списке. Создайте предикат, возвращающий по списку и двум числам M и N подсписок исходного списка, состоящий из элементов с номерами от M до N.

Контрольные вопросы

1. Список, голова и хвост списка.

2. Что может выступать в качестве элемента списка.

3. Что может выступать в качестве головы списка?

4. Что может выступать в качестве хвоста списка?

5. Основные операции над списками.

Лабораторная работа 3

⇐ Предыдущая 123 4 5 6 Следующая ⇒