% define a predicate member(E,L) <=> E occurs as an element in the list L

member(E,[E|_]). % E is the first element of L
% if E is an element of the remaining list of L, then it is an element of L
member(E,[_|R]) :- member(E,R).


% define a predicate sort(L,M) <=> M is a sorted permutation of L (list of numbers)
sort(L,M) :- perm(L,M), sorted(M).

% when is a list of numbers sorted?
sorted([]).
sorted([_]).
sorted([E1,E2|L]) :- E1 =< E2, sorted([E2|L]).

% when is a list a permutation of another list?
perm([],[]).
perm(L,[E|R]) :- remove(E,L,LwithoutE), perm(LwithoutE,R).

remove(E,[E|R],R).
remove(E,[F|R],[F|RwithoutE]) :- remove(E,R,RwithoutE).