% nm(X,Y, L): X and Y are neighbor members (elements) in L. nm(X, Y, L) :- append(_,[X,Y|_], L). % nid(L): L contains non-identical neighbor elements nid(L) :- nm(X,Y,L), X\==Y. % iprefN(L, P): P is a maximal nonempty prefix of L, % which consists of identical elements. ipref1(L, [H|T]) :- append([H|T], S, L), \+ nid([H|T]), ( S == [] -> true ; S \= [H|_] ). ipref2(L, [H|T]) :- append([H|T], S, L), \+ nid([H|T]), \+ S = [H|_]. % can be replaced by: S \= [H|_]. ipref3(L, P) :- P = [H|_], append(P, S, L), \+ nid(P), S \= [H|_]. ipref4(L, P) :- P = [H|_], append(P, S, L), \+ (nm(X,Y,P), X \== Y), S \= [H|_]. ipref5(L, P) :- P = [H|_], % P is nonempty, has head H append(P, S, L), % P is a prefix of L \+ (append(_,[X,Y|_], P), X \== Y), % P consists of identical elements S \= [H|_]. % S, the part of L after P (*) % does not start with H % (this ensures that P is maximal). % There is a snag in the above code, for example % | ?- iprefN([X,Y], P). % fails for N = 1..5. % This snag happens only when unbound variables occur as list elements. % Explanation: if, in line (*), H is an unbound variable, and S is a non-empty list, % then the \= check is bound to fail, as a nonempty list always unifies with % [H|_], if H is a variable. % The final version, that allows arbitrary Prolog terms as list elements is this: % P is a maximal nonempty prefix of L, which consists of identical elements. ipref_final(L, P) :- P = [H|_], % P is nonempty, has head H append(P, S, L), % P is a prefix of L \+ (append(_,[X,Y|_], P), X \== Y), % P consists of identical elements ( S = [H1|_] -> H \== H1 % if S, the part of L after P, is non-empty % then its head is not identical to H ; true % or else (if S is empty), succeed ). % (this if-then-else ensures that P is maximal).