% -*- prolog -*-

% scheme: (x y z)       (x . (y . (z . ())))

% prolog: [x,y,z]       cons(x,cons(y,cons(z,nil)))
%                       [x | [y | [z | []]]]

% membership

% NO:    member(X,nil)   ...  NOT!


% _ = singleton variable

mem(X, cons(X, _)).
mem(X, cons(_, Z)) :- mem(X, Z).

memb(X, [X | _]).
memb(X, [_ | Z]) :- memb(X, Z).

% s(X, Y) means Y has same elements as X, but sorted.
% s(X, Y)

s([], []).
s([A|X], Y) :- app(Y1, [A], Y2, Y), app(Y1, Y2, Y0), s(X, Y0).

same_len([], []).
same_len([_ | X], [_ | Y]) :- same_len(X, Y).

app([], X, X).
app([A|X], Y, [A|Z]) :- app(X, Y, Z).

app(W, X, Y, Z) :- app(WX, Y, Z), app(W, X, WX).

membe(A, X) :- app(_, [A], _, X).
