Pure Prolog Peano List Intersection

Question

Assume we are only looking at lists of Peano numbers. And lets assume pure_2 Prolog is not pure_1 Prolog with dif/2, but rather with pure_1 Prolog with when/2. Can we implement list intersection?

We would step back and pick up ideas from programming languages Gödel and Nu-Prolog. Thus for any needed if-then-else we would draw on this answer here. What would be:

/* pure_2 Prolog = pure_1 Prolog with when/2 */
intersect(A, B, C) :- ??

Note that nevertheless contrary to Gödel and Nu-Prolog, to adhere to pure_2 Prolog for this equestion here we would be not allowed to use ISO Prolog if-then-else (->;_). But we might use an apartness relation as demanded here.

A test case would be steadfastness:

?- intersect([s(0)], [0], X).
X = []

?- intersect([X], [Y], Z), X = s(0), Y = 0.
X = []

Answer 1

(Taking code from this and this)

less(0, s(_)).
less(s(X), s(Y)) :- less(X, Y).

neq(X, Y) :- less(X, Y); less(Y, X).

eq(0, 0).
eq(s(X), s(Y)) :- eq(X, Y).


horn_intersect([],_,[]).
horn_intersect(_,[],[]).

horn_intersect([X|Xs],List2,[X|Ms]) :- in(X,List2),horn_intersect(Xs,List2,Ms).
horn_intersect([X|Xs],List2,Ms)     :- not_in(X,List2),horn_intersect(Xs,List2,Ms).

in(X,[K|_]) :- eq(X, K).
in(X,[K|Ms]) :- neq(X, K),in(X,Ms).

not_in(_,[]).
not_in(X,[K|Ms]) :- neq(X, K),not_in(X,Ms).

Tests:

?- horn_intersect([X], [Y], Z).
X = Y, Y = 0,
Z = [0] ;
X = Y, Y = s(0),
Z = [s(0)] ;
X = Y, Y = s(s(0)),
Z = [s(s(0))] ;
X = Y, Y = s(s(s(0))),
Z = [s(s(s(0)))] ;
X = Y, Y = s(s(s(s(0)))),
Z = [s(s(s(s(0))))] ;
X = Y, Y = s(s(s(s(s(0))))),
Z = [s(s(s(s(s(0)))))] ;
X = Y, Y = s(s(s(s(s(s(0)))))),
Z = [s(s(s(s(s(s(0))))))] ;
X = Y, Y = s(s(s(s(s(s(s(0))))))),
Z = [s(s(s(s(s(s(s(0)))))))] ;
X = Y, Y = s(s(s(s(s(s(s(s(0)))))))),
Z = [s(s(s(s(s(s(s(s(0))))))))] ;
X = Y, Y = s(s(s(s(s(s(s(s(s(0))))))))),
Z = [s(s(s(s(s(s(s(s(s(...)))))))))] ;
X = Y, Y = s(s(s(s(s(s(s(s(s(s(...)))))))))),
Z = [s(s(s(s(s(s(s(s(s(...)))))))))] .

?- horn_intersect(X, Y, Z).
X = Z, Z = [] ;
Y = Z, Z = [] ;
X = Z, Z = [0],
Y = [0|_2472] ;
X = Z, Z = [0, 0],
Y = [0|_2472] ;
X = Z, Z = [0, 0, 0],
Y = [0|_2472] ;
X = Z, Z = [0, 0, 0, 0],
Y = [0|_2472] ;
X = Z, Z = [0, 0, 0, 0, 0],
Y = [0|_2472] ;
X = Z, Z = [0, 0, 0, 0, 0, 0],
Y = [0|_2472] ;
X = Z, Z = [0, 0, 0, 0, 0, 0, 0],
Y = [0|_2472] ;
X = Z, Z = [0, 0, 0, 0, 0, 0, 0, 0],
Y = [0|_2472] ;
X = Z, Z = [0, 0, 0, 0, 0, 0, 0, 0, 0],
Y = [0|_2472] ;
X = Z, Z = [0, 0, 0, 0, 0, 0, 0, 0, 0|...],
Y = [0|_2472] ;
X = Z, Z = [0, 0, 0, 0, 0, 0, 0, 0, 0|...],
Y = [0|_2472] .