Разделение списка пополам на последнем элементе с последним элементом и остальным списком

Question

Например, учитывая список [1,2,3,4,5], я хочу найти последний элемент (5) и оставшийся «список отдыха», т. Е. [1,2,3,4].

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

Answer 1

В Прологе ставится задача - часто с индуктивными определениями - описать, как параметры в предикате «связаны» друг с другом, а не как «преобразовать» входные данные в выходные.Это означает, что многие предикаты, такие как member/3 и append/3, могут использоваться в разнонаправленном способе.

Пример 1 : Мы можем определитьappend/3 [swi-doc] в индуктивном определении как:

1. , если X - пустой список, то для append(X, Y, Z)Y совпадает с Z;и
2. , если X не пусто, тогда мы вычисляем append/3 для списка X без первого элемента и Y, и мы добавляем этот список ZT к первому элементуиз X.

Затем мы можем перевести это в:

append([], Y, Y).               %% (1)
append([XH|XT], Y, [XH|ZT]) :-  %% (2)
    append(XT, Y, ZT).

Пример 2 Аналогичным образом мы можем определить «фильтр».Например, мы могли бы получить все элементы, которые больше 3 в списке.Мы можем определить это индуктивно как:

1. элементы больше трех в пустом списке, это пустой список;
2. элементы больше трех в непустом списке, гдепервый элемент, меньший или равный трем, - это список элементов, превышающий три других элемента этого списка;и
3. элементы больше трех в непустом списке, где первый элемент больше трех, - это список элементов больше трех остальной части списка, с добавлением первого элемента списка.

Затем мы можем перевести это в:

larger_three([], []).          %% (1)
larger_three([H|T], F) :-      %% (2)
    H =< 3,
    larger_three(T, F).
larger_three([H|T], [H|F]) :-  %% (3)
    H > 3,
    larger_three(T, F).

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

Здесь ваш базовый случай не будет иметь дело с пустым списком, поскольку для пустого списка не существует "последнего" элемента.Базовый случай будет иметь дело со списком с одним элементом.

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

Таким образом, мы можем написать индуктивное определение как:

1. "init" и "last" списка с одним элементом - это ....
2. "init" и "последний из списка, по крайней мере, с двумя элементами могут быть определены как init и последний из ..., а мы ...

Таким образом," скелет "выглядит так:

initlast([X], ___, ___).
initlast([X1, X2|T], __, ___) :-
    ___,
    initlast(___, ___, ___),
    ___.

с ___ элементами, которые необходимо заполнить. ___ s в теле определяют предварительную обработку и последующую обработку и может просто не существовать.