Списки. Полиморфизм

Упражнение 2. Определите предикаты, которые возвращают:

В классе list, который входит в набор Prolog Foundation Classes (PFC) основных классов языка Visual Prolog имеется предикат проверки принадлежности элемента списку isMember/2 и предикат getMember_nd/1, недетерминированно возвращающий элементы списка и определенный в виде функции. В версии 7.5 языка Visual Prolog появился оператор in, который можно использовать для выполнения обеих данных операций. Например:

if 2 in [1, 2, 3] then write("2 принадлежит списку")
 else write("2 не принадлежит списку") end if, nl, nl,
        
 foreach X in [1, 2, 3] do write(X), nl end foreach.

Следующая программа посвящена предикату append, определение которого позволяет использовать его большим количеством способов, в частности:

class predicates
    append: (A*, A*, A*) nondeterm anyflow.
    append: (A*, A*) -> A*.
clauses
    append([], L, L).    % разнообразное использование
    append([H | L1], L2, [H | L]):-
        append(L1, L2, L).

    append([], L) = L.    % соединение двух списков в один
    append([H | L1], L2) = [H | append(L1, L2)].

    run():-
        append([1, 2], [2, 3], L0),
        write(L0), nl,
        write(append([1, 2], [2, 3])), nl,

        L = [1, 2, 3, 4, 5],
        append(L1, [4, 5], L),
        write(L1), nl,
        append([1, 2, 3], L2, L),
        write(L2), nl, nl,
        append(P, S, L),
            writef("% - %\n", P, S),
        fail;

        L = [1, 2, 3, 4, 5, 6, 7],
        append(_, [X, _, _], L),
        writef("\nТретий с конца элемент списка - %", X),
        append([_, _, Y], _, L),
        writef("\nТретий с начала элемент списка - %", Y),
        fail;
        _ = readLine().

Упражнение 3. Найдите с помощью предиката append:

В классе list определены предикаты append, которые могут иметь от двух до пяти аргументов, выполняющие операцию соединения списков. Кроме этого, имеется предикат appendList/1, который соединяет список списков элементов в один список.

В приведенной ниже программе непосредственно генерируются подсписки списка — префиксы, суффиксы и все подсписки.

class predicates
    prefix: (A*) -> A* multi.
    suffix: (A*) -> A* multi.
    sublist: (A*) -> A* nondeterm.
clauses
    prefix(_) = [].        % префикс списка
    prefix([H | T]) = [H | prefix(T)].

    suffix(L) = L.        % суффикс списка
    suffix([_| T]) = suffix(T).

    sublist([]) = [].        % подсписок списка
    sublist(L) = S:-
        S = prefix(L),
        S <> [].
    sublist([_ | L]) = sublist(L).

    run():-
        write(prefix([1, 2, 3, 4])), nl,
        fail;
        nl, write(suffix([1, 2, 3, 4])), nl,
        fail;
        nl, write(sublist([1, 2, 3, 4])), nl,
        fail;
        _ = readLine().

Упражнение 4.

В приведенной ниже программе реализованы операция замены одного элемента списка другим, а также операция замены каждого n-го элемента списка заданным элементом. В определении второго предиката используется счетчик.

class predicates
    replace: (A*, A What, A With) -> A*.
    replace_nth: (A*, positive N, A With) -> A*.
    replace_nth: (A*, positive Counter, positive N, A With) -> A*.
clauses
    replace([A | T], A, B) = [B | replace(T, A, B)]:- !.
    replace([H | T], A, B) = [H | replace(T, A, B)].
    replace([], _, _) = [].

    replace_nth(L, N, A) = replace_nth(L, N, N, A):-
        N > 1,
        !.
    replace_nth(L, _, _) = L.

    replace_nth([_ | L], 1, N, A) = [A | replace_nth(L, N, N, A)]:- !.
    replace_nth([H | L], C, N, A) = [H | replace_nth(L, C - 1, N, A)].
    replace_nth([], _, _, _) = [].

    run():-
        L = [math::random(10) || _ = std::fromTo(1, 20)],
        write(L), nl,
        write(replace(L, 0, 100)), nl,
        write(replace_nth(L, 6, 333)), nl,
        _ = readLine().

Предикат fromTo (см. определение предиката run) недетерминированно возвращает целые числа в заданных пределах. Например, цель

X = fromTo(1, 3)

имеет следующие решения:

