В Прологе списки напоминают рекурсию, где мы имеем доступ к головному элемнту, и остальной части списка [Head | Tail] (грубо говоря первый элемент и указатель на остальные). Сам список мы не можем изменять, а лишь вернуть новый (возможно состоящий из частей старого).
Наиболее похожей структурой на списки Пролога — явлется связный (односвязный) список, где у каждого элемента хранится информация о элементе идущим за ним. В этой структуре данных также нельзя получать элементы по идексу (без вспомогательных конструкций), однако можно изменять элементы и менять у них связи. Также некоторая схожесть есть со стеком, где элементы так же идут друг за другом.
insert(Element, List, Position, Resulting_List) - Вставляет элемент Element в позицию Position исходного списка List, результат записывается в новый список Resulting_List.
Примеры использования:
?- insert(5, [1,2,3,4], 5, X).
X = [1, 2, 3, 4, 5] .
?- insert(1, [], 1, X).
X = [1] .
?- insert(X, [1, 2, 3], 4, [1,2,3,4]).
X = 4 .Реализация 1 (Основная рекурсия в нашей функции):
% Если позиция равна 1, вставляем элемент в начало списка
insert(Element, List, 1, [Element | List]).
% Если позиция не равна 1, рекурсивно сдвигаемся к началу списка
% и доходим до случая, когда позиция = 1
insert(Element, [Head | Tail], Position, [Head | NewTail]) :-
Position > 1,
NewPosition is Position - 1,
insert(Element, Tail, NewPosition, NewTail).В данной реализации мы идём от общего случая (Position = 1) - к частному (Position == 1). Для позиции = 1, нам остаётся добавить элемент в начало списка. Для остальных же рекурсивно переходим в эту функцию с исходным списком без первого элемента, пока не дойдём до позиции = 1.
Реализация 2 (Рекурсия уходит в стандартные):
% Реализация с использованием стандартных предикатов
insert2(Element, List, Pos, Result) :-
Pos > 0, NewPos is Pos - 1,
append(Prefix, Suffix, List), length(Prefix, NewPos),
append(Prefix, [Element | Suffix], Result).В данной реализации мы берём список Prefix, такой что он является префиксом исходного, и второй Suffix, являющийся суффиксом, что они вместе дают исходный список. Затем остаётся вставить наш элемент между двумя этими списками.
Можно использовать реализованный мной предикат insert с базовым length для того чтобы вставить элемент и узнать длину нового списка, или, например с предикатом permute, чтобы узнать перестановки с новым элементом и остальными из списка.
search_minus(List, Result) - Вычисление позиции Result первого отрицательного элемента в списке List.
Примеры использования:
?- search_minus([1,2,3,4,5], R).
false.
?- search_minus([-1,-1,-1], R).
R = 1 .
?- search_minus([1,2,-1,-1], R).
R = 3 .Реализация 1 (Основная рекурсия в нашей функции):
search_minus(List, Result) :- search_minus(List, 1, Result).
search_minus([Head | _], Position, Result) :-
Head < 0,
Result is Position.
search_minus([Head | Rest], Position, Result) :-
Head >= 0,
NewPos is Position + 1,
search_minus(Rest, NewPos, Result).
В данной реализации мы идём по всему списку рекурсивно пока элементы положительные, запоминая позицию. Как только встречаем отрицательный элемент записываем позицию в результат.
Реализация 2 (Рекурсия уходит в стандартные):
without_minus([], []).
without_minus([Head | Tail], Tail) :- Head < 0.
without_minus([Head | Tail], R) :-
Head >= 0,
without_minus(Tail, R_left),
append([Head], R_left, R).
search_minus_2(List, R) :-
without_minus(List, Without_m),
find_diff(List, Without_m, R, 1).
% Поиск первого отличающегося элемента из двух списков.
find_diff([], [], _, _) :- !, fail.
find_diff([_|_], [], Result, Pos) :- Result is Pos, !.
find_diff([Head1 | Tail1], [Head1 | Tail2], Result, Pos) :-
NewPos is Pos + 1,
find_diff(Tail1, Tail2, Result, NewPos).
find_diff([Head1 | _], [Head2 | _], Result, Pos) :- Head1 \= Head2, Result is Pos, !.Здесь программа делится на 2 этапа. Первый с помощью стандартных предикатов собираем новый список из исходного, где исключаются все отрицательные элементы. Во втором мы обходим вместе исходный список и изменнённый, и когда находим различие, сохраняем позицию.
Преимущества реляционного хранения данных в Прологе удобно простотой задания довольно сложных связей, удобством дальнейшего использования, легкость добавления нового элемента. Однако есть и минусы: сложность добавления новых параметров (В моём представлении grade (two.pl), для того чтобы например добавить номер телефона, придётся изменить все факты в каждый добавив его), неудобность представления (Нет графического представления, например таблиц).
Также в представлении (two.pl), единицей является оценка по предменту grade, что добавлет громоздкости, так как для каждой фамилии приходится несколько различных оценок. Так же при возможны колизии, ведь нельзя будет определить принадлежность оценки при совпадении фамилий.
get_averenge_marks() - Выводит все средние оценки по каждому предмету.
Примеры использования:
?- get_averenge_marks().
Averange for Английский язык is : 3.75
Averange for Информатика is : 3.9285714285714284
Averange for Логическое программирование is : 3.9642857142857144
Averange for Математический анализ is : 3.892857142857143
Averange for Психология is : 3.9285714285714284
Averange for Функциональное программирование is : 3.9642857142857144
Реализация:
% список предметов
get_subj_list(R) :- findall(Subj, grade(_, _, Subj, _), Subjs), sort(Subjs, R).
% сумма списка
sum_list_s([], 0).
sum_list_s([Head|Tail], Sum) :- sum_list(Tail, TailSum), Sum is Head + TailSum.
% ср. оценка на предмет
get_averenge_mark(Subj, Result) :-
findall(Mark, grade(_, _, Subj, Mark), Marks),
sum_list_s(Marks, Sum),
length(Marks, Num),
Result is Sum / Num.
% вспомогательная функиция
get_averenge_marks() :-
get_subj_list(R),
get_averenge_marks(R).
get_average_marks([]).
% рекурсивно идём по всем предметам
get_averenge_marks([Head | Tail]) :-
get_averenge_mark(Head, Mark),
write("Averange for "), write(Head), write(" is : "), write(Mark), nl,
get_averenge_marks(Tail).
% get_averenge_marks(). - получает все средние оценки по каждому предметуСначала получаем список уникальных предметов, затем идя по каждомому для него получаем среднюю оценку (get_averenge_mark). Затем выводим значения на консоль.
get_bad_for_groups() - Выводит колличество несдавших в каждой группе
Примеры использования:
?- get_bad_for_groups().
Count bad for group 101 is : 2
Count bad for group 102 is : 5
Count bad for group 103 is : 3
Count bad for group 104 is : 2
Реализация:
% Получаем список всех групп
get_group_list(R) :- findall(Group, grade(Group, _, _, _), Groups), sort(Groups, R).
% сколько 2ек людей в группе
get_bad_for_group(Group, Result) :-
findall(X, grade(Group, X, _, 2), People), sort(People, PeopleList),
length(PeopleList, Num),
Result is Num.
% вспомогательная
get_bad_for_groups :-
get_group_list(Groups),
get_bad_for_groups(Groups).
get_bad_for_groups([]).
% идём рекурсивно по всем группам
get_bad_for_groups([Head | Tail]) :-
get_bad_for_group(Head, Mark),
write("Count bad for group "), write(Head), write(" is : "), write(Mark), nl,
get_bad_for_groups(Tail).Сначала получаем список уникальных групп, затем идя по каждой, смотрим на кол-во уникальных студентов с двойкой (get_bad_for_group), выводим значения на консоль.
get_bad_for_subj() - Выводит колличество несдавших каждый предмет
Примеры использования:
?- get_bad_for_subj().
Count bad for subject Английский язык is : 4
Count bad for subject Информатика is : 2
Count bad for subject Логическое программирование is : 2
Count bad for subject Математический анализ is : 3
Count bad for subject Психология is : 1
Count bad for subject Функциональное программирование is : 1
Реализация:
% все с двойкой по этому предмету
get_bad_for_subj(Subj, Result) :-
findall(X, grade(_, X, Subj, 2), People), sort(People, PeopleList),
length(PeopleList, Num),
Result is Num.
% вспомогательная
get_bad_for_subj :-
get_subj_list(Subjects),
get_bad_for_subj(Subjects).
get_bad_for_subj([]).
% идём рекурсивно по предметам
get_bad_for_subj([Head | Tail]) :-
get_bad_for_subj(Head, Cnt),
write("Count bad for subject "), write(Head), write(" is : "), write(Cnt), nl,
get_bad_for_subj(Tail).
Сначала получаем список уникальных предметов, затем идя по каждмому для него получаем кол-во людей с 2 (get_bad_for_subj). И выводим значения на консоль.
Данная лабораторная работа помогла мне поближе познакомится со списками в Прологе, провести аналогию их с другими языками. Благодаря ей я вспомнил, что в Прологе можно получать не только результат, но и аргументы, которые привели к этому результату, что является для меня новинкой, относительно императивных языков. Узнал, что можно свести некоторые задачи, к базовым (как добавление элемента, длина элемента). Вспомнил о рекурсии и её многофункциональности. Познакомился с новым видом представления данных - фактов Пролога, и научился пользоваться ими, для решения задач. Вспомнил о проблемах с кодировкой :) .
Данная работа будучи практической, помогла овладеть новыми навыками программирования, например при решении второй задачи я довольно долго думал и пытался свести прошлый опыт программирования к Прологу. Это поможет мне в выполнении дальнейших лабораторных работ, а также я надеюсь что это поможет лучше понимать сложные алгоритмы на императивных языках, исходя из опыта на Прологе.
Благодаря данной работе у меня появился больший интерес к програмированию на Прологе, как на уникальном языке, так как при его использовании часто приходится задумываться о ещё недавних тривиальных вещах, как о чём-то новом, что открывает мышление под другим углом.