All initial segments of a list in Prolog

prolog

Note that @gusbro's solution with append/3 as well as @brebs answer work well if the initial list is given, however, both permit also other solutions that are not lists.

?- L = [1|non_list], append(Segment, _, L).
   L = [1|non_list], Segment = []
;  L = [1|non_list], Segment = [1]
;  false.
?- L = non_list, append(Segment, _, L).
   L = non_list, Segment = []
;  false.

So even non_list works ; that is a term that is as far remote from a list as possible. Often such extra unwanted generalizations are accepted, in particular if you know that you will never rely upon it. Also this is know as a list prefix of a term.

But if you want to be sure that only lists are considered, use Prolog's dcg-formalism which is the method of choice in many areas.

:- set_prolog_flag(double_quotes, chars). % to make "strings" readable

... --> [] | [_], ... . % any sequence

seq([]) --> [].
seq([E|Es]) --> [E], seq(Es).

segment_of(Xs, Zs) :-
   phrase((seq(Xs), ...), Zs).

?- segment_of(Xs, "abc").
   Xs = []
;  Xs = "a"
;  Xs = "ab"
;  Xs = "abc"
;  false.
?- segment_of(Xs, non_list).
false.
?- segment_of("ab", L).
   L = "ab"
;  L = [a,b,_A]
;  L = [a,b,_A,_B]
;  L = [a,b,_A,_B,_C]
;  ...

Without using append:

% Inc can be an empty list, if Lst is a list (empty or not)
increasing_list([], []).
increasing_list([_|_], []).

increasing_list(Lst, Inc) :-
    increasing_list_(Lst, Inc).

% Unify Inc with the current element (Head) of Lst
increasing_list_([Head|_Tail], [Head]).

% Add Head element from Lst to Inc
increasing_list_([Head|Tail], [Head|Inc]) :-
    % Loop through the elements in Lst
    increasing_list_(Tail, Inc).

Result in swi-prolog:

?- increasing_list([1, 3, 6 ,9, 8], Inc).
Inc = [] ;
Inc = [1] ;
Inc = [1,3] ;
Inc = [1,3,6] ;
Inc = [1,3,6,9] ;
Inc = [1,3,6,9,8]

All initial segments of a list in Prolog

Related

Recent Posts