How to get all consecutive sublists/subsets in Prolog?

Question

I would like to solve a simple problem, but even through I tried many different approaches, I couldn't find a solution for it. I am using SICStus Prolog (if that matters), and I want to get all sublists/subsets (I don't know which term is correct for this) of a list, which contains elements in succession. For example, if I have the list [1, 2, 3, 4], calling the sl/2 predicate as sl([1, 2, 3, 4], R)., the expected result is:

? - sl([1, 2, 3, 4], R).
R = [] ? ;
R = [1] ? ;
R = [1, 2] ? ;
R = [1, 2, 3] ? ;
R = [1, 2, 3, 4] ? ;
R = [2] ? ;
R = [2, 3] ? ;
R = [2, 3, 4] ? ;
R = [3] ? ;
R = [3, 4] ? ;
R = [4] ? ;
no

The best result I could reach until now is:

sl([], []).
sl([X|Xs], [X|Ys]) :-
    sl(Xs, Ys).
sl([_|Xs], Ys) :-
    sl(Xs, Ys).

But this also gives me the following unwanted results in addition:

R = [1,2,4] ? ;
R = [1,3,4] ? ;
R = [1,3] ? ;
R = [1,4] ? ;
R = [2,4] ? ;

How should I modify my predicates so I can get the desired result?

Possible duplicate of [Subsets in Prolog](https://stackoverflow.com/questions/4912869/subsets-in-prolog) — , Jun 05 '17 at 18:09

lurker · Accepted Answer · 2017-02-25T14:48:23.243

When writing a predicate in Prolog, you need to think about what the predicate means, or what relation it is defining. The reason your predicate gives non-solutions is that you are mixing meanings in your predicate clauses. They don't all really mean the same thing.

You have the predicate sl/2 which is intended to mean "sublist" (or "subsequence") but, more than that, means a sublist per the description you provided, which is a contiguous sublist (cannot have any "gaps" in it).

Now we can break down your clauses:

sl([], []).

This says the empty list is a contiguous sublist of the empty list. This is true, so is a valid fact.

sl([X|Xs], [X|Ys]) :-
    sl(Xs, Ys).

This says that [X|Ys] is a contiguous sublist of [X|Xs] if Ys is a contiguous sublist of Xs. This relation is not true. What would really be true here would be: [X|Ys] is a contiguous sublist of [X|Xs] if Ys is a contiguous prefix sublist of Xs. That is, not only does Ys need to be a sublist of Xs, but it needs to be only from the start of the list and not somewhere within this list. This is a clue that you'll need another predicate since the meaning of the relation is different.

Your final clause says that Ys is a sublist of [_|Xs] if Ys is a sublist of Xs. This appears to be true.

If we simply adjust to the above updated definitions, we get:

subseq([], []).
subseq([_|Xs], Ys) :-
    subseq(Xs, Ys).
subseq([X|Xs], [X|Ys]) :-
    prefix_subseq(Xs, Ys).

prefix_subseq(_, []).
prefix_subseq([X|Xs], [X|Ys]) :-
    prefix_subseq(Xs, Ys).

I offered the prefix_subseq/2 definition above without explanation, but I think you can figure it out.

This now yields:

| ?- subseq([a,b,c,d], R).

R = [a] ? a

R = [a,b]

R = [a,b,c]

R = [a,b,c,d]

R = [b]

R = [b,c]

R = [b,c,d]

R = [c]

R = [c,d]

R = [d]

R = []

(1 ms) yes

An interesting, compact way of defining your sublist (or subsequence) would be using the append/2 predicate:

subseq(L, R) :- append([_, R, _], L).

This says that L is the result of appending lists _, R, and _. The minor flaw in this simple implementation is that you'll get R = [] more than once since it satisfies the append([_, R, _], L) rule in more than one way.

Taking a fresh look at the definition, you can use a DCG to define a subsequence, as a DCG is perfect for dealing with sequences:

% Empty list is a valid subsequence
subseq([]) --> ... .
% Subsequence is any sequence, followed by sequence we want, followed by any sequence
subseq(S) --> ..., non_empty_seq(S), ... .

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

% non-empty sequence we want to capture
non_empty_seq([X]) --> [X].
non_empty_seq([X|T]) --> [X], non_empty_seq(T).

And you can call it with phrase/2:

| ?- phrase(subseq(S), [a,b,c,d]).

S = [] ? ;

S = [a] ? ;

S = [a,b] ? ;

S = [a,b,c] ? ;

S = [a,b,c,d] ? ;

S = [b] ? ;

S = [b,c] ? ;

S = [b,c,d] ? ;

S = [c] ? ;

S = [c,d] ? ;

S = [d] ? ;

no

We can reswizzle this definition a little and make use of a common seq//1 definition to make it more compact:

subseq([]) --> seq(_) .
subseq([X|Xs]) --> seq(_), [X], seq(Xs), seq(_).

% alternatively: seq(_), seq([X|Xs]), seq(_).

seq([]) --> [].
seq([X|Xs]) --> [X], seq(Xs).

Note that this is called a [substring](https://en.wikipedia.org/wiki/Substring)/sublist but not a [subsequence](https://en.wikipedia.org/wiki/Subsequence)! — false, Feb 25 '17 at 14:31
Not sure why you do not permit `[]` in `seq//1`. The empty sequence - that is pretty common. — false, Feb 25 '17 at 14:33
@false generally I agree. Originally, I did have `seq([]) --> []` as a base case, but not `subseq([]) --> ... .` In this context, permitting `[]` in `seq//1` results in multiple matches of `[]` in the solution set. Technically, `[]` satisfies the definition of the original predicate multiple ways, but I was wanting to avoid it in a "natural" way. I changed the name of `seq//1` in my answer to `non_empty_seq//1`. — lurker, Feb 25 '17 at 14:37
Is it natural to use a misleading name? You can say `{Xs=[_|_]}, seq(Xs)` instead. With `Xs` of fixed length, this is significantly more efficient. And otherwise probably too (would need to measure). — false, Feb 25 '17 at 14:40
That is fine. It's most natural definition would be: `non_empty_seq(Xs) --> {Xs = [_|_]}, seq(Xs).` — false, Feb 25 '17 at 14:43

How to get all consecutive sublists/subsets in Prolog?

1 Answers1