Лекции / 6
.pdf§. Списки и работа со списками.
Список – это специальный вид сложного терма, состоящий из последовательности связанных термов одного доменного типа, заключенных в квадратные скобки и разделенных запятой, например [1,2,-5,4,0]. Список в Прологе является односвязной структурой, то есть каждый элемент списка содержит только один (неявный) указатель на следующий элемент. При работе с такими списками выделяется первый элемент (называемый головой списка), а остальные элементы (составляющие хвост списка) можно получить, последовательно передвигаясь по указателям вплоть до последнего элемента. Хвост списка является таким же списком, как и исходный, поэтому обрабатывается аналогичным образом (рекурсивно).
Термами списка могут быть:
целые числа;
действительные числа;
символы;
символьные строки;
структуры.
Домен (тип) элементов списка необходимо определить в разделе domains:
domains
int_list = integer*
или
domains
int_list = int_value* int_value = integer
При необходимости можно ввести список списков: list_list = int_list*
Для отделения головы списка от хвоста используется символ |. Например, для списка [X| Y] X – голова списка, Y – хвост.
Операция 1. Вывод на экран списка введенных значений (например, [1,9,-2,5]). domains
number_list = integer* predicates print_list(number_list) clauses
print_list([ ]):- !. /* когда список исчерпан, ничего печатать не надо (отсечение) */ print_list([Head|Tail]):-write(Head),nl,print_list(Tail). /* печатаем голову, потом переводим на новую строку и рекурсивно вызываем предикат для печати хвоста списка*/
Операция 2. Определение количества элементов в списке.
domains
number_list = int_value* int_value = integer L_tail = integer
1
predicates length(number_list,int_value) clauses
length([], 0). /* в пустом списке 0 элементов /* length([_|T], L) :-length(T, L_tail),
L = L_tail + 1.
Символ нижнего подчеркивания здесь означает анонимную переменную, значение которой в данном предложении неважно.
Операция 3. Поиск элемента в списке.
domains
number_list = int_value* int_value = integer predicates
find_value(int_value,number_list)
Элемент находится в списке, если он либо является первым (головным) элементом списка, либо находится в остальной его части, то есть в хвосте. Эта логика записывается в виде двух предложений:
find_value(Head,[Head|_]). find_value(Head,[_|Tail]):-find_value(Head,Tail).
Операция 4. Объединение списков.
Создадим предикат, первые два аргумента которого будут объединяемыми списками, а третий аргументом будет результатом. Базис рекурсии – факт, что при присоединении пустого списка получается исходный список. Шаг рекурсии – правило, определяющее, что ко второму списку, нужно добавить хвост и второй список, а затем к результату приписать спереди первый элемент первого списка.
domains
number_list = int_value* int_value = integer predicates
merge(number_list,number_list,number_list) clauses
merge([ ], L, L).
merge([H|T], L, [H|T1]) :-merge(T,L,T1).
Этот код можно использовать для выполнения нескольких задач.
4.1. Слияние списков.
Goal: merge([1, 2, 3], [4, 5], X)
X= [1, 2, 3, 4, 5]
4.2. Проверка результата объединения списков.
Goal: merge([1, 2, 3], [4, 5], [1, 2, 4, 5]).
2
No
4.3. Разбиение списка на части.
Goal: merge([1, 2, 3], Y, [1, 2, 3, 4]).
X = [4]
Goal: merge(X, [4], [1, 2, 3, 4])
X = [1, 2, 3]
Возможны и более сложные запросы: Goal: merge(X, Y, [1, 2, 3, 4, 5])
X = [], Y = [1, 2, 3, 4, 5]
X = [1], Y = [2, 3, 4, 5]
X = [1, 2], Y = [3, 4, 5]
X = [1, 2, 3], Y = [4, 5]
X = [1, 2, 3, 4], Y = [5]
X = [1, 2, 3, 4, 5], Y = [] 6 Solutions
4.4. Поиск элементов левее и правее заданного значения.
Goal: merge(X, [3|Y], [1, 2, 3, -1, -2, 3, 5, 6, 3, 9]). X = [1, 2], Y = [-1, -2, 3, 5, 6, 3, 9]
X = [1, 2, 3, -1, -2], Y = [5, 6, 3, 9]
X = [1, 2, 3, -1, -2, 3, 5, 6], Y = [9] 3 Solutions
4.5. Определение последнего элемента списка.
domains
number_list = int_value* int_value = integer predicates
merge(number_list,number_list,number_list) last(number_list,int_value)
clauses
merge([ ], L, L).
merge([H|T], L, [H|T1]) :-merge(T,L,T1). last(L,X):-merge(_,[X],L).
4.6. Определение вхождения элемента в список.
Если элемент находится в списке, список может быть разбит на два подсписка так, что искомый элемент является головой второго подсписка.
domains
number_list = int_value* int_value = integer predicates
merge(number_list,number_list,number_list)
3
checkin(int_value,number_list) clauses
merge([ ], L, L).
merge([H|T], L, [H|T1]) :-merge(T,L,T1). checkin(X,L):-merge(_,[X|_],L).
4.7. Проверка, являются ли два значения соседями в списке.
domains
number_list = int_value* int_value = integer predicates
merge(number_list,number_list,number_list) sosedi(int_value,int_value,number_list) sosedianyorder(int_value,int_value,number_list) clauses
merge([ ], L, L).
merge([H|T], L, [H|T1]) :-merge(T,L,T1). sosedi(X,Y,L):-merge(_,[X,Y|_],L). sosedianyorder(X,Y,L):-merge(_,[X,Y|_],L);merge(_,[Y,X|_],L).
Операция 5. Получение элемента с заданным номером.
Вначале запишем тот факт, что элемент списка с номером 1 – это его голова.
Правило определения элемента будет исходить из того, что номер элемента в списке на единицу меньше номера этого элемента в хвосте списка.
domains
number_list = int_value* int_value = integer predicates
get_element(number_list,int_value,int_value) clauses
get_element([X|_],1,X).
get_element([_|L],N,Y):- N1=N-1, get_element(L,N1,Y).
Операция 6. Сумма элементов списка
Вначале запишем тот факт, что сумма элементов пустого списка равна нулю. Правило будет прибавлять голову списка к сумме хвоста.
domains
number_list = int_value* int_value = integer predicates sum(number_list,int_value) clauses
sum([], 0).
sum([H|T], S) :- sum(T, S1), S = S1 + H.
4
Операция 7. Удаление элемента из списка
Вначале записываем тот факт, что в результате удаления из пустого списка получается пустой список. Если удаляемый элемент находится в голове списка, то результатом является список, получаемый дальнейшим удалением элементов из хвоста, иначе голову надо переписать, а к хвосту применить рекурсивный вызов.
domains
number_list = int_value* int_value = integer predicates
delete_all(int_value,number_list,number_list) clauses
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).
Если в первом правиле заменить рекурсивный вызов предиката отсечением, будет удалено только первое вхождение.
delete_one(_,[],[]). delete_one(X,[X|L],L):–!.
delete_one(X,[Y|L],[Y|L1]):–delete_one(X,L,L1).
Операция 8. Определение максимального и минимального элементов списка.
Вначале необходимо определить два предиката max(X,Y,X):- X >= Y.
max(X,Y,Y):- X < Y. min(X,Y,X):- X < Y. min(X,Y,Y):- X >= Y.
Базис – факт, что для списка из одного элемента этот элемент является и максимальным, и минимальным. Затем правило будет сравнивать голову списка и максимальный элемент хвоста, и выбирать из них наибольший или наименьший.
domains
number_list = int_value* int_value = integer predicates
max(int_value,int_value,int_value) min(int_value,int_value,int_value) max_list(number_list,int_value) min_list(number_list,int_value) clauses
max(X,Y,X):- X >= Y. max(X,Y,Y):- X < Y. min(X,Y,X):- X < Y. min(X,Y,Y):- X >= Y. max_list([X],X).
max_list([H|T],M):- max_list(T,M_T), max(H,M_T,M). min_list([X],X).
min_list([H|T],M):-min_list(T,M_T), min(H,M_T,M).
5