Поиск последовательных подсписков списка

Question

Я хочу написать предикат split/2, который генерирует все последовательные списки, найденные в другом списке.

---

Пример : split([1,2,3,4],X) должен вернуть X = [4], X = [2,3], X = [1,2], X = [1,2,3] и т. Д.

Пока у меня есть только предикат, который возвращает все возможные подсписки списка:

sublist([],[]).
sublist([H|T], [H|R]) :-
    sublist(T,R).
sublist([_|T], R) :-
    sublist(T,R).

---

Однако с запросомиз примера этот предикат включает в себя нежелательные ответы, такие как X = [2,4] и X = [1,3], которые не найдены последовательно в [1,2,3,4].

Answer 1

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

Мы можем построить такой предикат следующим образом:

suffix(_, []).
suffix([H|T], [H|T2]) :-
    suffix(T, T2).

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

?- suffix([1,2,3,4],X).
X = [] ;
X = [1] ;
X = [1, 2] ;
X = [1, 2, 3] ;
X = [1, 2, 3, 4].

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

split([H|T], [H|S]) :-
    suffix(T, S).
split([_|T], S) :-
    split(T, S).

Например:

?- split([1,2,3,4],X).
X = [1] ;
X = [1, 2] ;
X = [1, 2, 3] ;
X = [1, 2, 3, 4] ;
X = [2] ;
X = [2, 3] ;
X = [2, 3, 4] ;
X = [3] ;
X = [3, 4] ;
X = [4] ;
false.

Приятно то, что мы получили второй предикат «бесплатно»: мы также можем получить все суффиксы для списка.

Мы могли бы также захотеть включить пустой список.Я оставляю это как упражнение.