Prolog sublist Relation

3
votes

I'm reading Ivan Bratko's Prolog Programming for Artificial Intelligence book and I have no experience with Prolog before. In book a sublist relation for a list is formulated as:

S is a sublist of L if:
1) L can be decomposed into two lists, L1 and L2, and
2) L2 can be decomposed into two lists, S and some L3.

And relation is given as:

sublist(S, L) :-
    conc(L1, L2, L),
    conc(S, L3, L2).

conc([], L, L).
conc([X|L1], L2, [X|L3]) :-
    conc(L1, L2, L3).

It seems odd to me why we don't just decompose list into two lists and check whether one of the lists matches with S?

3
listprologsublistdifference-lists
conc(L1, L2, L) is decomposing the list into two lists; your suggested implementation would therefore look like sublist(S, L) :- conc(_, S, L) ; conc(S, _, L). If you look at the output of that implementation with sublist(S, [1,2,3,4]), you'll notice [2,3] is never generated, but instead you get all sublists starting with 1 and also all sublists ending with 4. – Daniel Lyons

3 Answers

6
votes

I get the impression that you're very close when you write:

It seems odd to me why we don't just decompose list into two lists and check whether one of the lists matches with S?

Just decompose the list L into three lists and you're there:

  • L1 is a list that precedes the sublist ("prefix"),
  • S is the sublist itself, and
  • L3 is a list that follows the sublist ("suffix").

As conc/3 can only concatenate (or decompose) two lists—not three—a conjunction of two conc/3 goals is required.

conc(L1,L2,L), conc(S,L3,L2) expresses above relation.

5
votes

This should help; the key word/concept is difference list.

enter image description here

From "Prolog Techniques" by Attila Csenki, Chapter 2 (Free PDF with embedded ads)

A little latter in the book is this image

enter image description here

Second part of book is actually a separate book,

"Applications of Prolog" by Attila Csenki (Free PDF with embedded ads)

2
votes

For comparison purposes, the definition of the sublist/2 predicate used in the Logtalk library is:

sublist(List, List).
sublist(Sublist, [Head| Tail]) :-
    sublist(Tail, Head, Sublist).

sublist(Sublist, _, Sublist).
sublist([Head| Tail], _, Sublist) :-
    sublist(Tail, Head, Sublist).
sublist([Head| Tail], Element, [Element| Sublist]) :-
    sublist(Tail, Head, Sublist).

IIRC, this is a common definition.Some sample calls could be:

?- list::sublist(Sublist, [1,2,3]).
Sublist = [1, 2, 3] ;
Sublist = [2, 3] ;
Sublist = [3] ;
Sublist = [] ;
Sublist = [2] ;
Sublist = [1, 3] ;
Sublist = [1] ;
Sublist = [1, 2].

?- list::sublist([1,2], List).
List = [1, 2] ;
List = [_1376, 1, 2] ;
List = [_1376, _1382, 1, 2] ;
List = [_1376, _1382, _1388, 1, 2] ;
...

?- list::sublist(Sublist, List).
Sublist = List ;
List = [_1172|Sublist] ;
List = [_1172, _1178|Sublist] ;
List = [_1172, _1178, _1184|Sublist] .
...

Update

Noticed that the definition in the question and the one in my answer don't have the same semantics. The definition in the question implies consecutive elements. E.g.

?- sublist(Sublist, [1,2,3]).
Sublist = [] ;
Sublist = [1] ;
Sublist = [1, 2] ;
Sublist = [1, 2, 3] ;
Sublist = [] ;
Sublist = [2] ;
Sublist = [2, 3] ;
Sublist = [] ;
Sublist = [3] ;
Sublist = [] ;
false.

One issue in this definition is that the empty list solution is generated multiple times.