Списки на Прологе. Лекция № 5

1. Списки на Прологе

Лекция № 5

2. Описание

[monday, tuesday, wednesday, thursday, friday, saturday, sunday]
["понедельник", "вторник", "среда", "четверг", "пятница", "суббота",
"воскресенье"]
[1, 2, 3, 4, 5, 6, 7]
['п', 'в', 'с', 'ч', 'п', 'с', 'в']
[]
DOMAINS
<имя спискового домена>=<имя домена элементов списка>*
listI = integer*
listR = real*
listC = char*
listS = string*
listL = listI*
/*[[1,3,7],[],[5,2,94],[–5,13]]*/

3. Описание

[monday, 1, "понедельник"]
DOMAINS
element = i(integer); c(char); s(string)
listE = element*
[i(–15), s("Мама"),c('A'),s("мыла"),c('+'),s("раму"),
i(48),c('!')]

4. Определение списка

Пустой список ([]) является списком
Структура вида ([H|T]) является списком,
если Н – первый элемент списка (или
несколько первых элементов,
перечисленных через запятую), а Т –
список из оставшихся элементов
исходного списка.
У пустого списка нет головы!

5. Рекурсивное описание списка

[1, 2, 3] = [1|[2, 3]]
= [1|[2|[3]]]
= [1|[2|[3|[ ]]]]
= [1,2|[3]]
= [1, 2, 3|[]]
= [1|[2,3|[]]

6. Вычисление длины списка

length([], 0).
length([_|T], L) :–
length(T, L_T),
L = L_T + 1.
Цель:
length([1,2,3],X).
Первый аргумент:
список.
Второй аргумент:
длина списка.
L_T – количество
элементов в
хвосте
L – количестве
элементов
исходного списка

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

member(X,[X|_]).
member(X,[_|T]) :–
member(X,T).
member2(X,[X|_]).
member2(X,[Y|T]):–
X<>Y, member2(X,T).
member3(X,[X|_]):–!.
member3(X,[_|T]):–
member3(X,T).
member(2, [1, 2, 3]).
member(4, [1, 2, 3]).
member(X, [1, 2, 3]).
member(1, X).
Первый аргумент:
элемент, который
требуется найти.
Второй аргумент:
список.

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

conc([ ], L, L).
conc([H|T], L, [H|T1]) :–
conc(T,L,T1).
conc([1, 2, 3], [4, 5], X)
conc([1, 2, 3], [4, 5], [1, 2, 5])
conc([1, 2], Y, [1, 2, 3])
conc(X, [3], [1, 2, 3])
conc(X, Y, [1, 2, 3])
conc(L, [2|R], [1, 2, 3, 2, 4])
Первый аргумент:
первый список.
Второй аргумент:
второй список.
Третий аргумент:
результирующий
список
Чтобы приписать
элементы списка,
состоящего из
головы и хвоста, ко
второму списку,
нужно соединить
хвост и второй
список, а затем к
результату
приписать спереди
голову первого
списка

9. Варианты использования предиката conc

last(L,X):–
conc(_,[X],L).
Первый аргумент:
список.
Второй аргумент:
искомый
последний
элемент.
last2([X],X).
last2([_|L],X):–
last2(L,X).
member4(X,L):–
conc(_,[X|_],L).
Первый аргумент:
элемент, который
требуется найти.
Второй аргумент:
список.

10. Соседние элементы списка

neighbours(X,Y,L):–
conc(_,[X,Y|_],L).
neighbours2(X,Y,L):–
conc(_,[X,Y|_],L);
conc(_,[Y,X|_],L).
Первый аргумент:
первый элементсосед.
Второй аргумент:
второй элементсосед.
Третий аргумент:
список.

11. Обращение списка

reverse([ ],[ ]).
reverse([X|T],Z):–
reverse(T,S), conc(S,[X],Z).
rev([H|T],L1,L2):–
rev(T,[H|L1],L2).
rev([ ],L,L).
reverse2(L1,L2):–
rev (L1,[ ],L2).
palindrom(L):–
reverse (L,L).
Первый аргумент:
исходный список.
Второй аргумент:
перевернутый
список.

12. Получение элемента списка по его номеру

n_element([X|_],1,X).
n_element([_|L],N,Y):–
N1=N–1,
n_element(L,N1,Y).
Базис: элемент с номером
1 – это голова списка
Шаг: элемент с номером N
является N-1-ым
элементом хвоста
Первый аргумент:
исходный список.
Второй аргумент:
номер искомого
элемента.
Третий аргумент:
искомый элемент.

13. Удаление всех вхождений заданного значения из списка

Из пустого списка нельзя
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).
Первый аргумент:
элемент, который
нужно удалить.
Второй аргумент:
исходный список.
Третий аргумент:
результирующий
список.

14. Удаление первого вхождения

delete_one(_,[],[]).
delete_one(X,[X|L],L):–!.
delete_one(X,[Y|L],[Y|L1]):–
delete_one(X,L,L1).

15. Сумма элементов списка

summa([], 0). /* сумма элементов пустого
списка равна нулю */
summa([H|T], S) :–
summa(T, S_T), /* S_T - сумма элементов хвоста */
S = S_T + H. /* S - сумма элементов исходного списка */

16. Сумма элементов списка

