Списки. Предикаты высших порядков

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

Для моделирования множеств часто используются списки. В них хранятся элементы множества (списки не должны содержать повторяющиеся элементы). В следующей программе список разбивается всеми возможными способами на подмножество, состоящее из заданного количества элементов (сочетание), и подмножество оставшихся элементов.

class predicates
    subset: (positive, A*, A*  Subset [out], A* Rest [out]) nondeterm.
clauses
    subset(0, L, [], L):- !.
    subset(N, [A | L], [A | L1], L2):-
        subset(N - 1, L, L1, L2).
    subset(N, [A | L], L1, [A | L2]):-
        subset(N, L, L1, L2).

    run():-
        subset(2, [1, 2, 3, 4, 5], L1, L2),
            write(L1, " - ", L2), nl,
        fail;
        _ = readLine().

Упражнение 1. Сгенерируйте все подмножества элементов списка.

В приведенной ниже программе недетерминированно генерируются перестановки элементов списка. Если список содержит n элементов, то возвращается n! перестановок.

class predicates
    permutation: (A*) -> A* nondeterm.
    select: (A [out], A*, A* [out]) nondeterm.
clauses
    permutation(L) = [A | permutation(L1)]:-
        select(A, L, L1).
    permutation([]) = [].

    select(A, [A | L], L).
    select(A, [B | L], [B | L1]):-
        select(A, L, L1).

    run():-
        write(permutation([1, 2, 3])), nl,
        fail;
        _ = readLine().

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

class predicates
    permutation_rep: (A*) -> A* nondeterm.
    select_uniq: (A [out], A*, A* [out]) nondeterm.
clauses
    permutation_rep(L) = [A | permutation_rep(L1)]:-
        select_uniq(A, L, L1).
    permutation_rep([]) = [].

    select_uniq(A, [A | L], L).
    select_uniq(A, [B | L], [B | L1]):-
        select_uniq(A, L, L1),
        A <> B.

    run():-
        write(permutation_rep([1, 2, 3, 2])), nl,
        fail;
        _ = readLine().

Отличие заключается в определении предиката select. Предикат select_uniq возвращает только попарно различные элементы списка (и список оставшихся элементов).

Для выполнения операций объединения, пересечения и разности множеств предназначены предикаты union, intersection и difference класса list.

В классе list имеются предикаты, которые выполняют аналогичные операции с более сложным определением сравнения элементов. Предикаты

differenceBy: (comparator R, A* L1,  A* L2) -> A*   
differenceEq: (predicate_dt R, A* L1, A* L2) -> A*

удаляют из списка L1 такие элементы X, для которых в списке L2 существует элемент Y, такой, что пара (X, Y) принадлежит отношению R.

Предикаты

intersectionBy: (comparator R, A* L1,  A* L2) -> A*   
intersectionEq: (predicate_dt R, A* L1, A* L2) -> A*

оставляют в списке L1 элементы X, для которых в списке L2 существует элемент Y, такой, что пара (X, Y) принадлежит отношению R.

Предикаты

unionBy: (comparator R, A* L1,  A* L2) -> A*   
unionEq: (predicate_dt R, A* L1, A* L2) -> A* 

соединяют список элементов X из L1, для которых не существует элементов Y списка L2, таких, что пара (X, Y) принадлежит отношению R, со списком L2.

open core, console, list

clauses
    run():-
        L1 = [1, 2, 3, 4, 5], L2 = [4, 2, 5],
        write(union(L1, L2)), nl,
        write(intersection(L1, L2)), nl,
        write(difference(L1, L2)), nl, nl,
        write(differenceBy({(X, Y) = compare(X mod 2, Y mod 2)},
            L1, L2)), nl,
        write(intersectionEq({(X, Y):- X mod 3 = Y mod 3}, L1, L2)),
        nl, write(unionEq({(X, Y):- X > Y}, L1, L2)),
        _ = readLine().

Упражнение 2. Определите результаты применения операций, не запуская программу, приведенную в листинге 7.4.

Предикат compare/2 сравнивает элементы произвольных доменов, но его аргументы должны принадлежать одному и тому же домену. Он возвращает значение equal, greater или less, принадлежащее встроенному домену compareResult. Аргументом продиката differenceBy/3 является процедурный предикат, а аргументом предиката intersectionEq/3 — детерминированный предикат.

7.4. Алгоритмы сортировки списка

Ниже реализуются три хорошо известных способа сортировки списка — сортировка вставками, быстрая сортировка и сортировка слиянием. Списки упорядочиваются по возрастанию элементов. Первые два алгоритма имеют сложность $$O(n^2)$$, последний алгоритм — сложность $$O(n\log n)$$.

Сортировка вставками заключается в постепенном формировании упорядоченного списка из элементов исходного списка. Изначально формируемый список полагается равным пустому списку. На каждом шаге алгоритма берется очередной элемент списка (его голова) и вставляется в формируемый список так, чтобы он оставался упорядоченным.

class predicates
    insertionSort: (A* List) -> A* SortedList.
    sort: (A* List, A* SortedList) -> A* SortedList.
    insert: (A, A* SortedList) -> A* SortedList.
clauses
    insertionSort(L) = sort(L, []).

    sort([H | T], L) = sort(T, insert(H, L)).
    sort([], L) = L.

    insert(A, [B | L]) = [B | insert(A, L)]:-
        B < A,
        !.
    insert(A, L) = [A | L].

    run():-
        R = upperBound(integer),
        L = [math::random(R) || _ = std::fromTo(1, 20)],
        write(L, "\n", insertionSort(L)),
        _ = readLine().

