test-eff-member.pro

member(T, s1(T), s0).
member(L, s2(L, R), s1(R)).
member(L, s3(L, M, R), s2(M, R)).
member(T, ss(s1(T), s3(L, M, R)), s3(L, M, R)).
member(L, ss(s1(T), s3(L, M, R)), s3(T, M, R)).
member(M, ss(s1(T), s3(L, M, R)), s3(T, L, R)).
member(R, ss(s1(T), s3(L, M, R)), s3(T, L, M)).

member(T1, ss(s2(T1, T2), R), ss(s1(T2), R)).
member(T2, ss(s2(T1, T2), R), ss(s1(T1), R)).

member(T1, ss(s3(T1, T2, T3), R), ss(s2(T2, T3), R)).
member(T2, ss(s3(T1, T2, T3), R), ss(s2(T1, T3), R)).
member(T3, ss(s3(T1, T2, T3), R), ss(s2(T1, T2), R)).

member(T, ss(L, R), ss(U, R)) :- member(T, L, U).
member(R, s2(L, R), s1(L)).
member(M, s3(L, M, R), s1(L, R)).
member(T, ss(L, R), ss(L, U)) :- member(T, R, U).
member(R, s3(L, M, R), s2(L, M)).
member(T, ss(R, s0), U) :- member(T, R, U).

% any(N, Vars, Result, Rest).
% Select N variables from Vars and return them as Result.
% Rest - Unused variables.
any(1, [Head|Tail], [Head], Tail).
any(1, [Head|Tail], Result, [Head|Rest]) :- any(1, Tail, Result, Rest).
any(N, [Head|Tail], [Head|Result], Rest) :- N > 1, M is N - 1, any(M, Tail, Result, Rest).
any(N, [Head|Tail], Result, [Head|Rest]) :- N > 1, any(N, Tail, Result, Rest).

% expand(N, Vars, Result, Rest).
% Produce all possible trees using variables from Vars.
% Rest - unused variables.
expand(1, Vars, s0, Vars).
expand(1, Vars, s1(X), Rest)       :- any(1, Vars, L, Rest), permutation(L, [X]).
expand(1, Vars, s2(X, Y), Rest)    :- any(2, Vars, L, Rest), permutation(L, [X, Y]).
expand(1, Vars, s3(X, Y, Z), Rest) :- any(3, Vars, L, Rest), permutation(L, [X, Y, Z]).
expand(N, Vars, ss(X, Y), Rest)    :- N > 1, M is N - 1, expand(M, Vars, X, R), expand(M, R, Y, Rest).

% Run the following query to test:
% numlist(1, 12, Global), between(1, 3, Depth), between(1, 5, VarCount), 
%  any(VarCount, Global, Vars, _), expand(Depth, Vars, Tree, []), any(1, Vars, [Var], _), not(member(Var, Tree, _)).