sum_list([],S,S). /* список стал пустым, значит в накопителе –
сумма элементов списка */
sum_list([H|T],N,S) :–
N_T=H+N, /* N_T - результат добавления к сумме,
находящейся в накопителе, первого элемента
списка */
sum_list(T,N_T,S). /* вызываем предикат от хвоста T и
N_T */
sum2(L,S):–
Первый аргумент:
список
sum_list(L,0,S).
Второй аргумент:
накопитель
Третий аргумент:
конечная сумма

17. Среднее арифметическое элементов списка

avg([],0):–!.
avg(L,A):–
summa(L,S), /* помещаем в переменную S сумму
элементов списка */
length(L,K), /* переменная K равна количеству
элементов списка */
A=S/K. /* вычисляем среднее как отношение суммы
к количеству */

18. Минимальный элемент списка

Первый аргумент:
min_list([X],X).
список
Второй аргумент:
min_list([H|T],M):–
минимальный
элемент
min_list(T,M_T),
Сначала делаем
min(H,M_T,M).
минимальным последний
элемент списка.
На возврате сравниваем его
с каждой головой, которую
отсекали от списка.

19. Сортировка: метод прямого обмена (пузырьковая)

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

20. Сортировка: метод прямого обмена (пузырьком)

Если первый элемент
permutation([X,Y|T],[Y,X|T]):–
больше второго, то меняем
X>Y,!.
их местами
В противном случае
permutation([X|T],[X|T1]):–
вызываем рекурсию для
permutation(T,T1). хвоста.
bubble(L,L1):–
permutation(L,LL), Делаем один обменный
проход по списку
!,
Вызываем рекурсию для
полученного списка
bubble(LL,L1).
bubble(L,L). Если не было перестановок
Первый аргумент:
(permutation был ложен), то
список отсортирован
исходный список
Второй аргумент:
отсортированный список

21. Сортировка вставкой

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

22. Сортировка вставкой

ins_sort([ ],[ ]).
Пустой список отсортирован
ins_sort([H|T],L):–
Иначе: отсортировать хвост, потом
ins_sort(T,T_Sort), вставить отделенную голову к
отсортированному хвосту
insert(H,T_Sort,L).
insert(X,[],[X]).
insert вставляет элемент в
нужное место в
insert(X,[H|T],[H|T1]):–
отсортированном хвосте
X>H,!,
списка, что не нарушить
сортировку
insert(X,T,T1).
Первый аргумент: элемент
insert(X,T,[X|T]).
Второй аргумент:
отсортированный хвост
Третий аргумент: результат

23. Сортировка выбором

Основная идея:
В списке находим минимальный элемент.
Удаляем его из списка. Оставшийся список
сортируем. Приписываем минимальный элемент
в качестве головы к отсортированному списку.
Так как этот элемент был меньше всех элементов
исходного списка, он будет меньше всех
элементов отсортированного списка. И,
следовательно, если его поместить в голову
отсортированного списка, то порядок не
нарушится.

24. Сортировка выбором

choice([ ],[ ]).
choice(L,[X|T]):–
min_list(L,X),
delete_one(X,L,L1),
choice(L1,T).

25. Быстрая сортировка (Хоара)

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

26. Используемый предикат

partition – разбиение списка на два
подсписка. Аргументы:
Исходный список
Барьерный элемент
Список элементов исходного списка, которые
меньше барьерного
Список, состоящий из элементов, которые не
меньше барьерного элемента

27. Быстрая сортировка

quick_sort([],[]).
quick_sort([H|T],O):–
partition(T,H,L,G),
quick_sort(L,L_s),
quick_sort(G,G_s),
conc(L_s,[H|G_s],O).
partition([],_,[],[]).
partition([X|T],Y,[X|T1],T2):–
X<Y,!,
partition(T,Y,T1,T2).
partition([X|T],Y,T1,[X|T2]):–
partition(T,Y,T1,T2).

28. Объединение отсортированных списков

fusion(L1,[ ],L1):–!.
fusion([ ],L2,L2):–!.
fusion([H1|T1],[H2|T2],[H1|T]):–
H1<H2,!,
Сливаем хвост
со вторым
fusion(T1, [H2|T2],T). первого
списком
fusion(L1, [H2|T2],[H2|T]):–
Сливаем первый
fusion(L1,T2,T).
список с хвостом
второго списка

29. Сортировка слияниями

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

30. Сортировка слияниями

splitting([],[],[]).
splitting([H],[H],[]).
splitting([H1,H2|T],[H1|T1],[H2|T2]):–
splitting(T,T1,T2).
fusion_sort([],[]):–!.
fusion_sort([H],[H]):–!.
fusion_sort(L,L_s):–
splitting(L,L1,L2),
fusion_sort(L1,L1_s),
fusion_sort(L2,L2_s),
fusion(L1_s,L2_s,L_s).
Пустой список можно
разбить только на два
пустых подсписка
Список из одного элемента
разбивается на подсписок из
одного элемента и пустого
подсписка
Иначе: отсекаем два первых
элемента, вызываем
разбиение для хвоста, затем
добавляем отсеченные
элементы (один – в один
подсписок, другой – в другой
подсписок)

31. Проверка упорядоченности списка

sorted([ ]).
sorted([_]).
sorted([X,Y|T]):–
X<=Y,
sorted([Y|T]).