Search code examples
listprologprefixdcg

Test lists to see if they are a prefix or suffix of another list

I'm stuck on a problem. I was wondering if I could get some help.

Design a predicate bookends/3 that tests if the first list argument is a prefix of the third and the second is a suffix of the third. Note that the lists in the first and second arguments may overlap.

Example Output

?-bookends([1],[3,4,5],[1,2,3,4,5]).
true.

?-bookends([],[4],[1,2,3,4]).
true.

?-bookends([1,2,3],[3,4],[1,2,3,4]).
true.

?-bookends([1],[2,3],[1,2,3,4]).
false.

What I have so far

suffix(Suffix,Suffix).
prefix([_|L],Suffix):- suffix(L,Suffix).
bookends([],[],[]).
bookends([X|L],[X|L1],[X|L2]):-
    prefix(L,L2),
    suffix(L1,L2).

How do I get suffix to work, or am I approaching this wrong?

Solution

  • Let prefix & suffix do all the work:

    bookends(A,B,C) :- prefix(A,C), suffix(B,C).

    An empty list is always a prefix of anything:

    prefix([],_).

    If they share the same first element, check the rest 

    prefix([A|B],[A|C]) :- prefix(B,C).

    You might need to write reverse:

    suffix(A,B) :- reverse(A,AR), reverse(B,BR), prefix(AR,BR).