Find an “infix” of a list in Prolog - order matters

Question

A question from someone who knows Prolog for a week=)

I am writing some prolog command infix(Inf,List) to check if one list is, as our prof formulated, "an infix" of another list. The order matters+ it shouldn't be right at the beginning or the end of the List.

That means for example:

If we have Inf=[1,2] and List=[1,2,3,4] then is is false.

If we have Inf=[3,4] and List=[1,2,3,4] then is is also false.

If we have Inf=[2,3] and List=[1,2,3,4] then it is true.

If it is Inf=[3,2] and List=[1,2,3,4] then is is false.

If it is Inf=[2,4] and List=[1,2,3,4,5] then is is false.

I wrote some rules already and with them I seem to manage to solve the problem of order and not counting the first element of a List.

infix(Inf,List):- length(Inf,L1),length(List,L2), L1>L2, !, fail.
infix(Inf,List):- length(Inf,L1),length(List,L2), L1=L2, !, fail.
infix(Inf,List):- length(Inf,L1),length(List,L2), L1<L2, delete_first(Inf,List).

delete_first(Inf,[_L|List]):- sublist(Inf,List).

sublist([El|Sub],[El|List]):- checksublist(Sub,List).
sublist([S|Sub],[L|List]):- sublist([S|Sub],List).

checksublist([], L).
checksublist([El|Sub],[El|List]):- checksublist(Sub,List).

However, I can't formulate it in a way, so that the last element is not counted =(. According to my intuitive logic the conditionchecksublist([], L).should be smth like checksublist([], [_|[]]). But it doesn't work this way- I get false for everything.

Does anybody know how to get rid of the last element in this situation? Thanks in advance!

Answer 1

Grammars to the rescue! But I would not call this infix. It's a certain subsequence, actually even a certain substring.

infix(Inf, List) :-
   Inf = [_|_],
   phrase(([_], ..., seq(Inf), [_], ...), List).

% The following are frequently predefined

... --> [] | [_], ... .

seq([]) --> [].
seq([E|Es]) --> [E], seq(Es).

(Edit) Since you insist that both the prefix and the postfix are non-empty, you probably want this to hold for the infix too. Thus Inf = [_|_] added.

This is the result using Scryer's top level:

?- infix(Inf,"abcdef").
   Inf = "b"
;  Inf = "bc"
;  Inf = "bcd"
;  Inf = "bcde"
;  Inf = "c"
;  Inf = "cd"
;  Inf = "cde"
;  Inf = "d"
;  Inf = "de"
;  Inf = "e"
;  false.

See this how to print lists of characters as double quoted chars in other systems.

Answer 2

This is too imperative.

You can let Prolog solve it with append/2. It's search-assisted programming, let's use it.

infix(Inf,List) :- append([Prefix,Inf,Suffix],List),Prefix\=[],Suffix\=[].

This is completely declarative, in the sense that it is formulated as constraint that a solution must fulfill (very mathematical).

Test it using the Unit Test framework:

:- begin_tests(infix).

test(one,[fail]) :- infix([1,2],[1,2,3,4]).
test(two,[fail]) :- infix([3,4],[1,2,3,4]).
test(three) :- infix([2,3],[1,2,3,4]).
test(four,[fail]) :- infix([3,2],[1,2,3,4]).
test(five,[fail]) :- infix([2,4],[1,2,3,4,5]).

:- end_tests(infix).

rt:-run_tests(infix).

Then

?- rt.
% PL-Unit: infix ..
Warning: user://1:12:
        PL-Unit: Test three: Test succeeded with choicepoint
.. done
% All 5 tests passed
true.

Sadly, Prolog does not do deep reasoning and theorem proving but employs brute force: it tries possible solutions until one passes or there are no more. Weel, it's sufficient for this case.

For example:

?- append([Prefix,[3,4],Suffix],[1,2,3,4,5,3,4,6]).
Prefix = [1, 2],
Suffix = [5, 3, 4, 6] ;
Prefix = [1, 2, 3, 4, 5],
Suffix = [6] ;
false.