Расщепление списка на Prolog

В этой теме 1 ответ, 2 участника, последнее обновление  Васильев Владимир Сергеевич 2 года/лет, 8 мес. назад.

  • Автор
    Сообщения
  • #2157

    questioner
    Участник

    Есть предикат, генерирующий все варианты расщепления списка, т.е. его разделение на две части:

    splits(List, ([],List)).
    splits([Head|Tail],([Head|SplitTail], SecondPart)):- 
      splits(Tail, (SplitTail,SecondPart)).

    При запуске, интерпретатор возвращает мне следующие результаты:
    Split = ([], [1,2,3]);
    Split = ([1], [2,3]);
    Split = ([1,2], [3]);
    Split = ([1,2,3], []);
    No

    Нужно объяснить как работает эта функция.

  • #2166

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

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

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

Для ответа в этой теме необходимо авторизоваться.