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?
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, andL3 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.