Предикат upperBound/1 возвращает элемент, являющийся верхней границей числового домена.

Алгоритм быстрой сортировки постепенно формирует упорядоченный суффикс S списка, который изначально полагается пустым. На каждом шаге алгоритма берется очередной элемент списка — его голова X, и хвост списка разбивается на список L1 элементов, меньших головы, и на список L2 остальных элементов. Далее алгоритм рекурсивно применяется к списку L2 и списку S, получается упорядоченный список S1. После этого алгоритм применяется к списку L1 и списку [X | S1] (заметим, что последний список упорядочен и что он является суффиксом исходного списка). В результате получается упорядоченный список.

class predicates
    quickSort: (A* List) -> A* SortedList.
    sort: (A* List, A* SortedSuffix) -> A* SortedList.
    split: (A H, A*, A* LessThanH [out], A* GreaterThanH [out]).
clauses
    quickSort(L) = sort(L, []).

    sort([H | T], L) = sort(L1, [H | sort(L2, L)]):-
        split(H, T, L1, L2).
    sort([], L) = L.

    split(H, [A | L], [A | L1], L2):-
        A < H,
        !,
        split(H, L, L1, L2).
    split(H, [A | L], L1, [A | L2]):-
        split(H, L, L1, L2).
    split(_, [], [], []).

    run():-
        L = [math::random(20) || _ = std::fromTo(1, 20)],
        write(L, "\n", quickSort(L)),
        _ = readLine().

Предикат split можно заменить предикатом filter/4 класса list, определив предикат sort/2 следующим образом:

sort([H | T], L) = sort(L1, [H | sort(L2, L)]):-
    list::filter(L, {(X):- X < H}, L1, L2),
    !.
sort(_, L) = L.

Нетрудно заметить, что если исходный список упорядочен, то разбиение хвоста на два списка относительно его головы, не приносит эффекта (см. листинг 7.6). Этого недостатка лишен алгоритм слияния.

Алгоритм сортировки слиянием делит текущий список элементов на два примерно одинаковых по длине списка (их длина может отличаться не более чем на единицу). Далее он рекурсивно упорядочивает оба списка, а затем выполняется операция слияния двух упорядоченных списков в один.

class predicates
    mergeSort: (A* List) -> A* SortedList.
    split: (A*, A* List1 [out], A* List2 [out]).
    merge: (A* SortedList1, A* SortedList2) -> A* SortedList.
clauses
    mergeSort([]) = []:- !.
    mergeSort([A]) = [A]:- !.
    mergeSort(L) = merge(mergeSort(L1), mergeSort(L2)):-
        split(L, L1, L2).

    split([A, B | L], [A | L1], [B | L2]):- !,
        split(L, L1, L2).
    split(L, L, []).

    merge([], L) = L:- !.
    merge(L, []) = L:- !.
    merge([A | L1], [B | L2]) = [A | merge(L1, [B | L2])]:-
        A < B,
        !.
    merge(L1, [B | L2]) = [B | merge(L1, L2)].

    run():-
        L = [math::random(20) || _ = std::fromTo(1, 20)],
        write(L, "\n", mergeSort(L)),
        _ = readLine().

Упражнение 3. Напишите такой вариант сортировки

чтобы одновременно с сортировкой из списка удалялись дубликаты элементов.

7.5. Предикаты сортировки списка

Операцию сортировки списка выполняют предикаты sort и sortBy класса list. Сортировка выполняется в соответствии с алгоритмом слияния. По умолчанию список сортируется по возрастанию элементов:

L = sort([3, 6, 5, 1, 7, 8]). 

Для упорядочения списка по убыванию элементов используется предикат sort/2:

L = sort([3, 6, 5, 1, 7, 8], descending()).

Предикат sortBy выполняет сортировку в соответствии с заданным критерием. Например, при вызове

L = sortBy({(X, Y) = compare(X mod 3, Y mod 3)}, [3, 5, 7, 6, 1])

элементы списка будут упорядочены по возрастанию в соответствии со значением их остатка от деления на 3.

Критерий сортировки можно определить как в виде анонимного предиката (см. выше), так и в виде отдельного предиката (см. листинг 7.8).

class predicates
    comp : comparator{tuple{string, integer}}.
clauses
    comp(tuple(X, N), tuple(Y, N)) = compare(X, Y):- !.
    comp(tuple(_, N), tuple(_, K)) = compare(N, K).

    run():-
        write(list::sortBy(comp, [tuple("Маша", 18), tuple("Даша", 19),
                tuple("Глаша", 18), tuple("Паша", 17)])),
        _ = readLine().

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

В следующей программе приведены примеры использования предикатов второго порядка класса list — forAll/2, fold/3, removeDuplicatesBy/2, maximumBy/2 и decompose/2.

open core, console, list

class predicates
    comp : comparator{tuple{string, integer}}.
clauses
    comp(tuple(_, N), tuple(_, K)) = compare(N, K). % по возрасту

    run():- 
        L = [tuple("Маша", 18), tuple("Даша", 19),
                tuple("Глаша", 18), tuple("Паша", 17)],
        % вывод элементов списка
        forAll(L, {(tuple(X, N)):- write(X, " - ", N), nl}), nl,

        % суммарный возраст студентов
        write(fold(L, {(tuple(_, K), S) = K + S}, 0)), nl,

         % удаление студентов того же возраста, остаются по одному
        write(removeDuplicatesBy(comp, L)), nl,

        % самый старший по возрасту студент
        write(maximumBy(comp, L)), nl,

        % разбиение на группы по возрасту
        write(decompose(L, {(tuple(_, Age)) = Age})),
        _ = readLine().

Упражнения