Artificial Intelligence Question posted in
ChatGBT is becoming a world-wide phenomena, try it out here.

Prolog sublist Relation – Artificial Intelligence

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?

Tags:

3

Answers


  1. 0

    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)

    Login or Signup to reply.
  2. 0

    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.

    Login or Signup to reply.
  3. 0

    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.

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search