X = 1
X = 2
X = 3

Упражнение 5. Определите предикат, который:

В следующей программе определена операция обращения списка, в результате выполнения которой список записывается в обратном порядке. Например, список [1, 2, 3] преобразуется в список [3, 2, 1]. В определении операции используется вспомогательный аргумент — список, в который перекладываются по одному элементы исходного списка.

class predicates
    reverse: (A*) -> A*.
    reverse: (A*, A*) -> A*.
clauses
    reverse(L) = reverse(L, []).

    reverse([], L) = L.
    reverse([A | L], L1) = reverse(L, [A | L1]).

    run():-
        write(reverse([1, 2, 3, 4, 5])), nl,
        write(reverse([1, 2], [3, 4, 5])),
    _ = readLine().

В классе list имеется предикат reverse/1, который выполняет операцию обращения списка.

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

class predicates
    split: (unsigned*, unsigned* [out], unsigned* [out]).
clauses
    split([A | L], [A | L1], L2):-
        A mod 2 = 0,
        !,
        split(L, L1, L2).
    split([A | L], L1, [A | L2]):-
        split(L, L1, L2).
    split([], [], []).

    run():-
        split([1, 2, 3, 4, 5, 9, 8, 7, 6], L1, L2),
        write(L1), nl,
        write(L2),
        _ = readLine().

Следующая программа посвящена двум важным предикатам. Первый из них — это предикат delete, который удаляет первое вхождение элемента в список. Если такого элемента в списке нет, предикат принимает значение ложь. Второй предикат — это предикат select. Предикат можно использовать двояким образом. С одной стороны, он недетерминированно возвращает произвольный элемент списка и список без этого элемента. С другой стороны, он недетерминированно вставляет заданный элемент на произвольное место в заданном списке, так что в результате получается новый список.

class predicates
    delete: (A, A*) -> A* determ.
    select: (A, A*, A*) nondeterm (o,i,o) multi (i,o,i).
clauses
    delete(A, [A | L]) = L:- !.
    delete(A, [B | L]) = [B | delete(A, L)].

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

    run():-
        L = delete(4, [1, 2, 3, 4, 5]),
        write(L), nl,
        fail;
        nl,
        select(A, [1, 2, 3, 4, 5], L),
            write(A, " - ", L), nl,
        fail;
        nl,
        select(100, L, [1, 2, 3, 4, 5]),
            write(L), nl,
        fail;
        _ = readLine().

Как упоминалось выше, элементы списка в языке Visual Prolog должны принадлежать одному и тому же домену. Поэтому в нем нельзя использовать вложенные списки напрямую и строить термы вида [[0], 1, [2, 3, [4, 5, []]]]. Но такие списки можно смоделировать. В следующей программе рекурсивно определяется домен элементов списка, включающий как атомарные элементы, так и вложенные списки. Аргументом функтора list/1 является список элементов исходного домена. Атомы — это термы с функтором at/1. В программе реализуется операция линеаризации списка — приведения его к списку атомарных элементов. Идея определения операции линеаризации с помощью вспомогательного списка, играющего роль стека, описана в [9].

domains
    elem{A} = at(A); list(elem{A}*).

class predicates
    flatten: (elem{A}*) -> elem{A}*.
    flatten: (elem{A}*, elem{A}**) -> elem{A}*.
clauses
    flatten(List) = flatten(List, []).

    flatten([list(L) | Tail], AuxList) =  flatten(L, [Tail | AuxList]):- !.
    flatten([Head | Tail], AuxList) =  [Head | flatten(Tail, AuxList)].
    flatten([], [L | AuxList]) =  flatten(L, AuxList).
    flatten([], []) = [].

    run():-
        L = [list([at(0)]), at(1), 
                list([at(2), at(3), list([at(4), at(5), list([])])])],
        writef("%\n%", L, flatten(L)),
        _ = readLine().

В языке Visual Prolog имеются развитые средства обработки исключений. Например, если функция определена только на непустых списках, то ее можно "доопределить" так, что она станет всюду определенной:

class predicates
    first: (Elem*) -> Elem*.
clauses
    first([H | _]) = [H].
    first([]) = _:-
        exception::raise_error(predicate_name(),
            "  Input list is empty.").

Если аргумент предиката first равен пустому списку, то возбуждается исключение. Предикат predicate_name возвращает имя предиката, в определении которого он участвует.

Упражнения