Подразделы

Другие разделы

Дата и время

20/04/2024 19:08:12

Авторизация

Логическое программирование

Логическое программирование и язык Пролог Синтаксис. Операторы. Списки Сопоставление Арифметические и логические выражения Семантика программы на языке Пролог Списки. Обработка списков Предикаты для классификации и обработки термов Предикаты для управления процессом доказательства Предикаты для ввода и вывода данных Предикаты для работы с утверждениями Предикаты порождения Отладка программ на языке Пролог Примеры программ на языке Пролог Логика предикатов. Метод резолюции Верификация программ: основные обозначения и термины Правильность алгоритмов и способ верификации программ Синтез программ

Списки. Обработка списков

Рассмотрим реализацию нескольких полезных предикатов для обработки списков. Эти предикаты являются встроенными или их можно подключить с помощью команды

:- use_module(library(lists)).

Хотя их не нужно определять явно в своей программе, знание их определений полезно при написании аналогичных предикатов. Определения предикатов для обработки списков обычно являются рекурсивными и состоят из двух предложений. Первое предложение определяет логические связи между аргументами предиката в тривиальном случае, задает условие окончания рекурсии. Если существует несколько случаев, то таких предложений может быть несколько. Второе предложение задает логические связи между результатом для всего списка, головой списка и результатом, полученного в ходе рекурсивного применения предиката к хвосту списка. Например, программа для предиката принадлежности может быть основана на правиле "X является элементом списка L, если X является головой списка L, либо X является элементом хвоста списка L".

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

Можно рассмотреть также случай с пустым списком

member(X,[]):-fail.

но отсутствие этого предложения также приводит к неудаче.

Кроме проверки принадлежности

?-member(b,[a,b,c]).
yes

этот предикат может использоваться для получения элементов из списка, если первым аргументом будет неконкретизированная переменная:

?-member(X,[a,b,c]).
X=a;
X=b;
X=c;
no

Предикат append/3 является истинным, если его третий аргумент является списком, полученным в результате сцепления списков, заданных в первом и втором аргументе. Существуют два тривиальных случая:

append([],L,L).
append(L,[],L). % можно не рассматривать

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

append([H|L1],L2,[H|L3]):-append(L1,L2,L3).

Предикат append можно использовать для проверки и сцепления:

?-append([a,b],[c,d],[a,b,c,d]).
yes
?-append([a,b],[c,d],R).
R=[a,b,c,d]

для разделения заданного списка на две части, одна из которых известна:

?-append(X,[c,d],[a,b,c,d]).
X=[a,b]
?-append([a,b],X,[a,b,c,d]).
X=[c,d]

и для получения всех вариантов расщепления списка:

?-append(X,Y,[a,b,c]).
X=[], Y=[a,b,c];
X=[a], Y=[b,c];
X=[a,b], Y=[c];
X=[a,b,c], Y=[];
no

Можно определить предикат принадлежности, используя предикат append для разделения списка.

принадлежит(X,L):-append(_,[X|_],L).

Для добавления элемента X в конец списка L можно использовать предикат append(L,[X],L1). Добавление элемента X в начало списка L является элементарной операцией: L1=[X|L]. Для удаления элемента из списка потребуется определить предикат.

select(X,[X|L],L).
select(X,[H|T],[H|L]):-select(X,T,L).

Предикат select можно использовать для удаления элемента

?-select(b,[a,b,c],R).
R=[a,c]

для проверки принадлежности:

?-select(b,[a,b,c],_).
yes

для получения всех вариантов удаления:

?-select(X,[a,b,c],L).
X=a, L=[b,c];
X=b, L=[a,c];
X=c, L=[a,b];
no

и, наоборот, для получения всех вариантов вставки элемента в список:

?-select(d,R,[a,b,c]).
R=[d,a,b,c];
R=[a,d,b,c];
R=[a,b,d,c];
R=[a,b,c,d];
no

Последнюю возможность предиката select можно использовать для получения всех перестановок.

перестановка([],[]).
перестановка([H|T],R):-перестановка(T,L),select(H,R,L).

?-перестановка([a,b,c],R).
R=[a,b,c];
R=[b,a,c];
R=[b,c,a];
R=[a,c,b];
R=[c,a,b];
R=[c,b,a];
no

Предикат для обращения списка можно определить так:

reverse([],[]).
reverse([H|T],R):-reverse(T,L),append(L,[X],R).

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

reverse(L,R):-reverse(L,[],R).
reverse([],R,R).
reverse([H|T],L,R):-reverse(T,[H|L],R).

Упражнения

Напишите определения следующих предикатов.

1) длина(X,L), где число L – это количество элементов в списке X.

2) множество(X), где список X не содержит одинаковых элементов (является множеством).

3) подмножество(A,B), где множество A является подмножеством множества B.

4) пересечение(A,B,C), где множество C является пересечением множеств A и B.

5) объединение(A,B,C), где множество C является объединением множеств A и B.

6) разность(A,B,C), где множество C является разностью множеств A и B.

7) упорядочен(X), где список чисел X является упорядоченным по возрастанию.

8) слияние(X,Y,Z), где список Z образуется в результате слияния двух упорядоченных по возрастанию списков чисел X и Y.

9) вставка(X,L,R), где упорядоченный по возрастанию список R образуется в результате вставки числа X в список чисел L, который является упорядоченным по возрастанию.

10) сортировать(L,R), где список R образуется в результате сортировки списка чисел L. Использовать следующий алгоритм: сначала отсортировать хвост списка, затем вставить голову в отсортированный хвост.

11) подсписок(X,Y), где список X является подсписком (непрерывной подпоследовательностью) списка Y.

12) максимум(M,L), где число M является максимальным элементом списка чисел L.

13) элемент(X,N,L), где X является N-м элементом списка L.

14) подсписок(R,N,M,L), где список R является подсписком списка L длиной M, начиная с N-го элемента.

15) палиндром(X), где список X читается одинаково слева направо и справа налево.

?-палиндром("аргентинаманитнегра").
yes

16) сумма(L,S), где число S является суммой элементов списка чисел L.

17) количество(X,L,K), где число K – это количество элементов, равных X в списке L.